斐波那契递归实现代码执行的流程

lzb1001

def fib(n):
    if n == 0: # 当n为0时返回0
        return 0
    elif n == 1: # 当n为1时返回1，实际n == 2时也是return 1，所以也可写成elif n == 1 or n == 2: 或 elif n in [1, 2]:
        return 1
    else:
        return fib(n - 1) + fib(n - 2) # 当n大于1时，用递归的方法调用函数求第n-1和第n-2个斐波那契值

当 n = 3 时传入 3 ：

3不等于0，也不等于1，所以会执行else语句，从而返回 fib(3 - 1) + fib(3 - 2)即fib(2) + fib(1)

接下去有点糊涂了，是A还是B:

A. 调用红色fib(2)传入2？

B. 还是说调用红色fib(2)传入2和调用蓝色fib(1)传入1这两步同时进行？

Ewan-Ahiouy

在这种情况下，调用红色的fib(2)和蓝色的fib(1)是同时进行的。因为在求解fib(3)的过程中，需要分别计算fib(2)和fib(1)的值，然后将它们相加才能得到fib(3)的值。

具体执行流程如下：
1. 调用fib(3)时，根据递归的定义，需要计算fib(2)和fib(1)的值。
2. 在计算fib(2)的过程中，同样需要计算fib(1)的值，因此会继续调用fib(1)。
3. 对于fib(1)，直接返回1作为结果。
4. 回到计算fib(2)，再次调用fib(1)并返回1作为结果。
5. 根据fib(n) = fib(n-1) + fib(n-2)的递归公式，将fib(2)和fib(1)的结果相加，得到fib(3)的结果。
6. 最终，fib(3)的值为2。

所以，整个过程中会同时调用红色的fib(2)和蓝色的fib(1)来计算fib(3)。

isdkz

在Python中，函数的调用过程是顺序的，也就是说在斐波那契的递归调用中，会先执行 "fib(2)"，然后再执行 "fib(1)"。所以是选项A，首先调用fib(2)。这个过程并不是并行的，因此不是选项B。这种执行顺序在语言层面是规定好的，所有函数调用都是这样的。

这是因为在计算  fib(n - 1) + fib(n - 2)  这个表达式时，需要先计算出  fib(n - 1)  的值，然后才能进行加法操作。计算  fib(n - 2)  的步骤需要等待  fib(n - 1)  计算完成并返回结果之后才能开始。

这种递归调用的过程可能会有一些难以理解，因为每次函数调用都会创建一个新的上下文环境，保存函数的局部变量和执行状态。当  fib(n - 1)  调用返回结果之后，会返回到原来的上下文中，然后再进行  fib(n - 2)  的计算。

递归调用的过程如下：

1.  fib(3)  调用  fib(2)  和  fib(1)
2.  fib(2)  会继续调用  fib(1)  和  fib(0)
3.  fib(1)  和  fib(0)  都是基本情况，会直接返回结果，不再进行递归调用
4.  fib(2)  得到  fib(1)  和  fib(0)  的结果之后，进行加法运算，然后返回结果给  fib(3)
5.  fib(3)  再调用  fib(1) ，得到结果之后，与  fib(2)  的结果进行加法运算，得到最终结果。

lzb1001

相信很多初学者对递归调用执行和返回的困惑和我是一样的……

1、上面两位大神的说法不一样，我个人理解也比较倾向于isdkz的观点，@小甲鱼 看到的话有空可否讲解下？

下面先假设isdkz的说法是对的，那么下面的步骤分解执行：

当 n = 3 ，首先会调用函数fib(n)，也就是传入 3 ：

3 不等于 0，也不等于 1，所以会执行 else语句，从而返回 fib(3 - 1) + fib(3 - 2) 即 fib(2) + fib(1)

上面红色 fib(2) ，此时 n = 2 ，会继续调用函数fib(n)，也就是传入 2：

2 不等于 0 ，也不等于1， 所以还是会执行 else语句，从而返回 fib(2 -1) + fib(2 - 2) 即 fib(1) + fib(0)

上面蓝色fib(1) ，此时 n = 1 ，会继续调用函数fib(n)，也就是传入 1：

1不等于0，但等于1，所以会执行 elif语句， 从而返回值 1 即 fib(1) = 1

接下去然后呢……？

是回到上面黄色fib(0)了吗？

请各位理解，不要嫌弃啰嗦和执着，如isdkz所言，确实对初学者而言这种递归调用的过程可能会有一些难以理解

sfqxx

我赞同 B。
在执行fib(3)的过程中，递归调用的顺序是有规律的，可以通过画出递归调用树来更清晰地理解。

首先，当执行到fib(3)时，会调用fib(2)和fib(1)两个子问题：

             fib(3)
           /        \
      fib(2)       fib(1)

接着，继续拆分子问题fib(2)和fib(1)：

              fib(3)
           /             \
      fib(2)           fib(1)
     /       \             /
fib(1)  fib(0)        (base case, 返回值为1)

此时fib(1)和fib(0)都达到了基本情况，它们的返回值分别为1和0。

回到上一层，我们可以得到fib(2)的值，即fib(2) = fib(1) + fib(0) = 1 + 0 = 1。

接着，将这个结果代入原来的递归调用树，计算fib(3)：

              fib(3)
           /             \
          1                fib(1)
                          /
                        (base case, 返回值为1)

最后，将这个结果返回给初始调用的函数，最终得到fib(3)的值为2。

所以，答案是B. 在计算fib(3)时，同时会调用fib(2)和fib(1)。递归调用的过程是按照一定的顺序进行的，当遇到基本情况时会返回结果，然后再根据返回结果计算上一层的值，最终得到整个递归调用的结果。

lzb1001

sfqxx 发表于 2023-6-29 23:15
我赞同 B。
在执行fib(3)的过程中，递归调用的顺序是有规律的，可以通过画出递归调用树来更清晰地理解。
...

所以你和二楼Ewan-Ahiouy的看法一致，我和三楼isdkz的看法一致

请小甲鱼深更半夜别潜水了，有空出来冒个泡，给大家解疑释惑下啊

sfqxx

lzb1001 发表于 2023-6-29 23:21
所以你和二楼Ewan-Ahiouy的看法一致，我和三楼isdkz的看法一致

请小甲鱼深更半夜别潜水了，有空出来 ...

@小甲鱼

isdkz

lzb1001 发表于 2023-6-29 23:21
所以你和二楼Ewan-Ahiouy的看法一致，我和三楼isdkz的看法一致

请小甲鱼深更半夜别潜水了，有空出来 ...

你先不要管递归，不要把简单的问题想复杂了

fib(2) + fib(1) 肯定是先进入 fib(2) 得到 fib(2) 的结果后再来执行 fib(1) 呀，这两个是按顺序执行的，并不是并行的关系

lzb1001

https://www.bilibili.com/video/av93816054/?p=131，感觉按这个视频和图例的意思采用的是A即非并行，注意：下图中箭头旁边的数字是代码执行的顺序号！




另外，找到一个老外用英文讲解的视频，逐行分析递归斐波那契函数，https://www.ixigua.com/6367127506856755458，感觉按老外的视频和图例的意思采用的是B即并行，注意：下图中箭头旁边的数字是函数相应返回的值




大家感兴趣可以对比看一看

小甲鱼

A，先调用 fib(2)，再调用 fib(1)

小甲鱼

lzb1001 发表于 2023-6-30 00:55
感觉按这个视频和图例的意思采用的是A，即非并行https://www.bilibili.com/video/av93816054/?p=131

老外的这个 1、2、3、4、5 指的是函数相应返回的值

lzb1001

小甲鱼 发表于 2023-7-1 02:23
老外的这个 1、2、3、4、5 指的是函数相应返回的值

小甲鱼指的是老外那张图里斜向右上方的箭头旁边写的值吗？

小甲鱼

lzb1001 发表于 2023-7-1 23:00
小甲鱼指的是老外那张图里斜向右上方的箭头旁边写的值吗？

是的~

lzb1001

小甲鱼 发表于 2023-7-1 23:26
是的~

谢谢小甲鱼大师的亲自指点