“费波纳奇回归”是怎么回事？在这个项目里？

Question

我在理解return fibonacci( number-1 ) + fibonacci( number-2 )在以下程序中的作用时遇到问题：

import sys
def fibonacci( number ):
    if( number <= 2  ):
        return 1
    else:
        return fibonacci( number-1 ) + fibonacci( number-2 )

问题是我无法想象这行代码是如何工作的：

return fibonacci( number-1 ) + fibonacci( number-2 )

同时处理"fibonacci( number-1 )“和"fibonacci( number-2 )”吗？或者"fibonacci( number-1 )“是第一个要处理的，然后是第二个？

我只看到处理这两个参数最终都会返回'1‘，所以我期望看到的最后一个结果是'1 + 1’= '2‘

如果有人能详细解释一下它的计算过程，我将不胜感激。

我认为这是一个非常新的问题，但我不能真正了解它的过程。

Answer 1

你为什么不这样做呢：

>>> def fibonacci(number):
...     if number < 2:
...         return number
...     print "Number is currently %d, getting fibonacci(%d)" % (number, number - 1)
...     minus_one = fibonacci(number-1)
...     print "Number is currently %d, just got fibonacci(%d), now getting fibonacci(%d)" % (number, number - 1, number - 2)
...     minus_two = fibonacci(number-2)
...     print "Number is currently %d, returning %d + %d" % (number, minus_one, minus_two)
...     return minus_one + minus_two

所以当你调用fibonacci时，你会得到这样的结果：

>>> fibonacci(4)
Number is currently 4, getting fibonacci(3)
Number is currently 3, getting fibonacci(2)
Number is currently 2, getting fibonacci(1)
Number is currently 2, just got fibonacci(1), now getting fibonacci(0)
Number is currently 2, returning 1 + 0
Number is currently 3, just got fibonacci(2), now getting fibonacci(1)
Number is currently 3, returning 1 + 1
Number is currently 4, just got fibonacci(3), now getting fibonacci(2)
Number is currently 2, getting fibonacci(1)
Number is currently 2, just got fibonacci(1), now getting fibonacci(0)
Number is currently 2, returning 1 + 0
Number is currently 4, returning 2 + 1
3

它仍然很复杂，但至少现在您可以看到函数正在做什么来计算您的数字。

Answer 2

是否同时处理"fibonacci( number-1 )“和"fibonacci( number-2 )”？或者"fibonacci( number-1 )“是第一个要处理的，然后是第二个？

有关系吗？

发生的情况是该函数被调用了两次。对于传递给函数的当前“实例”的number的值，一次使用number -1，一次使用-2。

假设你打电话给fibonacci(3)。这一行最终会是：

return fibonacci(2) + fibonacci(1)

Answer 3

我非常喜欢诺伦·罗亚尔的回答，但这仍然有点难以想象。所以，在闲聊了一下之后：

​

..。其中时间从左到右流动，略微调整以防止一些重叠的边。不递归的叶节点是橙色的。