파이썬 06. 재귀함수

2019.03.07 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기.

2. 잘못된 정보를 입력했을 때 지속적으로 새롭게 실행하도록 만드는 방법

재귀함수

1. 자기가 자기 자신을 호출하는 함수 ---> 함수 내부에서 자기 자신을 또 호출

2. 기저 조건(base case) 필요 ---> 탈출 조건

3. 해결방안 - 점화식을 먼저 세우고 기저조건을 세운다.

항상 다시 시작될 자신을 호출 할 때는 return 값으로 호출 해줘야 한다.

예)

def func(num):
    func(num -1)

func(5) ---> 스텍프레임이 계속 쌓여 가므로 스텍이 터지게 된다. stack over flow

위의 예를 기저조건이 없다. 해결하기 위해 기저조건을 설정

def func(num):
    if num <= 0:
        return
    print(num)
    func(num -1)

func(5)
5
4
3
2
1

재귀함수 응용

factorial
5! = 1 x 2 x 3 x 4 x 5

5! = 4! x 5
= 3! x 4 x 5
= 2! x 3 x 4 x 5
= 1! x 2 x 3 x 4 x 5

factorial

전제조건 :

1. 점화식 -- > fac(num) = fac(num -1 ) x num

2. 기저조건 ---> if num == 1 then return 1

def factorial(num):
    if num == 1:
        return 1

    return factorial(num-1) * num     #여기에서 return이 안들어가면 실행이 안됨

factorial(5) ===> 120

for num in range(1,10):
    print(factorial(num), end=" ")   ===> 뒤에 " "을 붙여서 뛰어쓰게 해줌

1 2 6 24 120 720 5040 40320 362880

fibonacci

fibonacci

1. 점화식 ---> fibo(num) = fibo(num-2) + fibo(num-1)

2. 기저조건 num = 1 or num = 2 then return 1

예 1)

def fibo(num):
    if num == 1 or num == 2:
        return 1
    return fibo(num-2) + fibo(num-1)

예2)

def fibo_iteration(n):
    # 기저 조건 li에 설정
    li = [0, 1]
    a = 0
    while len(li) < n:  # 반복문으로 구현
        result = li[a]+li[a+1]
        li.append(result)
        a = a + 1
    return li[n-1]

예3)

def fibo_iteration_2(n):
   first = 0
   second = 1
   if n==1:
       return first
   elif n==2 :
       return second
   else :
       for i in range(2,n):
           first, second = second, first+second
   return second

위와 같이 하면 fibonacci 수열이 만들어 지게 된다.

for i in range(1, 11):
    print(fibo(i), end = "   ")

와 같이 하면 피보나치 수열의 나열을 볼 수 있다.

하지만 피보나치 수열은 재귀적으로 구현하게 되면 지속적으로 계산해서 나왔던 것을 또 구하고 또 구하는 비효율이 발생한다. 이것을 위해 스택을 활용할 수 있다.

스택을 활용한 피보나치 구현

• 피보나치 함수를 재귀함수를 통해 구현하되 내부에 캐시로 사용할 자료구조를 두고
  한번 호출되었던 값은 캐시에 저장해두었다가 다음번에 다시 같은 매개변수가 전달되면
  연산하지 않고 캐시에 저장된 값을 바로 반환하도록 구현하십시오.

def make_fibo():
    cache = [0, 1]

    def fibo_recursion(n):
        if fibo_recursion(n) in cache:
            return fibo_recursion(n)
        elif n == 1:
            return 0
        elif n == 2:
            return 1
        return fibo_recursion(n-2) + fibo_recursion(n-1)
        cache.append(fibo_recursion(n))
    return fibo_recursion


if __name__ == "__main__":
    fibo = make_fibo()
    for i in range(1, 11):
        print(fibo(i), end="  ")

하노이 타워

하노이 타워는 개인적으로 풀지 못해 굉장히 아쉬운 문제이다.

내가 그만큼 직접 해보면서 이것을 느꼈었는데 이런 걸 해결하지 못한게 아쉬울 따름이다.

하노이 타워에서 중점적으로 봐야하는 것은

1. num == 1 일 때 어떻게 해야 하는지

   1. num == 1 일 때는 시작지점에서 도착지점으로 가야 한다.

2. 마지막 n이 나오기 전에 타워는 어디로 이동해야 하는지

   1. 마지막 n은 항상 도착지점으로 가야 하므로 n-1의 타워는 중간 지점으로 가야 한다.

3. 마지막 n을 어디에 이동시켜야 하는지

   1. 마지막 n은 항상 바로 시작지점에서 도착 지점으로 가야 한다.

4. 마지막 n을 옴긴 이후에 n-1은 어떻게 해야 하는지

   1. n-1의 중간지점을 다시 시작점으로 하여 by를 거쳐 end로 가야 한다.

위를 바탕으로 하노이타워를 만들어보자

def hanoi(num , start, by, end):
    if num == 1:
        print(f"{num}번째 도형을 {start}에서 {end}로 옴겨주세요")  #1번조건
        return ---->굉장히 중요한 조건이다.
    hanoi(num -1, start, end, by)   #2번 조건
    print(f"{num}번째 도형을 {start}에서 {end}로 옴겨주세요") #3번 조건
    hanoi(num -1, by, start, end)  #4번 조건 

hanoi(5, "a", "b", "c")

1번째 도형을 a에서 c로 옴겨주세요
2번째 도형을 a에서 b로 옴겨주세요
1번째 도형을 c에서 b로 옴겨주세요
3번째 도형을 a에서 c로 옴겨주세요
1번째 도형을 b에서 a로 옴겨주세요
2번째 도형을 b에서 c로 옴겨주세요
1번째 도형을 a에서 c로 옴겨주세요
4번째 도형을 a에서 b로 옴겨주세요
1번째 도형을 c에서 b로 옴겨주세요
2번째 도형을 c에서 a로 옴겨주세요
1번째 도형을 b에서 a로 옴겨주세요
3번째 도형을 c에서 b로 옴겨주세요
1번째 도형을 a에서 c로 옴겨주세요
2번째 도형을 a에서 b로 옴겨주세요
1번째 도형을 c에서 b로 옴겨주세요
5번째 도형을 a에서 c로 옴겨주세요
1번째 도형을 b에서 a로 옴겨주세요
2번째 도형을 b에서 c로 옴겨주세요
1번째 도형을 a에서 c로 옴겨주세요
3번째 도형을 b에서 a로 옴겨주세요
1번째 도형을 c에서 b로 옴겨주세요
2번째 도형을 c에서 a로 옴겨주세요
1번째 도형을 b에서 a로 옴겨주세요
4번째 도형을 b에서 c로 옴겨주세요
1번째 도형을 a에서 c로 옴겨주세요
2번째 도형을 a에서 b로 옴겨주세요
1번째 도형을 c에서 b로 옴겨주세요
3번째 도형을 a에서 c로 옴겨주세요
1번째 도형을 b에서 a로 옴겨주세요
2번째 도형을 b에서 c로 옴겨주세요
1번째 도형을 a에서 c로 옴겨주세요

와 같이 하면 하노이 문제를 풀 수 있다.

참고 사이트