<파이썬> 피보나치 수열을 재귀함수 구현 후 실행 관련 질문
조회수 953회
파이썬(피보나치 수열을 재귀함수를 활용하여 구현한 코드)
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 답변
-
대략 그렇습니다.
조금 더 확실하게는 로깅을 남겨서 확인해 보면 됩니다. 아래 데코레이터로 만든 로깅 코드이고, 그 결과입니다.
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
댓글 입력