斐波那契数列

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

一、定义

斐波那契数列（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\n", 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……或者更大的数字时，重复计算的项目和次数也会变得更多，所以我们考虑使用其他的方法来实现斐波那契数列。

三、循环实现斐波那契数列

循环实现代码：

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

结果：

输入5，输出5。

输入40，输出102334155。

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

分析：
当我们用循环来实现斐波那契数列时，代码运行速度变得很快，只需要几秒。

四、 学习递归算法的体会

在我学习函数递归的时候，了解到递归有一个要素：提取重复的逻辑，缩小问题规模。我下意识的认为问题规模缩小了，代码的运行速度也会变快，但实际上不是这样，递归算法的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理，比如参数传递需要压栈等操作，会对执行效率有一定影响。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！