C语言——函数基本知识（三）

        上篇文章我们介绍了函数递归的使用，接下来我们再来讲解一些有关递归的习题。

一. 求n的阶乘

        阶乘是指：n*(n-1)*(n-2)*······*2*1。

        首先我们可以先利用循环实现上面的代码。

代码如下：

​
int main()
{
	int n=0;
	int a;
	int j=1;
	scanf("%d", &n);
	for (a = 1; a <= n; a++)
	{
		j *= a;
	}
	printf("%d", j);

	return 0;
}

​

        这是求阶乘比较简单的代码，但是当我们输入各种数据的时候，我们发现当输入20的时候，结果就不对了，

        出现错误原因很简单，这种叫做阶乘溢出，因为阶乘 j 的类型是int型，而20的阶乘超过了int类型所存储的最大范围，导致阶乘溢出。

        我们可以将上面的代码进行优化。

优化代码如下：

int main()
{
	int n=0;
	int a;
	long long j=1;
	scanf("%d", &n);
	for (a = 1; a <= n; a++)
	{
		j *= a;
	}
	printf("%lld", j);

	return 0;
}

将 j 的类型变成长整型，可以避免阶乘溢出，注意当用printf的时候用“%lld”

接下来我们用函数递归实现n的阶乘。

递归代码如下：

int fac(int x)
{
	if (x >= 1)
	{
		x *= fac(x - 1);
	}
	else
		return 1;
}
int main()
{
	int n;
	scanf("%d", &n);
	int a = fac(n);
	printf("%d", a); 
	return 0;
}

运行结果如下：

二. 求第n个斐波那契数

        斐波那契数列（Fibonacci sequence），又称黄金分割数列 [1]，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为：1、1、2、3、5、8、13、21、34……在数学上，这一数列以如下递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

普通代码如下：

int fib(int x)
{
	if (x <=2)
		return 1;
	else
		return x = fib(x - 1) + fib(x - 2);
}
int main()
{
	int a;
	scanf("%d", &a);
	int f = fib(a);
	printf("%d", f);
}

但是我们发现有问题：

        在使用 fib 这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。 使用 factorial 函数求10000的阶乘（不考虑结果的正确性），程序会崩溃。

        为什么呢？

        我们发现 fib 函数在调用的过程中很多计算其实在一直重复。

        那么如何改进呢？？？

        1. 将递归改写成非递归。

        2. 使用static对象替代 nonstatic 局部对象。在递归函数设计中，可以使用 static 对象替代 nonstatic 局部对象（即栈对象），这不仅可以减少每次递归调用和返回时产生和释放 nonstatic 对象的开销，而且 static 对象还可以保 存递归调用的中间状态，并且可为 各个调用层所访问。  

        比如，下面代码就采用了非递归的方式

优化代码如下：

int fib(int n)
{
	int result;
	int pre_result;
	int next_older_result;
	result = pre_result = 1;
		while (n > 2)
		{
			n -= 1;
			next_older_result = pre_result;
			pre_result = result;
			//将result值给前一个pre_result，把pre_result的值赋给result前面第二个next_older_result
			result = pre_result + next_older_result;
		}
	return result;
}
int main()
{
	int a;
	scanf("%d", &a);
	int f = fib(a);
	printf("%d", f);
}

        提示：

         1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。

         2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。

        3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。

        本节函数基本知识（三）就介绍到这里，之后会更新《函数栈帧的创建与销毁》《函数递归经典题型——汉诺塔问题》《函数递归经典题型——青蛙跳台问题》。

        往期回顾：

C语言 ——函数基本知识（一）-CSDN博客

C语言——函数基本知识（二）-CSDN博客

“山林不向四季起誓，荣枯随缘”——C语言（爱心+祝福语）代码分享_爱心代码朋友圈文案-CSDN博客

C语言——二分法查找讲解_c语言二分法查找一个数-CSDN博客

C语言穷举法算法经典题型（一）_c语言穷举法经典例题-CSDN博客

C语言穷举法算法经典题型（二）_百钱百鸡问题c语言-CSDN博客

C语言算法经典基础题型——求一个数的回文数（两种方法）-CSDN博客

C语言基础入门（小白）三种方法解决幽灵换行符问题-CSDN博客