斐波那契数列(递归与非递归)

　

斐波那契数列

首先来说下递归，递归的思想是大事化小。

斐波那契数列：1,1,2,3,5,8,13,21........

设f(n)是第n个斐波那契数，

当n<=2,斐波那契数都为1；

当n>2,那么第f(n)个斐波那契数就等于前两个斐波那契数之和。

递归的代码实现：

#include<stdio.h>
int fbnq(int n)
{
	if (n <= 2)
		return 1;//n=1,2   返还1;
	else
		return fbnq(n - 1) + fbnq(n - 2);//n>2   返还前两个数之和
}
int main()
{ 
	int n = 0;
	scanf_s("%d", &n);
	int ret = fbnq(n);
	printf("%d\n", ret);
	return 0;
}

输入10，得到下图：

得到第十个斐波那契数的同时，问题也来了，当输入很大的数时

比如40，可以得到结果，但是计算所花时间比较长，大概需要10秒左右，当输入更大的数计算时间更长。

为什么会需要这么长的时间呢？

看代码，我们设置一个全局变量来统计一下，当要打印第40个斐波那契数时，第5个斐波那契数要计算多少次。

#include<stdio.h>
int count = 0;//全局变量
int fbnq(int n)
{
	if (n == 5)
		count++;
	if (n <= 2)
		return 1;//n=1,2   返还1;
	else
		return fbnq(n - 1) + fbnq(n - 2);//n>2   返还前两个数之和
}
int main()
{ 
	int n = 0;
	scanf_s("%d", &n);
	int ret = fbnq(n);
	printf("第%d个斐波那契数为%d\n",n, ret);
	printf("第5个斐波那契数计算%d次\n", count);
	return 0;
}

打印第40个斐波那契数，第5个计算了很多次，这种代码效率太低。

这是完全可以用非递归来解决这种代码效率低下的情况；

非递归代码实现：

#include<stdio.h>
int fbnq(int n)
{
	int a = 1;
	int b = 1;
	int c = a;
	while (n > 2)
	{
		c = a + b;//从第三个数开始，斐波那契数等于前两个数的和；
		a = b;//将前一个数给到a，开始下一次求值
		b = c;//将斐波那契数给b，开始下一次求值
		n--;//每求一次，n都要减一
	}
	return c;
}
int main()
{ 
	int n = 0;
	scanf_s("%d", &n);
	int ret = fbnq(n);
	printf("第%d个斐波那契数为%d\n",n, ret);
	return 0;
}

同样输入40，这次输出结果直接就打印出来了；

同样的结果在不考虑溢出的情况下，非递归的计算速度明显快很多，但是递归的代码可读性较强，它比非递归的形式更加清晰。

所以，不同的情况采取的方式自然不同，这就让我们在以后写程序时更好的达到自己理想的效果。

相关阅读

js 递归调用

程序员不止眼前的逻辑和代码，还有底层的框架与架构。 1. 前言 最近在做一个复杂表格设计数据格式设置，其中用到了多叉树的原

数据库：sql递归查询

mysql 自关联表，以下为向下递归以及向上递归样例。 1 递归查询前期准备，如果你的表已经存在，可忽略此步。 建表 CREATE TABLE `wq_a

3L, 5L, 8L三个水桶等分8L水 Java(递归, 穷举)

题目 有三个容积分别是8升、5升和3升的水桶，其中容积为8升的水桶中有8升水，其它两个水桶是空的。三个水桶都没有刻度，问如何在不借

递归算法（转）

转自：https://blog.csdn.net/feizaosyuacm/article/details/54919389目录： 1.简单递归定义 2.递归与循环的区别与联系 3.递归的

mysql递归查询

父子查询： 根据父 id 查询下面所有子节点数据；子父查询： 根据子 id 查询上面所有父节点数据；