用Fibonacci级数理解递归

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，并返回到函数定义中。因此它似乎只是从else语句中的第一个函数返回值。然而，编写else语句是为了返回2个函数f(n-1)+f(n-2)的和，在这种情况下，我以为返回值是5？你甚至可以把2个功能加在一起吗？

事先谢谢你的帮助。

下面是Visualize Python Sum of 2函数中的代码链接

Answer 1

添加一些print语句还可以帮助澄清顺序：

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

Answer 2

有疑问的时候，就把它拆开。

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

每次递归调用命中基本大小写时，它将html" target="_blank">返回1或0，这取决于命中的大小写。此值将返回给上一个调用方。要理解，请考虑：

f(1)3 + f(0)3

请注意，下标表示递归调用树的深度。呼叫由F(2)2进行。首先计算F(1)3，并且1返回F(2)2。然后计算f(0)3，并且0返回f(2)2。两个返回值相加，结果为1。

f(2)2然后将1返回给调用它的人，在本例中，它恰好是f(3)1。f(3)1称为f(2)2+f(1)2，同时此其他f(1)2也将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，依此类推。