大家好，很高兴又和大家见面啦！经过前面几个篇章的学习，我相信大家对函数的基本知识点都已经掌握的差不多了，接下来我们将要开始探讨函数递归的相关内容了。
七、函数递归
1.什么是递归
定义
程序调用自身的编程技巧称为递归。
递归作为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需要少量的程序就可以描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递归的主要思考方式在于：大事化小
理解
对于函数递归我的理解是一种特殊的函数嵌套。在上一篇我们介绍了函数的嵌套使用，一个函数在自己的函数体中调用其它函数，这就是函数嵌套，函数递归类似于函数嵌套，也是一个函数在函数体中调用函数，这不过这一次调用的函数是自己，这种嵌套方式也就相当于数学中的复合函数f(f(x))。
最简单的递归
为了方便理解，我们来举一个最简单的函数递归：
//函数递归
//最简单的函数递归
int main()//int——返回类型；main——函数名
{
printf("hello\n");//函数体——函数的实现；
main();//调用函数，函数为自己本身——函数递归；
return 0;//return 0——函数返回值；
}这样能不能运行呢，我们可以看一下：
可以看到我们这个程序是可以正常运行的，而且还会陷入死循环，但是它和死循环又不同，我们可以看到，它循环到一定阶段就终止了。为什么会这样呢？这里我们要拓展一个知识点——内存
内存
计算机的内存就好比与一个空间，它里面有三个分区，分别是栈区、堆区和静态区。
- 栈区里存放的是局部变量以及函数的形参；
- 堆区里存放的是动态开辟的内存，如malloc、calloc这样的函数所开辟的空间都是在堆区内开辟的；
- 静态区存放的是全局变量以及由static修饰的变量。
正如我们从上图中看到的，既然内存是一个空间，那它肯定是有一定大小的，更不用说这三个小空间了，它们也是有一定容量大小的。我们在调用函数的时候，就相当于在各自对应的小空间里继续申请空间，来存放函数的相关内容。
在这个最简单的函数递归中，计算机会不停的重复一件事，就是在栈区为printf以及main函数申请空间来进行操作，每次调用main函数就会申请一块空间，每次调用printf也会申请一块空间，当程序执行的足够多时，栈区的空间就被全部申请完了，此时就没法继续申请空间来运行程序了，这种情况也被称为栈溢出。这也就是为什么这种递归方式会使计算机陷入死循环，但又会有一个停止点。
习题
在了解完什么是递归后，我们来做一道题来进一步加深对函数递归的理解：
接收一个整型值（无符号），按照顺序打印它的每一位，如：1234，我需要按顺序打印1 2 3 4。
在编写之前，我们先分析一下这道题：
- 首先，题目要求接收一个整型值，那我们可以想到的就是通过scanf或者getchar来进行接收；
- 其次，无符号的意思就是这个整型值要是unsigned类型；
- 再来，题目要求将这个整型值打印出来，所以我们可以想到的是通过printf或者getchar来进行输出；
- 最后，它要按照顺序打印数值的每一位，那根据我们所学的内容，如果要将这每一位都打印出来，我们是不是可以通过操作符“/”和“%”来完成。
好思路有了，我们开始来编写我们的代码：
int main()
{
unsigned int a = 0;//定义无符号整型局部变量a来存储接收到的整型值；
scanf("%d", &a);//通过scanf函数来将1234传送给变量a；
printf("%d\n", a / 1000);//通过除号，我们将1给取出来进行打印；
unsigned int b = a % 1000;//通过取模，我们将234给取出来存放进无符号整型局部变量b中；
printf("%d\n", b / 100);//通过除号，我们将2给取出来进行打印；
unsigned int c = b % 100;//通过取模，我们将34给取出来存放进无符号整型局部变量c中进行打印；
printf("%d\n", c / 10);//通过除号，我们将3给取出来进行打印；
unsigned int d = c % 10;//通过取模，我们将4给取出来存放进无符号整型局部变量d中进行打印；
printf("%d\n", d);//我们将4给直接打印出来；
return 0;
}
大家可以通过测试结果看到像这样编写代码，我们就能顺利的往常题目的要求，但是我们会在编写的过程中发现，其实我们的函数体中一直在重复一个两个操作，相除取整，和相模取余，不同的是我们相除的数值是不一样的由1000-100-10-1，我们现在思考一个问题，我们可不可以通过递归来完成这个任务呢？下面我们继续分析：
（1）由递归的定义可知，它是函数在自己的函数体内调用自己，那肯定是满足结构：
//函数递归的结构
返回类型 函数名(函数参数)
{
函数名(函数参数);
}
//例如
int A(int a)
{
A(b);
}（2）函数体内要实现相除、相模与打印三个内容：
//函数的实现
a / ? ;
a% ? ;
printf("%d", );（3）递归是通过将一个比较复杂的内容转换成多次重复的比较简单的小内容来实现函数，那肯定需要有一个循环来实现：
//多次重复实现 while () {}
for (;;)
{}
do
{
} while;
在这个三个循环中选取一个即可；
（4）既然要能重复，那说明执行的语句是可以反复执行的，如果按我们之前编写的来做的话肯定不行，那我们就要开始寻找这四次之间的联系第一次/1000相当于/10^3，第二次就是/10^2，第三次就是/10^1，第四次就是/10^0，但是这里我们要注意，在C语言中"^"这个符号可不是次方的意思，而是按位异或，如果我们要使用次方的话，我们需要使用数学函数pow，这里我们尝试编写代码：
void print(unsigned int x)
{
//for (y = 3; y >= 0; y--)
//{
// n = pow(z, y);
// printf("%d\n", n);
//}
if (x>9)
{
int y = 3, z = 10, n;
n = pow(z, y);
y--;
printf("%d ", x / n);
print(x % n);
}
}
int main()
{
unsigned int a = 0;
scanf("%d", &a);
print(a);
return 0;
}
通过我自己在测试的过程中，我发现在函数使用递归时，函数就已经进入了循环，不需要额外使用循环语句，所以我尝试着修改了一下，既然它自己能够循环的话，那我们来看看结果如何；
我们可以看到，在第一层函数走完，进入第二层函数时，屏幕上打印出了1，x也如我们所想，变成了234，继续运行：
这时我们发现出问题了，屏幕上打印的是0，并且此时x的值还是234，为什么会这样呢？细心的朋友会发现，此时的y和n与进入第二层函数时的y和n一模一样，我们再仔细的观察一下函数体，会发现，每次进入print函数时，在进入if语句后，函数都会先给y进行赋值，问题就出现在这里，下面我们对代码进行一下调整：
void print(unsigned int x,int y)
{
//for (y = 3; y >= 0; y--)
//{
// n = pow(z, y);
// printf("%d\n", n);
//}
if (x>9)
{
int z = 10, n;
n = pow(z, y);
y--;
printf("%d ", x / n);
print(x % n, y);
}
}
int main()
{
unsigned int a = 0;
int b = 3;
scanf("%d", &a);
print(a, b);
return 0;
}
现在我们来运行一下看看结果：
此时我们发现，成功打印了1/2/3，为什么4没有打印呢？我们分析一下代码，既然没有打印，那就说明此时函数没有进入if语句，当x=4时，不满足条件，函数就结束了，那我们再修改一下代码：
//接收一个整型值（无符号），按照顺序打印它的每一位
//如：1234，我需要按顺序打印1 2 3 4void print(unsigned int x,int y)
{
//for (y = 3; y >= 0; y--)
//{
// n = pow(z, y);
// printf("%d\n", n);
//}
if (x>0)
{
int z = 10, n;
n = pow(z, y);
y--;
printf("%d ", x / n);
print(x % n, y);
}
}
int main()
{
unsigned int a = 0;
int b = 3;
scanf("%d", &a);
print(a, b);
return 0;
}
现在可以看到，此时程序很好的完成了题目要求。
2.递归的两个必要条件
通过这一题，我们可以给使用递归总结一下：
（1）使用递归时，需要附加限制条件，防止代码进入死循环导致栈溢出；
（2）每次递归调用之后，应该越来越接近这个限制条件；
对于递归来说，这两点也就是递归在使用时的两个必要条件，只有这两个必要条件同时满足，函数才能正常递归。
接下来我们在知道递归的必要条件后，尝试着将这一题再优化一下。我们先思考一个问题，刚刚我们是从前往后取，我们能不能通过从后往前取得方式来进行递归呢？如果从后往前取得话那就是先取4，再取3，再取2，再取1，有了前面的经验，现在我们来直接编写：
//接收一个整型值（无符号），按照顺序打印它的每一位
//如：1234，我需要按顺序打印1 2 3 4
void print(unsigned int x)
{
if (x > 9)
{
print(x / 10);
}
printf("%d ", x % 10);
}
int main()
{
unsigned int a = 0;
scanf("%d", &a);
print(a);
return 0;
}
这么一看，确实比之前简洁了很多，但是这样操作的话，结果会是从1开始打印吗？
这里我们可以看到，确实是从1开始打印，但是为什么呢？下面我们来通过图示理解一下：
通过流程图我们可以看到，此时递归的逻辑是先递归执行函数，直到不满足限制条件为止，再开始从最后一次递归函数依次向前进行打印，直到回到最初的函数，最后进入主函数结束运行。从数字上来理解，就是先从4开始依次往前取到1，再由1开始依次打印到4。从这里我们可以得到结论：
（1）执行语句在递归条件判断函数体内，则跟着递归函数一同顺序执行；
（2）执行语句不在递归条件判断函数体外，则从递归停止后开始由内到外依次逆序执行。
结语
以上就是递归的第一部分内容——什么是递归以及递归的两个必要条件，希望这篇内容能帮助大家更好的理解函数递归。接下来随着学习的深入，我会继续给大家分享我在学习过程中的感受，感谢大家的翻阅，咱们下一篇
