递归和非递归分别实现求第n个斐波那契数
运行环境 win10 vs2013
首先我们需要知道什么是菲波那切数列
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
想要输出斐波那契数列只需要找到其中的规律即可, 简单来说 从第三项起 前面两个数相加的和等于第三个数,所以我们在写程序是只需要直接输出前两项 1,1然后利用递归函数直接来计算后面的值,由于使用递归函数基数数量级过大所耗费的时间也就越多,所以我们假设只输出第八项的数值
程序如下:
运行结果如图
#include<stdio.h>
#include<stdlib.h>
//求第n项斐波那契数列
int Lib(int n){
if (n == 1 || n == 2){
return 1;
}
return Lib(n - 1) + Lib(n - 2);
}
int main(){
printf("%d\n",Lib(8));
system("pause");
return 0;
}
为了体现用递归函数计算数量级过大时间耗费多,可以尝试求第100项
运行结果
看似什么都没有,其实计算机正在快速运算,
如果不使用递归函数也可快速求值,在计算出某一项是将其保存,在计算后面的项时直接使用,避免多次计算,将极大的减少运算时间
接下来我们不采用递归计算第100项
运行结果