python - 斐波那契数列的递归

Question

我需要一些帮助来理解这里发生的处理，所以假设我打电话给fib(5)我想要斐波那契 5，即 8。但我试图理解算法的大脑说它不是。这就是我（错误地）认为的方式：

return fib(4) + fib(3) // Stack frame 1
return fib(3) + fib(1) // Stack frame 2

现在因为 x 是 1 fib(1)，条件语句if x == 0 or x == 1:导致递归结束。根据我的逻辑，这将变成 3+1+4+3。请纠正我的错误逻辑。

def fib(x):
    """assumes x an int >= 0
       returns Fibonacci of x"""
    assert type(x) == int and x >= 0
    if x == 0 or x == 1:
        return 1
    else:
        return fib(x-1) + fib(x-2)

Answer 1

以下是所发生情况的完整扩展：

fib(5) expands to fib(4)+fib(3)
  fib(4) expands to fib(3)+fib(2)
    fib(3) expands to fib(2)+fib(1)
      fib(2) expands to fib(1)+fib(0)
        fib(1) evaluates to 1
        fib(0) evaluates to 1
      fib(1) evaluates to 1
    fib(2) expands to fib(1)+fib(0)
      fib(1) evaluates to 1
      fib(0) evaluates to 1
  fib(3) expands to fib(2)+fib(1)
    fib(2) expands to fib(1)+fib(0)
      fib(1) evaluates to 1
      fib(0) evaluates to 1
    fib(1) evaluates to 1

如果你数一数，你会得到 8 作为答案。

Answer 2

对于所有x大于 1，fib函数调用自身两次：

1. fib(5)变成fib(4) + fib(3)
2. 并扩展到(fib(3) + fib(2)) + (fib(2) + fib(1))
3. 并扩展到((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + 1)
4. 扩展到(((fib(1) + fib(0)) + 1) + (1 + 1)) + ((1 + 1) + 1)
5. 扩展到(((1 + 1) + 1) + (1 + 1)) + ((1 + 1) + 1)

总和为8。