用斐波那契数列理解递归

Question

我正在努力更好地理解递归以及 return 语句的工作原理。因此，我正在查看一段代码，用于识别与给定项关联的斐波那契数——在本例中为 4。我很难理解 else 语句。

def f(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  else:
    return f(n-1) + f(n-2)

f(4)

我曾尝试使用 Visualize Python 检查每一步发生的情况，但当它遇到 else 语句时我迷路了。

看起来它正在获取 n 的值并减去 1，以创建一个新的 n 值 3，它 returns 到函数定义。所以它似乎只是 returning 来自 else 语句中第一个函数的值。然而，else 语句被写入 return 2 个函数 f(n-1) + f(n-2) 的总和，在这种情况下我认为 return 值将是 5？您甚至可以将 2 个函数加在一起吗？

在此先感谢您的帮助。

这是 Visualize Python Sum of 2 functions

中代码的 link

Answer 1

如有疑问，请将其分解。

树形流程其实和实际的控制流程是反直觉的，但是一旦理解了调用顺序，就会变得更加清晰。这里要理解的是，您不断将较大的计算分解为较小计算的总和，并在遇到基本情况（if 语句）时停止。现在你可以进行所有的小计算，并将这些小计算的结果组合起来形成一个越来越大的结果，直到你得到最终答案。

每次递归调用命中基本情况时，它都会 return 1 或 0，具体取决于命中的情况。此值将 returned 给前一个调用者。要理解，请考虑：

f(1)<sub>3</sub> + f(0)<sub>3</sub>

这里注意，下标表示递归调用树的深度。该调用由 f(2)2 发出。 f(1)3 先计算，1 returned 为 f( 2)2。然后计算 f(0)3，0 returned 为 f( 2)2。将两个 return 值相加，结果为 1。

f(2)2 然后 returns 1 给调用 it 的人，在这种情况下恰好是 f(3)1。 f(3)1 调用了 f(2)2 + f(1 )2,同时这个f(1)2也returns 1 到 f(3)1，谁现在加上 f( 2)2，组成2。

f(3)1 现在将 2 传递给 f(4)0，它的调用者，碰巧调用了f(3)1 + f(2)1 ... 就这样。

另一种看待这个问题的方法是从实际进行的第一个函数调用开始：f(4)0 .

f(4)0 计算 f(3)1 + f(2)1。但是要计算 f(3)1，它需要知道 f(2)2 + f(1)2，类似地，计算f(2)1 ，它需要知道 f(1)2 + f(0)2,等等。

Answer 2

添加一些打印语句也有助于理清顺序：

def f(n):
    print("Number received:", n)
    if n == 0:
        return 0
    if n == 1:
        return 1
    else:
        print("---- First recursion ----")
        a = f(n-1)
        print("---- Second recursion ----")
        b = f(n-2)
        print(" a=:",a,"; b=",b,"; returning:", a+b)
        return a + b

print("Final f(4)=", f(4))

输出：

Number received: 4
---- First recursion ----
Number received: 3
---- First recursion ----
Number received: 2
---- First recursion ----
Number received: 1
---- Second recursion ----
Number received: 0
 a=: 1 ; b= 0 ; returning: 1
---- Second recursion ----
Number received: 1
 a=: 1 ; b= 1 ; returning: 2
---- Second recursion ----
Number received: 2
---- First recursion ----
Number received: 1
---- Second recursion ----
Number received: 0
 a=: 1 ; b= 0 ; returning: 1
 a=: 2 ; b= 1 ; returning: 3
Final f(4)= 3

用斐波那契数列理解递归

Understanding recursion with the Fibonacci Series

python

recursion

function

fibonacci