关于递归斐波那契数列的效率问题。

常规的递归求斐波那契数列的代码为：时间复杂度为O(2^n).

int FiBo_Recursion(int n)//递归求   时间复杂度O(n^2)
{
	if (n == 1 || n == 2)
	{
		return 1;
	}
	else return FiBo_Recursion(n - 1) + FiBo_Recursion(n - 2);
}

其时间复杂度高的原因是因为做了大量的重复的计算。

如图（求第十位斐波那契数的时候的递归过程）：PS：省略部分。

可见普通求斐波那契数列的效率是非常的低效。这里我们可以利用已经求到的数值来对上面的树进行剪枝，达到提升效率的目的。

如图所示：

求第n个斐波那契数，只需要知道第n-1个斐波那契数和第n-2个斐波那契数即可。无需进行重复的求解。

代码：时间复杂度为O(n)

int FastFiBo(int n)
{
	static int LLastRes	= 0;//保存上上一层的结果
	int res				= 0;//这一层得出的结果
	if (n == 1 || n == 2)
	{
		LLastRes = 1;
		return 1;
	}
	int LastRes = FastFiBo(n - 1);
	res = LastRes + LLastRes;//本层结果等于上一层结果加上上一层结果  即 n = (n-1) + (n-2);
	LLastRes = LastRes;//更新上上层的结果
	return res;
}

 可以根据进入函数的次数比较俩次的结果。

int total1 = 0;//保存优化后的进入函数的次数
int total2 = 0;//保存优化前的进入函数的次数
int FastFiBo(int n)
{
	total1++;
	static int LLastRes	= 0;//保存上上一层的结果
	int res				= 0;//这一层得出的结果
	if (n == 1 || n == 2)
	{
		LLastRes = 1;
		return 1;
	}
	int LastRes = FastFiBo(n - 1);
	res = LastRes + LLastRes;//本层结果等于上一层结果加上上一层结果  即 n = (n-1) + (n-2);
	LLastRes = LastRes;//更新上上层的结果
	return res;
}
int FiBo(int n)
{
	total2++;
	if (n == 1 || n == 2)
	{
		return 1;
	}
	else return FiBo(n - 1) + FiBo(n - 2);
}

void main()
{

	int a = FastFiBo(10);
	int b = FiBo(10);
}

结果：

结论：

优化过后的代码大大提高了求斐波那契数的效率。