Fibonacci序列的递归

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.