[TIL] Python #13 재귀함수2(피보나치)

counter = 0
def fib(n):
    global counter
    counter += 1
    if n > 1:
        return fib(n-1) + fib(n-2)
    else:
        return n

print(fib(3))
print(counter)

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + fib(3)
((fib(2) + fib(1)) + fib(2) + fib(3)
(((fib(1) + fib(0)) + fib(1)) + fib(2)) + fib(3)

1단계: ((1 + 0) + 1) + fib(2) + fib(3)
2단계: (2 + (fib(1) + fib(0))) + fib(3)
3단계: (2 + (1 + 0)) + fib(3)
4단계: 3 + 2(*위에fib(3)을 찾으세요)
5단계: 5