8

考虑一下 Python 中的这个基本递归：

def fibonacci(number):
    if number == 0: return 0
    elif number == 1:
        return 1
    else:
        return fibonacci(number-1) + fibonacci(number-2)

根据斐波那契数列的 (n-1) + (n-2) 函数，这是有道理的。

Python 如何执行包含不在同一代码行内而是在同一代码行内的另一个递归的递归？'finobacci(number-1)' 是否完成所有递归，直到它达到'1'，然后它对 'fibonacci(number-2)' 执行相同操作并添加它们？

为了比较，以下用于将数字 'x' 提升为幂 'y' 的递归函数，我可以理解递归，def power 调用自身直到 y==0 ，因为在一行中只有一个递归调用。仍然不应该所有结果都是'1'，因为当y == 0时执行的最后一个命令是'return 1'，因此不返回x？

def power(x, y):
    if y == 0:
        return 1
    else:
        return x*power(x, y-1)
4

10 回答 10

16

简答

每次Python“看到”fibonacci()它都会进行另一个函数调用，并且在完成该函数调用之前不会进一步进行。

例子

所以让我们说它正在评估fibonacci(4)。

一旦到达线路return fibonacci(number-1) + fibonacci(number-2)，它就会“看到”呼叫fibonacci(number-1)。

所以现在它运行了fibonacci(3)——它还没有看到fibonacci(number-2)。要运行fibonacci(3)，就必须搞清楚fibonacci(2)+fibonacci(1)。同样，它运行它看到的第一个函数，这次是fibonacci(2).

现在它终于在运行时达到了基本情况fibonacci(2)。它评估fibonacci(1)，返回1，然后，它第一次可以继续到调用的+ fibonacci(number-2)一部分。return ，然后让return 。fibonacci()fibonacci(0)0fibonacci(2)1

现在fibonacci(3)已经获得了从 的返回值fibonacci(2)，它可以进行评估fibonacci(number-2)( fibonacci(1))。

这个过程一直持续到一切都被评估并fibonacci(4)可以返回3。

要查看整个评估的进展情况，请按照此图中的箭头进行操作：

在此处输入图像描述

于 2012-12-04T17:40:16.587 回答
10

在表达式fibonacci(number-1) + fibonacci(number-2)中，第一个函数调用必须在第二个函数调用被调用之前完成。

因此，第一次调用的整个递归堆栈必须在第二次调用开始之前完成。

于 2012-12-04T17:38:56.213 回答
5

'finobacci(number-1)' 是否完成所有递归，直到它达到 '1' 然后它对 'fibonacci(number-2)' 执行相同操作并添加它们？

是的，完全正确。换句话说，以下

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

相当于

f1 = fibonacci(number-1)
f2 = fibonacci(number-2)
return f1 + f2
于 2012-12-04T17:41:06.213 回答
3

您可以使用rcviz模块通过简单地将装饰器添加到递归函数来可视化递归。

这是上面代码的可视化：

使用 rcviz 输出 OP 函数

边按执行遍历它们的顺序编号。边缘从黑色渐变为灰色以指示遍历顺序：黑色边缘在前，灰色边缘在后。

（我在GitHub 上写了 rcviz 模块。）

于 2014-04-28T22:51:57.540 回答
2

我真的建议您将代码放在Python 导师中。

您将能够即时获得它。查看堆栈帧、参考资料等。

于 2012-12-04T17:43:27.593 回答
0

您的第二个递归函数执行此操作（示例），因此不会返回 1。

power(2, 3)

2 * power(2, 2)

2 * 2 * power(1,2)

2 * 2 * 2 * power(0,2) # Reaching base case

2 * 2 * 2 * 1

8
于 2012-12-04T17:43:01.637 回答
0

您可以自己解决这个问题，方法是在函数中放置一个打印函数，并添加一个深度，以便我们可以更漂亮地打印出来：

def fibonacci(number, depth = 0):
    print " " * depth, number
    if number == 0:
        return 0
    elif number == 1:
        return 1
    else:
        return fibonacci(number-1, depth + 1) + fibonacci(number-2, depth + 1)

打电话fibonacci(5)给我们：

5
 4
  3
   2
    1
    0
   1
  2
   1
   0
 3
  2
   1
   0
  1

我们可以看到5调用4，完成，然后调用3，然后完成。

于 2012-12-04T17:43:53.477 回答
0

Matthew 和 MArtjin 是对的，但我想我可以详细说明一下：

Python 会尽可能地从左到右做一些事情。括号中暗示了此规则的例外情况。

in x*power(x, y-1):x被评估然后power被评估

而 in fibonacci(number-1) + fibonacci(number-2),fibonacci(number-1)被评估（递归地，直到它停止）然后fibonacci(number-1)被评估

于 2012-12-04T17:44:12.173 回答
0 
  def fib(x):
    if x == 0 or x == 1:
    return 1
  else:
    return fib(x-1) + fib(x-2)

print(fib(4))

在此处输入图像描述

于 2020-04-20T18:40:08.810 回答
-1 
def fib(n):
  if n <= 1:
  return n
else :
  return fib(n - 1) + fib(n - 2)
于 2018-01-07T05:07:55.183 回答