[已解决]第23讲 递归问题 不理解是怎么运行的

xxpy_601

def fab1(n):
    if n < 1:
        print('输入有误！')
        return -1
    if n ==1 or n == 2:
        return 1
    else:
        return fab1(n-1) + fab1(n-2)
result = fab1(20)
if result != -1:
    print('总共有%d对小兔崽子诞生' % result)

跟着小甲鱼的第23讲代码写的，虽然计算结果正确。
但是无法理解fab1 是怎么运行的和结果是怎么得出来的。

最佳答案

月排行榜 / 总排行榜

winlans

2018-1-22 13:23:04

xxpy_601 发表于 2018-1-22 12:33
用画图的方法，能明白。
但是不知道为什么会是这样的计算结果

递归函数是不可能同时运行的， 你能看懂图示的话， 应该是可以理解的， 递归函数会压栈，直到递归到结束条件， 函数开始弹栈， 结果会一层一层的返回。

跳转到最佳答案楼层

BngThea

递归，你需要理解：
1 进入递归的时候，后续的代码会暂时搁置不执行，重新进入该函数
2 等到返回的时候，从上面后续暂停的代码处开始执行

xxpy_601

用画图的方法，能明白。
但是不知道为什么会是这样的计算结果

用可视化分解程序执行的时候，
会打印
n = 6
n = 5
n = 4
n = 3
n = 2 结果是1
n = 1 结果是1
n = 3 结果是2
n = 2 结果是1
n = 4 结果是3
n = 3
n = 2 结果是1
n = 1 结果是1
n = 3 结果是2
等等 这块能理解，倒着执行 先执行 n-1的结果 再执行n-2 的结果最后求和
不能理解的是为什么前面会有n= 6 5 4 3  一直到2 才分别执行n-1 和 n-2的结果
难道是这里先执行 return fab1(n-1) + fab1(n-2) 中的fab1(n-1)才会这样吗？
为什么这里不同时执行 fab1(n-2)呢？

winlans

xxpy_601 发表于 2018-1-22 12:33
用画图的方法，能明白。
但是不知道为什么会是这样的计算结果

递归函数是不可能同时运行的， 你能看懂图示的话， 应该是可以理解的， 递归函数会压栈，直到递归到结束条件， 函数开始弹栈， 结果会一层一层的返回。

xxpy_601

如果n=6的话，程序运行顺序是不是下面的（视频中没有讲过压栈是怎么回事，所以不太理解，是不是可以理解为闭包呢，感觉挺像的）
n6=n5(6-1)=n4(5-1)=n3(4-1)=(n3-1)and(n3-2)
(n3-1)= if n==2: =1
(n3-2)=1 if n==1: =1
n3=(n3-1)+(n3-2)=2
n4=n3（这里是不是就是压栈,因为已经得到结果并存储起来了）+（(n4-2)=2 ifn ==2： =1）=3
n5=n4（这里是不是就是压栈,因为已经得到结果并存储起来了）+((n5-2)=3=((3-1）=2 if n==2: =1)+(3-2)=1 if n==1: =1))=5
n6=n5（这里是不是就是压栈,因为已经得到结果并存储起来了）+((n6-2)=4=(((4-1)=(n3-1)+(n3-2)=2) +((4-2)=n2=1)))=8
最后 返回结果8