算法 | 【斐波那契数列与递归】

[id_[id_140877368]078486956]

当n趋向于正无穷时，an与an+1的比值趋近于五减去根号下十一分之二的值，这个值等于二分之一减去根号下五分之一

黄金分割和斐波那契序列在数学层面联系紧密，这种模式不仅体现在细微处，比如细胞分裂过程、花朵轮廓分布，也常见于宏观领域，例如人口分布统计、地理空间测量，乃至天体运行轨迹。

斐波那契数列的数学定理和相关公式可以查阅斐波那契数列——百度词条，那里有详细介绍。这个数列的排列规律十分引人注目，任何相邻两个数的和都等于紧随其后的那个数。我们很容易根据这一特性，推导出它的递推公式，即当前项等于前两项之和，用数学符号表示就是an等于an−1加上an−2。并且按照递推公式我们还可以推导出相应的通项公式：

通项公式为an等于十五，an的值等于一除以五的平方根

一个数值的n次方减去另一个数值的n次方,前者是后者的某个倍数

\tag{通项公式}an​=5​1​(通项公式)

下面让我们通过几个示例来了解斐波那契数列的魅力把。

这个数列 1,1,2,3,5,13,21,34,55,…, 被称作 Fibonacci 数列，需要算出它的第n项数值。

同样的，这次先用循环和递归做一遍，然后在想办法进行优化。

#include 
using namespace std;
/*
这个数列叫做 Fibonacci 数列, 它从第一个数开始, 每个数都是前两个数之和, 第一个数是 1, 第二个数也是 1, 接下来的数依次是 2, 3, 5, 13, 21, 34, 55, 计算第 n 个数需要知道前两个数, 然后将它们相加得到结果。
*/
// 循环实现
int Fibonacci(int n)
{
	/*
	1     1     2    5
	a=1 b=1 
			 c=a+b=2
	    a=b    b=c
	分析：
	c 保存两数之和，a、b向后移动
	*/
	int a = 1, b = 1, c = 1;
	for (int i = 3; i <= n; ++i)
	{
		c = a + b;
		a = b;
		b = c;
	}
	return c;
}
// 递归实现
int Fib(int n)
{
	if (n <= 2)	return 1;
	else return Fib(n - 1) + Fib(n-2);
}
int main()
{
	for (int i = 1; i < 10; ++i)
	{
		cout << Fibonacci(i) << " ";
		cout << Fib(i) << endl;
	}
	return 0;
}

分析递归效率：

循环依靠迭代公式来计算，几乎不存在需要改进的环节，假如我们选用通项公式来计算，但目前的递归方法仍有提升的余地。

递归过程解析：比如，要算出第五个斐波那契数，它的递归计算方法是这样的

如图所示：

我们注意到，在求第五个斐波那契数时，需要多次重复求解前四个数的问题，具体来说，求解三次求2问题，两次求1问题，这种重复求解显然是不必要的。从我们的角度来看待这个问题，我们只需要分别计算一次“1”、一次“2”、一次“3”、一次“4”，就可以得到“5”的结果了。而且，我们也确实按照这种方式进行了计算。显而易见，我们借助循环计算斐波那契数列，其方法就是遵循这一思路来完成的。

早先讲过，一般情况下，循环能够转变为递归，那么，我们能否通过略微调整，将循环代码改写成递归形式呢？

循环式分析：

程序中设定了三个存储单元，第一个用于记录前一个数值，第二个用于记录前两个数值开yunapp体育官网入口下载手机版，第三个用于存放两个数值相加的值，随后前两个存储单元的记录分别更新为下一个数值和当前数值。具体步骤请参考表格内容。

112358132134

递归算法设计：

这个数列的每个数字，都是前两个数字之和，要推算出某个数字，可以依次往前推算，直到推算到较小的数字，例如要推算34，就先推算21，再推算13，然后推算5，接着推算3，最后推算2。

解析：若将此序列视作数据集合，那么递归就好比逆向遍历该集合进行计算，而循环则是顺序遍历该集合进行运算。并且，在整个运算期间，都会完整地经历一遍该集合的元素，递归的调用频次与循环的遍历频次相等。

计算方法：每执行一次递归都同步完成运算，从斐波那契序列的初始值 1,1 算起，直到递归过程终止时，即可得到最终结果，而且此方法不会产生重复计算的情况。

递归调用形式为fib(n,a,b) 变为fib(n−1,b,a+b)fib(n,a,b) 转为fib(n−1,b,a+b) ,在调用期间，n代表递归的轮数，a的存储单元存放b的数值，b的存储单元存放c的数值（a+b的结果）

递归过程分析：求第9个斐波那契数

计算过程依次为：先算出9基于1和1的结果，得到8基于1和2的值，再算出7基于2和3的值，接着算出6基于3和5的值，然后算出5基于5和8的值，再算出4基于8和13的值，然后算出3基于13和21的值，最后算出2基于21和34的值

数值序列如下，各项依次为，第一项等于一，第二项等于一，第三项等于二，第四项等于三，第五项等于五，第六项等于八，第七项等于十三，第八项等于二十一，第九项等于三十四

所以，针对递归式fib(n,a,b)fib(n,a,b)fib(n,a,b)的递归结束情形也明确了。当n等于2n=2n=2时输出b开yun体育app入口登录，或者当n等于1n=1n=1时输出a都行，以下是C++的代码实现方式：

#include 
using namespace std;
/*
题目：无穷数列 1,1,2,3,5,13,21,34,55,..., 称为 Fibonacci 数列，计算第n位数列。
*/
int Fib_Reverse(int n, int a, int b)
{
	if (n <= 2) return b;
	else return Fib_Reverse(n - 1, b, a + b);
}
int NiceFib(int n)
{
	int a = 1, b = 1;
	return Fib_Reverse(n, a, b);
}
int main()
{
	for (int i = 1; i < 10; ++i)
	{
		cout << NiceFib(i) << " ";
	}
	cout << endl;
	return 0;
}

除了直接计算斐波那契数列之外，还有许多相关联的课题。例如：求解杨辉三角形的数值、探讨登楼梯的方案、研究兔子繁衍的规律、分析青蛙跃过阶梯的路径等等。此外，卢卡斯数列 1、3、4、7、11、18…，同样展现出斐波那契数列的相似特性。值得注意的是开元ky888棋牌官方版，在当代物理学、准晶体构造、化学分析等学科中，斐波那契数列能够直接发挥作用。感兴趣的同学可以自行在网上查找相关资料。

倘若我的文字能为你提供些许益处，恳请你动动手指给予支持，这份认可将是我不断进步的源泉。倘若文中存在疏漏之处，敬请不吝赐教，若有相左之见，也欢迎在互动区域分享高见，彼此砥砺前行。

——学习路上，你我共勉