斐波那契数列之小兔子递归的每一步分析

lzb1001

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】


万分感谢！

lzb1001

哪位大神帮忙指点下迷津

歌者文明清理员

好的，让我来帮您回答问题。

【问题1】您的程序是一个递归求解斐波那契数列第n项的函数。当n >= 3时，会调用两次fab函数，分别传入n-1和n-2作为参数，最终将它们的返回值相加并返回。每次调用fab函数时，会打印出当前的参数值n。因此，运行后控制台中的数字是所有调用fab函数时传入的参数值，按照从大到小的顺序排列的。最后，函数返回的结果表示斐波那契数列的第n项。

【问题2】下面是一个简单的示意图，展示了fab(7)调用过程中的递归树。节点上方的数字表示当前调用fab函数时传入的参数值n，节点下方的数字表示对应调用fab函数返回的结果值。

1.                         fab(7)
   
2.                       /        \
   
3.                  fab(6)         fab(5)
   
4.                 /     \        /     \
   
5.            fab(5)    fab(4)   fab(4)   fab(3)
   
6.            /     \   /     \   /     \  /    \
   
7.         fab(4) fab(3) fab(3) fab(2) fab(3) fab(2)
   
8.          /     \ /    \   /    \  /    \  /    \
   
9.         ...   ...   ...   ...   ...   ...   ...

复制代码

希望能帮助到您！