有人可以解释这个递归函数吗？

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