理解斐波那契数列递归

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) 

我一直在使用可视化Python来检查每一步发生了什么尝试，但是当它击中else语句我迷路。

它看起来像取n的值并减1，创建一个新的n值3，它返回到函数定义。所以它似乎只是返回else语句中第一个函数的值。然而，else语句被写成返回2个函数f（n-1）+ f（n-2）的和，在这种情况下，我认为返回值是5？你甚至可以一起添加2个功能吗？

在此先感谢您的帮助。

下面是可视化的Python Sum of 2 functions

Answer 1

到代码的链接有疑问时，就打破它。

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

每次递归调用碰到基本情况时，它将返回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等等。

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