C语言——函数递归

一.什么是递归？

递归是一种解决问题的方法，在C语言中，递归就是函数自己调用自己。

具体来讲，函数递归是将一个问题分解为更小的、类似的子问题来解决问题。

二、函数递归的优缺点

优点：

1.代码简化：

递归能够将复杂问题分解成更小、更简单的子问题，使得代码逻辑更加清晰和简洁。例如，树结构遍历，阶乘计算勇递归实现比迭代更为直观

2.问题分解：

递归天然适合分治策略，将复杂问题分解为更小的子问题，简化解决过程。例如，归并排序，快速排序等算法。

3.数学表达：

递归与数学归纳法类似，适合处理有递归定义的数学问题，例如斐波那契数列。

缺点：

1.性能问题：

递归可能导致多次重复计算，效率较低，且每次调用都会增加栈开销，可能引发栈溢出（Stack overflow）。

2.调试难度：

递归调用层级较深时，调试和理解代码的执行流程较为复杂。

3.重复计算：

某些递归算法（例如斐波那契数列）会重复计算相同的子问题，效率低下。

三.递归的限制条件

递归书写的时候要满足两个必要条件：

1.递归存在限制条件，当满⾜这个限制条件的时候，递归便不再继续。

2.每次递归调⽤之后越来越接近这个限制条件。

四.函数递归举例分析

1.栈溢出举例

上述是一个简单的递归程序，不过是一个错误的示范，代码最终会陷⼊死递归，导致栈溢出。

原因分析：函数递归栈溢出的原因是递归深度过大，或者没有正确的递归终止条件，导致递归函数无法停止调用，不断地将新的函数压入栈中，最终导致栈空间耗尽。以上述代码为例，每调用一次main函数都会向内存中的栈区申请一块空间，而栈区的空间是有限的（见下图），当栈空间耗尽时，程序就会因为无法继续压入新的栈帧而抛出“栈溢出”异常。

2.求阶乘

题⽬：计算n的阶乘n!（不考虑溢出），n的阶乘就是1~n的数字累积相乘

题目分析：

n! = n * (n-1)!

我们可以举例分析一下它的特征：

5! = 5*4*3*2*1

4! = 4*3*2*1

所以:5! = 5*4!

有上面我们可以分析将n!这个大问题转化为与原问题相似，但规模较小的问题来求解。

当n==0时，n的阶乘是1，n的阶乘递归公式如下：

代码实现：

int fact(int n)
{
	if (n == 0)
		return 1;
	else
		return fact(n - 1) * n;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int c=fact(n);
	printf("%d", c);

	return 0;
}

画图推演：

如果在程序开始时我们输入的值是5，那么在fact函数中，由于5*fact（4）中fact（4）未知，所以无法返回，还会调用fact函数，而在栈区中会分配空间让5*fact（4）暂存，逐步递推，一直到fact（0）满足了递归中的限制条件，会从fact（1）开始计算，当fact（1）计算结束后，栈区为1*fact（0）分配的空间会被销毁，以此类推，一直到fact（5）得到结果，逐步回归。

3.顺序打印一个整数的每一位

题目：输⼊⼀个整数m，按照顺序打印整数的每⼀位。

例：

题目分析：

和上一个例题的大致思路相同，首先我们要分析问题，通过分析可以得出这个问题既可以用函数递归的方法，还可以用迭代的方法（注：循环属于迭代，但迭代并不是循环，比如用goto语句也可以进行迭代），我们这里用递归的方法。

通过分析，我们可以想到用取模和取余的方法，1234%10就能得到4，然后1234/10得到123，这就相当于去掉了4 然后继续对123%10，就得到了3，再除10去掉3，以此类推不断的 %10 和 /10 操作，直到1234的每⼀位都得到，但是这⾥有个问题就是得到的数字顺序是倒着的，经过脱离，我们可以得到如下代码。

代码实现：

Print(int n)
{
	if (n > 9)       //限制条件
	{
		Print(n / 10);
	}
	printf("%d ",n%10);
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	Print(n);

	return 0;
}

画图推演：

4.斐波那契数列（递归或迭代实现）

斐波那契数：斐波那契数列的第1项是1，第2项也是1。从第3项开始，每一项都等于前两项之和。

题目： 计算斐波那契数递归实现求第n个斐波那契数 例如： 输入：5 输出：5 输入：10， 输出：55 输入：2， 输出：1

（1）递归实现

题目分析：

斐波那系数是前两项加起来等于后一项：1，1，2，3，5，8，13…,所以我们可以以n<=2为限制条件，当n=1或2时，返回1，到n=3项时就是n=1项和n=2项之和，依次往后推，即Fib(n)=Fib(n-1)和Fib(n-2)之和

代码实现：

int Fib(int n)
{
	if (n > 2)    //限制条件
		return Fib(n - 1) + Fib(n - 2);
	else
		return 1;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int c=Fib(n);
	printf("%d\n", c);
	return 0;
}

画图推演：

虽然用这种方法也可以进行计算，但是当我们想要计算一个稍微大点的数是，我们会发现，计算机响应的时间特别的长，这是因为，用递归的方法进行计算时，会有过多相同的值的重复计算，而且递归的层次越深，冗余计算就会越多，大大降低了计算效率。这也体现出了递归算法的弊端，所以并不是所有的方法都适合用函数递归。

（2）非递归实现

题目分析：

也可以参考上面递归实现的思路，我们可以用三个变量相互替换来解决，a为第一项，b为第二项，c为第三项，运用while()循环，每一次循环n就减1，直到n=2，最后输出c。

代码实现：

#include<stdio.h>
int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n >= 3)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d\n", ret);
	return 0;
}

改进之后运行发现用非递归的方式效率明显高于递归的方式，原因是：

避免了重复计算：递归方式在计算斐波那契数时存在着大量的重复计算，每次递归都会重复计算前面已经计算过的子问题。而非递归方式通过迭代的方式，从前往后按顺序计算每一项，避免了重复计算，提高了效率。

减少函数调用开销：递归方式需要频繁地进行函数调用，每次调用都需要保存现场、传递参数等操作，会产生额外的开销。而非递归方式只需要使用循环来进行迭代计算，减少了函数调用的开销，提高了效率。

节省内存空间：递归方式在递归过程中需要维护函数调用栈，消耗了额外的内存空间。而非递归方式只需要使用有限的变量来保存中间结果，不需要额外的栈空间，节省了内存空间。