재귀

재귀함수란, 항시 배웠던 내용이다 .

 

일단 표헌식을 표헌할때 

T(n) = a(나누어지는 갯수) x T(n/b(분할 크기))+해당 level에서 추가적으로 하는 일

로 표현한다.

 

재귀식의 모습은

def pivot()

{ ... 

 ....

 .. return pivot() }꼴이다.

 

주로 . 재귀함수를 사용하면 몇번의 level을 거치지 않을때 사용하는 것으로 해보자. 

사용하면 안되는 경우도 있는데, 그 크기가 유사한 여러가지로 분할되거나, 갯수가 마치 현재 크기만큼 많을때 사용해선 안된다고 배웠다. 

 

간단한 예제

import sys

def fib (n) :

    if n == 0 :

        return 0

    if n == 1 :

        return 1

    return fib(n-1) + fib(n-2)

N = int(sys.stdin.readline())

print(fib(N))

 

주로 이런 방식으로,

1. 탈출의 조건(0,1등의 특이 case)

2. return값은, 함수의 재호출

 

이 2가지 규칙을 지킨다.

(하지만, 해당 문제는 n이 20 미만이란 조건이 있어 사용했고, n이 클때 피보나치를 재귀로 구하면 2의 n승으로 너무 거대하다) 

 

 

재귀 4779번. 

import sys

def cantor(s,first,last) :

   

    if first >= last :

        return s

   

    deletefirst = int((last+1)/3)

    deletelast = int(2*deletefirst-1)

    if deletefirst == deletelast :

        return s

   

    s[deletefirst:deletelast] = " "

    cantor(s,first,deletefirst-1)

    cantor(s,deletelast+1,last)

somethingleft= True

while somethingleft :

    N= int(sys.stdin.readline())

    s = ["-" for _ in range(3**N) ]

    cantor(s,0,3**N) #index 기준

    for x in s :

        print(x)

내가 작성했던 코드이고, 무한 재귀가 발생해버렸다. 

 

import sys

def cantor(first,last) :

   

    if last == 1 :

        return

    for i in range(first+last//3, first+(last//3)*2) :

        s[i] = " "

    cantor(first,last//3)

    cantor(first+(last//3)*2, last//3)

while True :

    try :

        N= int(sys.stdin.readline())

        s = ["-" for _ in range(3**N) ]

        cantor(0,3**N) #크기 기준

        print(''.join(s))

   

    except :

        break

 

참고하여 변경한 코드이다 . 오늘 배워갈 내용을 정리해보자 .

 

1. 재귀함수는, 반드시 탈출의 조건이 필요하고. 이는 last == 1 (크기가 1일때)로써, 잘 정의했다.

2. 함수 작성 과정에서 혼동이 왔다. last가 크기로 결정을 해놓고, 나중에는 index로 보아서 무한 재귀가 또 발생했다.

이를 주의하자 

index로 하려면 index로쭉, 크기로 하려면 크기로 쭉 표현하고 사용해야한다. 

3. 최종 배열을 문자열 형태로 표현할때는 ''.join(배열)로 표현할 수 있음을 기억하자. 

4. 문자열 slice s[a:b] = 3과 같은형태는 불가능함을 기억하자. 

5. 문제중, 파일의 끝에서 끝난다가 무슨 뜻인지 몰랐다.

허나 이는 eof 발생시 종료하라는 의미를 지닌다. 

마치 try catch처럼, try except로 입력의 종료를 유발했다. 

 

즉, divide and conquer로 짤때는

case 1.  가장 밑에 무엇이 될지 (종단)

case 2.  그 다음부턴 어떤 규칙으로 나아갈지

 

이 를 가장 고민하자. 

 

dfs를 , 재귀처럼 푸는 방식이 있음에 주의하자 !