有人可以解釋這個遞歸函數嗎？

Question

我已經做了一個遞歸函數來查找斐波那契數列的位置。用戶輸入一個數字（術語），並通過該函數運行該數字以查找該數字。

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