누군가이 재귀 함수를 설명 할 수 있습니까?

Question

나는 fibonacci 시퀀스의 위치에서 번호를 찾는 재귀 함수를 만들었습니다. 사용자는 숫자 (용어)를 입력하고 숫자를 찾기 위해 함수를 통해 숫자를 실행합니다.

def fib(number): 

if number == 0: 
    return 0 
if number == 1: 
    return 1 
else: 
    number = fib(number - 1) + fib(number - 2) 
    return number 

user = int(input("Enter a position in the fibonacci sequence: ")) 

print fib(user) 

'4'를 입력하면 누군가가이 번호가 내 재귀 함수를 통해 어떻게 실행될 수 있는지 설명 할 수 있습니까?

감사합니다.

Answer 1

if 문으로가는 :

fib(0) = 0 

fib(1) = 1 

fib(2) = fib(2-1) + fib(2-2) 
     = fib(1) + fib(0) 
     = 1  + 0 
     = 1 

fib(3) = fib(3-1)   + fib(3-2) 
     = fib(2)    + fib(1) 
     = fib(2-1) + fib(2-2) + 1 
     = fib(1) + fib(0) + 1 
     = 1  + 0  + 1 
     = 2 

fib(4) = fib(4-1)      + fib(4-2) 
     = fib(3)       + fib(2) 
     = fib(3-1)   + fib(3-2) + fib(2-1) + fib(2-2) 
     = fib(2)    + fib(1) + fib(1) + fib(0) 
     = fib(2-1) + fib(2-2) + 1  + 1  + 0 
     = fib(1) + fib(0) + 1  + 1  + 0 
     = 1  + 0  + 1  + 1  + 0 
     = 3