3

我无法理解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”

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

我认为这是一个非常新的问题，但我无法真正了解其过程。

4

4 回答 4

5

你为什么不做这样的事情：

>>> 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

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

于 2012-06-24T21:01:10.123 回答
3

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

有关系吗？

发生的事情是该函数被调用了两次。一次是number-1，一次是-2，因为那个值number被传递给函数的当前“实例”。

说你打电话fibonacci(3)。那条线最终会是：

return fibonacci(2) + fibonacci(1)
于 2012-06-24T20:44:47.210 回答
2

我非常喜欢诺伦皇室的回答，但还是有点难以想象。所以，经过一番折腾： 在此处输入图像描述

...时间从左到右流动的地方，稍作调整以防止一些重叠的边缘。不递归的叶子节点是橙色的。

于 2012-06-24T21:04:47.140 回答
2

一开始我在理解递归时遇到了一些麻烦，所以我会尝试通过这个函数。

现在假设您调用 fibonacci(4)

由于数字大于 2 python 将转到此行：

返回斐波那契（数字-1）+斐波那契（数字-2）

因此它将开始评估并调用：

斐波那契 (3) #这是斐波那契 (4 - 1)

因为每次遇到函数调用时，它都必须运行它（可以这么说）。

所以现在它会尝试做 fibonacci(3)，因为它大于 2：

它将再次进入这一行：

返回斐波那契（数字-1）+斐波那契（数字-2）

现在它用 3 调用它，所以当它到达 fibonacci(number-1) 时，它将执行以下操作：

斐波那契(2) #这是斐波那契(3 - 1)

由于数字等于 2，因此此递归调用将返回 1。现在您必须记住/想象 python 知道 fibonacci(2) 的答案可以这么说。

所以现在它有了 fibonacci(2) 的答案，它将继续执行这一行：

返回斐波那契（数字-1）+斐波那契（数字-2）

具体来说：+ fibonacci(number-2)

请记住，我们正站在斐波那契（2）中，所以这将执行斐波那契（1），这将返回 1。

所以现在当我们返回时，我们开始返回，也就是说，我们递归地退出函数。

出了什么问题？当我们做斐波那契（4）时，我们需要知道斐波那契（3），斐波那契（2），斐波那契（1），现在我们知道了。

所以当它递归到斐波那契（3）时，它需要知道斐波那契（2）和斐波那契（1）并且它知道，所以现在我们现在是斐波那契（3）。

现在我们回到斐波那契（4），我们需要知道斐波那契（3）和斐波那契（2），我们都知道，所以它会返回什么，两者的总和。

我希望很清楚，递归很难遵循，但通过练习会变得更好。

尝试通过调用来跟踪函数调用（用铅笔写下）你正在调用什么调用，以及你从调用中得到的结果。

请记住，在这种递归中，您会在“寻找答案”的递归级别中下降，当您获得这些答案（返回）时，您会再次返回以给出未知值的答案。

于 2012-06-24T21:13:50.453 回答