斐波那契递归实现代码执行的流程
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 :
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这两步同时进行？ 在这种情况下，调用红色的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)。
在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 于 2023-6-29 22:34 编辑
相信很多初学者对递归调用执行和返回的困惑和我是一样的……
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所言，确实对初学者而言这种递归调用的过程可能会有一些难以理解 我赞同 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)。递归调用的过程是按照一定的顺序进行的，当遇到基本情况时会返回结果，然后再根据返回结果计算上一层的值，最终得到整个递归调用的结果。 sfqxx 发表于 2023-6-29 23:15
我赞同 B。
在执行fib(3)的过程中，递归调用的顺序是有规律的，可以通过画出递归调用树来更清晰地理解。
...
所以你和二楼Ewan-Ahiouy的看法一致，我和三楼isdkz的看法一致
请小甲鱼深更半夜别潜水了，有空出来冒个泡，给大家解疑释惑下啊 lzb1001 发表于 2023-6-29 23:21
所以你和二楼Ewan-Ahiouy的看法一致，我和三楼isdkz的看法一致
请小甲鱼深更半夜别潜水了，有空出来 ...
@小甲鱼 lzb1001 发表于 2023-6-29 23:21
所以你和二楼Ewan-Ahiouy的看法一致，我和三楼isdkz的看法一致
请小甲鱼深更半夜别潜水了，有空出来 ...
你先不要管递归，不要把简单的问题想复杂了
fib(2) + fib(1) 肯定是先进入 fib(2) 得到 fib(2) 的结果后再来执行 fib(1) 呀，这两个是按顺序执行的，并不是并行的关系
本帖最后由 lzb1001 于 2023-7-2 09:32 编辑
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 指的是函数相应返回的值 小甲鱼 发表于 2023-7-1 02:23
老外的这个 1、2、3、4、5 指的是函数相应返回的值
小甲鱼指的是老外那张图里斜向右上方的箭头旁边写的值吗？ lzb1001 发表于 2023-7-1 23:00
小甲鱼指的是老外那张图里斜向右上方的箭头旁边写的值吗？
是的~ 小甲鱼 发表于 2023-7-1 23:26
是的~
谢谢小甲鱼大师的亲自指点
页:
[1]