用斐波那契数列理解递归

Question

用斐波那契数列理解递归

15

我试图更好地理解递归和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语句是写成要返回两个函数f(n-1) + f(n-2)的总和，这种情况下我认为返回值应该是5？你能把两个函数加起来吗？

非常感谢您的帮助。

以下是Visualize Python中的代码链接：两个函数的总和

- efw

4

不是添加两个函数，而是添加调用函数返回的整数。每个调用都是完全独立的，特别是每个调用都有自己私有的 n 值。 - jasonharper

2个回答

4

添加一些打印语句也可以帮助澄清顺序：

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

- rnso

这段代码无法处理输入中的大数字。您应该考虑运行时间。 - Akshay Sapra

2

@Akshay Sapra，我认同避免记忆化会使函数缺乏灵活性，但OP询问的是“返回语句如何工作”。这里很好地解决了递归的基本原理，这正是问题所在。 - Daniel Scott

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- cs95 · Accepted Answer

如果不确定，就把它分解。

实际上，树形流程与实际控制流是反直觉的，但一旦您了解了调用序列，它就变得更清晰。这里需要理解的是，您将一个较大的计算分解为若干个小计算的总和，并在达到基本情况（即if语句）时停止。现在，您可以执行所有的小计算，并将这些小计算的结果组合成更大的结果，直到获得最终答案。

每次递归调用达到基本情况时，它将返回1或0，具体取决于命中的情况。这个值将返回给上一个调用者。为了理解，请考虑:

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

请注意，下标代表递归调用树的深度。调用是由f(2)₂发起的。首先计算f(1)₃，并将1返回给f(2)₂。然后计算f(0)₃，并将0返回给f(2)₂。两个返回值相加，结果为1。

f(2)₂然后向调用它的人返回1，在这种情况下，是f(3)₁。 f(3)₁调用了f(2)₂ + f(1)₂，同时另一个f(1)₂也向f(3)₁返回1，现在将其与f(2)₂的结果相加，得到2。

f(3)₁现在将2传递给它的调用者f(4)₀，后者恰好调用了f(3)₁ + f(2)₁，如此反复。

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

f(4)₀计算f(3)₁ + f(2)₁。但要计算f(3)₁，它需要知道f(2)₂ + f(1)₂，同样，要计算f(2)₁，它需要知道f(1)₂ + f(0)₂，等等。