斐波那契数列的两种方法（递归和循环） 黄金分割数怎么求

斐波那契数列 一、定义二、递归实现斐波那契数列三、循环实现斐波那契数列四、 学习递归算法的体会

一、定义

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1，F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

二、递归实现斐波那契数列

递归实现代码：

#define _CRT_SECURE_NO_WARNINGS#include int fib(int n){if (n == 1){return 1;}if (n == 2){return 1;}return fib(n - 1) + fib(n - 2);}int main(){int n = 0;printf("请输入要求第几个数字：");scanf("%d", &n);printf("%d ", fib(n));system("pause");return 0;}

结果：

输入5，输出5。

输入40，输出102334155。

输入50，输出-298632863。 这里输出负数的原因是，fib(50)是一个很大的数字，int根本就表示不下来。

分析： 如果我们自己运行代码尝试，可以知道： 输入5时，计算速度还是很快的，输入40时，计算也只需几秒，而输入50，计算则花费了6-7分钟（和电脑cpu有关）。 所以我们思考一下使用递归实现斐波那契数列是否存在一些问题？

我们以输入5为例子。

可以看出其中fib(3)，fib(2)，fib(1)被重复计算了很多次。当输入40，50……或者更大的数字时，重复计算的项目和次数也会变得