<파이썬> 피보나치 수열을 재귀함수 구현 후 실행 관련 질문

조회수 70회

파이썬(피보나치 수열을 재귀함수를 활용하여 구현한 코드)

def fib(n):
    if  n ==1 or n==2:
        return 1
    return fib(n-1)+fib(n-2)
print(fib(6))

위의 코드를 실행시키면 print(fib(6))때문에 n에 6이 할당된 후에 return값이 fib(5)+fib(4)이 되는데 그 다음 n에 5가 어떤 방식으로 할당되게 되는 것인가요?

아래는 제가 생각하는 실행 과정을 나열해봤습니다. 틀린 부분이 있으면 수정 부탁드립니다.

1.fib(6) = fib(5)+fib(4)
2.fib(5) = fib(4)+fib(3)
3.fib(4) = fib(3)+fib(2)
4.fib(3) = fib(2)+fib(1)
5.fib(2) = 1
6.fib(1) = 1
7.fib(3) = 2
8.fib(2) = 1
9.fib(4) = 3
10.fib(3) = fib(2)+fib(1)
11.fib(2) = 1
12.fib(1) = 1
13.fib(3) = 2
14.fib(5) = 5
15.fib(4) = fib(3)+fib(2)
16.fib(3) = fib(2)+fib(1)
17.fib(2) = 1
18.fib(1) = 1
20.fib(3) = 2
21.fib(2) = 1
22.fib(4) = 3
23.fib(6) = 8

1 답변

  • 좋아요

    0

    싫어요
    채택 취소하기

    대략 그렇습니다.

    조금 더 확실하게는 로깅을 남겨서 확인해 보면 됩니다. 아래 데코레이터로 만든 로깅 코드이고, 그 결과입니다.

    def log_recurse(f, l=[0]):
        def g(*arg, **kwarg):
            print(">>" * l[0], *arg)
            l[0] += 1
            r = f(*arg, **kwarg)
            l[0] -= 1
            print("<<" * l[0], *arg)
            return r
    
        return g
    
    
    @log_recurse
    def fib(n):
        if n == 1 or n == 2:
            return 1
        return fib(n - 1) + fib(n - 2)
    
    
    print(fib(6))
    
     6        
    >> 5      
    >>>> 4    
    >>>>>> 3  
    >>>>>>>> 2
    <<<<<<<< 2
    >>>>>>>> 1
    <<<<<<<< 1
    <<<<<< 3
    >>>>>> 2
    <<<<<< 2
    <<<< 4
    >>>> 3
    >>>>>> 2
    <<<<<< 2
    >>>>>> 1
    <<<<<< 1
    <<<< 3
    << 5
    >> 4
    >>>> 3
    >>>>>> 2
    <<<<<< 2
    >>>>>> 1
    <<<<<< 1
    <<<< 3
    >>>> 2
    <<<< 2
    << 4
     6
    8
    

답변을 하려면 로그인이 필요합니다.

Hashcode는 개발자들을 위한 무료 QnA 사이트입니다. 계정을 생성하셔야만 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)

ᕕ( ᐛ )ᕗ
로그인이 필요합니다

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 계정을 생성하셔야만 글을 작성하실 수 있습니다.