[已解决]一个关于递归的问题，请教各位鱼友

063724901

def fib(n):
    if n==1 or n==0:
        return 1
    else:
        a=fib(n-1)
        b=fib(n-2)
        c=a+b
        return c
当n=4 的时候 为什么c是等于5；
return 在这个函数中起到了什么作用。
程序开始执行的过程是先递归 fib(a) 一直递归到 a=fib(1)=1；再接着递归 fib(b) 一直到b=fib(0)=1
那为啥接下来算c=a+b 不就直接等于1+1=2了吗？为什么结果会是5呢?

最佳答案

月排行榜 / 总排行榜

chakyam

2017-11-6 15:52:27

f4
=f3+f2
=(f2+f1)+(f1+f0)
=((f0+f1)+f1)+(f1+f0)
=3f1+2f0
=5

补个图

跳转到最佳答案楼层

chakyam

f4
=f3+f2
=(f2+f1)+(f1+f0)
=((f0+f1)+f1)+(f1+f0)
=3f1+2f0
=5

补个图

063724901

chakyam 发表于 2017-11-6 15:52
f4
=f3+f2
=(f2+f1)+(f1+f0)

可是计算机程序在执行这段代码的过程中 是先将a=fib(n-1) 递归结束啊，然后再执行b=fib(n-2)啊。并不是直接算fib(4)=fib(3)+fib(2).如果按照计算机代码一步步的执行下来，我依旧想不明白为啥 c=5

063724901

chakyam 发表于 2017-11-6 15:52
f4
=f3+f2
=(f2+f1)+(f1+f0)

这张图思考的方向是人来算这段代码，并不是计算机执行代码的过程 ，按照计算机执行代码的顺序 我==不懂

063724901

chakyam 发表于 2017-11-6 15:52
f4
=f3+f2
=(f2+f1)+(f1+f0)

谢谢你

Teagle

拿走不谢

以后递归都可以采用类似的办法进行考虑

063724901

Teagle 发表于 2017-11-6 19:46
拿走不谢

以后递归都可以采用类似的办法进行考虑

谢谢谢谢，一直没看到。