看图轻松理解斐波那契数列

作者:超人汪小建(seaboat)

出处:https://blog.csdn.net/wangyangzhizhou/column/info/25184/2


斐波那契

斐波那契(Leonardo Pisano ,Fibonacci, Leonardo Bigollo,1175年-1250年),又称列奥纳多,是中世纪意大利数学家。他是西方第一个研究斐波那契数列的人,并将现代书写数和乘数的位值表示法系统引入欧洲。主要作品包括《计算之书》、《几何实践》、《平方数书》等。

斐波那契数列

斐波那契数列,又称黄金分割数列或兔子数列,该数列为0、1、1、2、3、5、8、13、21、34、…,可以看到它的性质是前两项之和等于后一项。

兔子问题

斐波那契数列可以用来描述兔子繁殖问题,一般而言,兔子在出生两个月后就有繁殖能力,一对兔子每个月能生出一对小兔子。如果所有兔子都不死,那么一年后可以繁殖多少对兔子?实际结果如下,第一个月和第二个月,兔子还没有繁殖能力,所以都只有1对。第三个月生下第一对,总共有2对。第四个月老兔子继续生下一对,另一对还没有繁殖能力,总共有3对。以此类推,第五个月到第十二个月的兔子对数对应如下。

月数 1 2 3 4 5 6 7 8 9 10 11 |12
对数 1 1 2 3 5 8 13 21 34 55 89| 144

表达式

$$
f(x) = \begin{cases}
0, x=0\
1,x=1\
f(x-1) + f(x-2),x>2,x∈N^*
\end{cases}$$

image

递归实现

    int fib(int n){
        if (n == 0)
           return 0;
        if (n == 1)
           return 1;
        return fib(n - 1) + fib(n - 2);
    }

假如n=4时,看看递归过程的堆栈情况。

① 调用fib函数,传入参数值4。

image

② fib(4)=fib(3)+fib(2),需要继续调用fib(3),而fib(2)先不进入执行堆栈。

image

③ fib(3)=fib(2)+fib(1),需要继续调用fib(2),fib(1)先不进入执行堆栈。

image

④ fib(2)=fib(1)+fib(0),需要继续调用fib(1),fib(0)先不进入执行堆栈。

image

⑤ fib(1)返回1,停止往下调用,然后上一步的fib(0)进入堆栈。

image

fib(0)返回0,则 ④ 中的fib(2)=fib(1)+fib(0)=1

image image

然后,堆栈回到③中,因为fib(3)=fib(2)+fib(1),所以将fib(1)入栈。

image

fib(1)返回1,则 ③ 中的fib(3)=fib(2)+fib(1)=1+1=2。

image image

然后,堆栈回到 ② 中,因为fib(4)=fib(3)+fib(2),所以将fib(2)入栈。而fib(2)=fib(1)+fib(0),于是将fib(1)入栈。此时fib(1)直接返回1,然后继续将fib(0)入栈。则fib(2)=fib(1)+fib(0)=1,最后fib(4)=fib(3)+fib(2)=3。

image image image image image image

赞(0) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » 看图轻松理解斐波那契数列
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏