本篇博客会讲解如何使用C语言实现递归，以及2个注意事项。
递归是什么
递归，简单来说，就是自己调用自己。C语言中，可以使用函数来实现递归，也就是让一个函数自己调用自己。举一个简单的例子：
请你求斐波那契数量的第n项。所谓斐波那契数列，即前2项是1，从第3项开始，每一项都是前2项的和。也就是：1 1 2 3 5 8 13 21 34 55…
分析一下：假设有一个函数int Fib(int n);，当n <= 2时，函数返回1，否则返回Fib(n-1) + Fib(n-2)，这就是自己调用自己的最直观、最简单的例子了。
int Fib(int n)
{
if (n <= 2)
return 1;
else
return Fib(n-1) + Fib(n-2);
}
如何实现递归
实现递归，需要有“大事化小小事化了”的思路。举个例子：请使用递归打印一个整数的每一位。假设这个函数是void Print(int n);，当n为1234时，会打印1 2 3 4。
打印n是一个“大事”，我们可以把它拆分成“小事”。显然，最后一位是最容易打印的，也就是说，1234中的4是最容易打印的，直接1234%10即可，那问题就转换成了先打印123的每一位，再打印4。而123=1234/10。
经过我们的分析，打印n其实就2步：
- 打印n/10的每一位。
- 打印n%10。
如果你这么想，那你还忽略了一点：如果是一位数，比如3，就不需要第一步了，直接进行第二步。换句话说，只有2位数以上才需要第一步。代码实现如下：
void Print(int n)
{
if (n >= 10)
Print(n / 10);
printf("%d ", n%10);
}
当我们调用Print(1234)时，输出结果如下：
递归的调用逻辑
递归是自己调用自己的。我们还是用“打印一个整数的每一位”为例。假设Print(1234);，会发生什么呢？
首先会调用一次Print函数，Print函数再调用Print函数：
Print函数再调用Print函数：
Print函数再调用Print函数：
总算不用继续调用了。此时打印1，返回到上一层：
打印2，返回上一层：
打印3，返回上一层：
最后打印4，返回。
以上就是整体调用的逻辑。红色的线表示继续调用新的Print函数，即“递推”；紫色的线代表返回到上一层，即“回归”。“递推”和“回归”合称“递归”。
递归的注意事项
函数调用是需要开辟栈帧的，如果无限制的调用下去，栈空间会被耗干，就出现了“栈溢出”现象。为了防止这种情况，递归时需要注意以下2点：
- 需要一个限制条件，当不满足这个限制条件时，递归不再继续。
- 不断接近这个限制条件。
还是“打印一个整数的每一位”这个例子。可以发现，当满足n>=10时，才会递归调用Print(n/10)，这就是递归的限制条件。如果没有这个条件，就会无限递归下去，出现“栈溢出”的错误。
由于每次递归调用都是Print(n/10)，n/10之后会接近n>=10这个条件，直到n变成一位数，不满足这个限制条件，递归结束。
注意，以上的2个注意事项只是递归的“必要条件”，而不是“充要条件”。也就是说，满足这2个注意事项，你写的递归函数不一定对，但不满足这2个注意事项的话，你写的递归函数一定是错误的。
递归的优缺点
优点：
- 递归可以用少量的代码实现大量重复的计算，代码较为简洁。
- 有一些场景非常适合使用递归实现，比如数据结构中的树形结构，基本上都要使用递归来实现各种功能。
缺点：
- 当递归的深度太深的时候，会出现“栈溢出”的错误。
- 某些场景下，递归的重复计算太多，会导致时间复杂度也偏高。
这里强调一下最后一点，即“递归会增加时间复杂度”。以“求斐波那契数列的第n项”为例，也就是本篇博客开头举的例子，大家可以在自己电脑上测一下，当n是50多的时候，算的会非常慢。这是因为，递归调用时，会有大量重复的计算，整体是一个类似二叉树的结构，时间复杂度为O(2N)。比如计算Fib(50)：
- Fib(50)会调用Fib(49)和Fib(48)。
- Fib(49)调用Fib(48)和Fib(47)，Fib(48)调用Fib(47)和Fib(46)。
- Fib(48)调用Fib(47)和Fib(46)，Fib(47)调用Fib(46)和Fib(45)，Fib(47)调用Fib(46)和Fib(45)，Fib(46)调用Fib(45)和Fib(44)……
这要是一直调用下去，耗时将以“指数爆炸”的形式增长，程序的时间复杂度太高，效率太低。
所以，递归并不适用于所有情况，一定要在不太影响效率的前提下使用。
总结
- 递归就是自己调用自己，实现思路是大事化小小事化了。
- 递归是“递推”和“回归”的合称，会先向深处递推，再回归。
- 递归需要注意，必须在满足某个限制条件时才继续递归，且每次递归要更加接近这个限制条件。
- 递归深度太深，会导致栈溢出。
- 递归有可能增加时间复杂度，导致程序效率太低。只有在不过多影响效率的前提下，才推荐使用递归。
感谢大家的阅读！
