斐波那契数列之小兔子递归的每一步分析
本帖最后由 lzb1001 于 2023-6-19 21:30 编辑def fab(n):
if n < 1:
print(n) # 目的用于测试！
return -1
elif n == 1 or n == 2:
print(n) # 目的用于测试！
return 1
else:
print(n) # 目的用于测试！
return fab(n - 1) + fab(n - 2)
result = fab(7)
if result != -1:
print(f' 7 个月总共有兔子：{result} 对！')
运行后：红色字体为我手动加的注释用于说明输出的值的由来，不知道大家是否看得懂，空白部分没搞懂所以没注释，烦请大神帮忙补充完整【问题1】
fab(7) ---> else: ---> print(7) ： 7
fab(7-1) ---> else: ---> print(6)： 6
fab(6-1) ---> else: ---> print(5)： 5
fab(5-1) ---> else: ---> print(4): 4
fab(4-1) ---> else: ---> print(3)： 3
fab(3-1) ---> elif n == 1 or n == 2: ---> print(2)： 2，同时return 1
1
2
3
2
1
4
3
2
1
2
5
4
3
2
1
2
3
2
1
7 个月总共有兔子：13 对！
哪位大神可以根据上面帮我画一个类似下面的图？我画了几次感觉都不对【问题2】
万分感谢！ 哪位大神帮忙指点下迷津{:10_254:} 本帖最后由 歌者文明清理员 于 2023-6-19 22:45 编辑
好的，让我来帮您回答问题。
【问题1】您的程序是一个递归求解斐波那契数列第n项的函数。当n >= 3时，会调用两次fab函数，分别传入n-1和n-2作为参数，最终将它们的返回值相加并返回。每次调用fab函数时，会打印出当前的参数值n。因此，运行后控制台中的数字是所有调用fab函数时传入的参数值，按照从大到小的顺序排列的。最后，函数返回的结果表示斐波那契数列的第n项。
【问题2】下面是一个简单的示意图，展示了fab(7)调用过程中的递归树。节点上方的数字表示当前调用fab函数时传入的参数值n，节点下方的数字表示对应调用fab函数返回的结果值。
fab(7)
/ \
fab(6) fab(5)
/ \ / \
fab(5) fab(4) fab(4) fab(3)
/ \ / \ / \/ \
fab(4) fab(3) fab(3) fab(2) fab(3) fab(2)
/ \ / \ / \/ \/ \
... ... ... ... ... ... ...
希望能帮助到您！
页:
[1]