C语言（递归）

                        Hi~！这里是奋斗的小羊，很荣幸各位能阅读我的文章，诚请评论指点，关注+收藏，欢迎欢迎~~

                        💥个人主页：小羊在奋斗

                        💥所属专栏：C语言

本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为同样是初学者的学友展示一些我的学习过程及心得。文笔、排版拙劣，望见谅。

一、递归

1、什么是递归

2、递归的限制条件

3、递归的举例

4、递归与迭代

1、什么是递归

递归是C语言学习绕不开的一个话题，那什么是递归呢？递归其实是一种解决问题的方法，在C语言中，递归就是函数自己调用自己。若一个复杂的问题，能层层分解为若干个相对简单且与原问题相似的子问题，则原问题可以采用递归算法求解，所以递归的思想就是把大事化小的过程。

递归中的递是递推的意思，归是回归的意思。

来看一个简单的递归示例：

但是上述代码会陷入死递归，因为递归需要一个限制条件，不然会一直向内存申请空间但不释放，导致栈溢出（Stack overflow）。VS调试技巧中也提到过栈溢出，但这里也不细说，因为内容太多，后面会有专门的文章。

2、递归的限制条件

递归在书写的时候，有2个必要的限制条件：

（1）递归存在限制条件，也就是出口，当满足这个限制条件的时候，递归不再继续；

（2）每次递归调用后越来越接近这个限制条件。

这么说可能有些生硬，不过在看完了这篇文章后相信你会对这两句话有所体会。

3、递归的举例

3.1求n的阶乘（不考虑溢出）

我们知道，0和1的阶乘为1，n的阶乘是所有小于及等于n的正整数的积。

比如：4！= 4*3*2*1, 3！= 3*2*1，那么4！= 4*3！，即n！= n（n - 1）！。这样的思路就是把一个较大的问题，转换为一个与原问题相似，但规模较小的问题来解决。当n一直减到n = 1的时候，n的阶乘为1，这是我们本来就知道的。到这里，我们就得到了求n的阶乘的公式：

函数实现如下：

#include <stdio.h>

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

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

运行结果（这里不考虑n太大的情况，会溢出）：

图形演示：

3.2输入一个整数顺序打印每一位

我们拿到这个题目后，很容易想到把这个数的每一位单独拿出来再打印，但问题是，怎么拿到一个数的每一位呢？有一个熟知的方法就是通过模10（%10）和除10（/10）不断循环来取得一个数的每一位，但是这个办法取出来的是逆序的，我们这里需要的是顺序的，很明显我们常用的这个方法行不通。

虽然这个方法行不通，但是它给了我们一个灵感，我们发现一个数的最低位是很容易得到的，因此我们可以这样想：如果想要按顺序打印1234的每一位，我们可以先打印123，再打印4；打印123之前先打印12，再打印3；打印12之前先打印1，再打印2。这样不就实现我们想要的效果了嘛。

不难发现，上面解决问题的思路用递归很容易解决，既然有了思路，废话不多说，我们直接上代码演示：

#include <stdio.h>

void print(int m)
{
	if (m > 9)
	{
		print(m / 10);
	}
	printf("%d ", m % 10);
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	print(n);
	return 0;
}

是不是看起来很简单，运行结果为：

如果不太明白执行逻辑，不要慌，我直接上图细细演化每一步的执行过程：

4、递归与迭代

递归是一种很好的编程技巧，但是和很多技巧一样，也是可能会被误用的。就像3.1一样，看到推导的公式，很容易就被写成递归的形式：

Fact（）函数是可以得出正确的结果，但是在函数递归的时候存在一些运行时的开销。

在C语言中每一次函数调用，都需要为本次函数调用在栈区申请一块内存空间来保存函数调用期间的各种局部变量的值，这块空间被称为运行时栈帧，或者函数栈帧。只要函数不返回，函数对用的栈帧空间就一直被占用，所以如果函数调用中存在递归调用的话，每一次递归函数调用都会开辟属于自己的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间。

所以如果采用函数递归的方式完成代码，递归层次太深，就会浪费太多的栈帧空间，也可能引起溢出。

为了避免这些问题，就得想其他的办法，通常就是用迭代的方法来代替递归。我们学过的循环就是一种迭代。比如上面的计算n的阶乘问题，我们也可以用循环的方法来解决：