理解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

如有疑问,请将其分解.

树流实际上与实际控制流程相反,但是一旦理解了调用顺序,它就会变得更加清晰.这里要理解的是,你不断将较大的计算分解为较小的计算总和,并在你遇到基本情况(if语句)时停止.现在,您可以执行所有小型计算,并将这些小型计算的结果组合在一起,形成更大,更大的结果,直到您得到最终答案.

每次递归调用命中基本情况时,它将返回1或0,具体取决于命中的情况.该值将返回给前一个调用者.要理解,请考虑:

f(1)3 + f(0)3

请注意,下标表示递归调用树的深度.电话是由.先计算,然后返回.然后计算,并返回.将两个返回值相加,结果为.f(2)2f(1)31f(2)2f(0)30f(2)21

f(2)2然后返回 1给谁调用它,在这种情况下恰好是.所谓的,同时这等也返回到,谁现在增加了与结果,而形成.f(3)1f(3)1f(2)2 + f(1)2f(1)21f(3)1f(2)22

f(3)1现在传递2给它的来电者,它正好打电话......所以就这样了.f(4)0f(3)1 + f(2)1

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

f(4)0计算.但是要计算,它需要知道,同样地,需要知道,等等.f(3)1 + f(2)1f(3)1f(2)2 + f(1)2f(2)1f(1)2 + f(0)2