python 的斐波那契数列 递归逻辑
2018-09-06 本文已影响0人
风铃_2a53
斐波那契数列 ：0，1，1，2，3，5，8，13，21，34，55，89.........
f(0)=0
f(1)=1
f(2)=1
f(3)=2 =f(2)+f(1)
f(4)=3 =f(3)+f(2)=f(2)+f(1)+(2)
f(5)=5 =f(4)+f(3)=f(3)+f(2)+f(2)+(1)=f(2)+f(1)+f(2)+f(2)+(1)
f(6)=8 =f(5)+f(4)=f(4)+f(3)+f(3)+f(2)
=f(3)+f(2)+f(2)+f(1)+f(2)+f(1)+f(2)
=f(2)+f(1)+f(2)+f(2)+f(1)+f(2)+f(1)+f(2)
f(7)=13
f(8)=21
f(9)=34
f(10)=55
fib(5)==f(4)+f(3)=f(3)+f(2)+f(2)+(1)=f(2)+f(1)+f(2)+f(2)+(1)
第一步 fib（5）拆解
》》》return fib（4）+fib（3）
》》》return (fib（3）+fib（2）) + fib（3）
》》》return [ (fib(2)+fib(1)) +fib(2)] + (fib(2)+fib(1))
》》》执行结束跳出
精髓在于拆解fib（n）拆解成若干个 都 可以跳入的if判断中return 1 ，这个程序就执行完了
执行的 每个fib 都跳入到return 1 ，执行结束，程序结束
每一个栈帧就代表了被调用中的一个函数，这些函数的栈帧是已先进后出的方式排列起来的，，就形成一个栈
