通过斐波那契数再谈函数递归2.0

上次我们通过几个简单的例子，认知到递归可以大大的减少代码量，方便使用，这次我们再结合斐波那契数来深入认识一下函数递归。

代码1.0，通过递归实现

#define _CRT_SECURE_NO_WARNINGS
//求第n个斐波那契数（不考虑溢出）
#include<stdio.h>
int fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return (fib(n - 1) + fib(n - 2));
}
int main()
{
	int n = 10;
	int res = fib(n);
	printf("%d ", res);
	return 0;
}

运行结果：

 当我们把n取较大数的时候，能够明显发现程序耗时是很长的，说明递归的效率可能不高，当求第50个斐波那契数时，特别耗费时间，当n过大时，程序可能就会崩溃了，这是为什么呢？是因为在递归调用的过程中，很多数据会被重复计算，我们通过下面的代码来看一下：

这是求n=10的斐波那契数，我们用全局变量count来对此过程中求n=3的斐波那契数进行计数，直观的来看看到底重复计算的次数有多少。

#define _CRT_SECURE_NO_WARNINGS
//求第n个斐波那契数（不考虑溢出）
#include<stdio.h>
int count = 0;
int fib(int n)
{
	if (n == 3)
		count++;
	if (n <= 2)
		return 1;
	else
		return (fib(n - 1) + fib(n - 2));
}
int main()
{
	int n = 10;
	int res = fib(n);
	printf("%d \n", res);
	printf("%d \n", count);
	return 0;
}

运行结果： 

 

我们可以看出，在计算fib(10)的过程中，计算fib(3)的次数为21，这么多的重复计算就造成了程序十分的低效率，所以我们在使用递归的过程中一定要考虑到程序的效率问题，而且当n过大时，也会引起程序的崩溃。

参数过大会引起栈溢出，因为系统分配给程序的栈空间是有限的，但是在递归过程中，不断的开辟新空间，最终产生了栈空间耗尽的情况，造成了栈溢出，程序就会崩溃。

那么由递归引起的低效率问题和栈溢出该如何解决呢？

将递归改为非递归；使用static对象代替nonstatic局部对象。

我们来看看改进后的求斐波那契数的程序，用非递归实现。

#define _CRT_SECURE_NO_WARNINGS
//求第n个斐波那契数（不使用递归）
#include<stdio.h>
int fib(int n)
{
	int result = 1;
	int firstnum;
	int secondnum;
	firstnum = secondnum = 1;
	while (n > 2)
	{
		n -= 1;
		firstnum = secondnum;
		secondnum = result;
		result = firstnum + secondnum;
	}
	return result;
}
int main()
{
	int res = fib(10);
	printf("%d \n", res);
	return 0;
}

运行结果：

 我们通过循环来实现函数，可能会导致代码数量的增加，但是同时也提高了效率。

递归会使复杂的问题变简单，所以许多问题我们是用递归来进行解释的，因为递归比非递归的形式更加清晰，代码的思想一目了然，不过通过其他方法例如循环实现效率往往更高，但是代码的可读性可能会变差，那我们遇到问题时，到底用递归吗？这个时候如果问题过于复杂，难以用循环(迭代)来实现的话，此时递归可以以它的简洁性来补偿它所带来的运行时的开销。