哈喽！这里是一只派大鑫，不是派大星。本着基础不牢，地动山摇的学习态度，从基础的C语言语法讲到算法再到更高级的语法及框架的学习。更好地让同样热爱编程(或是应付期末考试 狗头.jpg)的大家能够在学习阶段找到好的方法、路线，让天下没有难学的程序(只有秃头的程序员 2333)，学会程序和算法，走遍天下都不怕！

今天呢我们来讲一下非常有用也非常令人费解的算法——递归！ Oh my god

可能很多人在大一的时候，就已经接触了递归了，不过，我敢保证很多人初学者刚开始接触递归的时候，是一脸懵逼的，我当初也是，给我的感觉就是，递归太神奇了！

可能也有一大部分人知道递归，也能看的懂递归，但在实际做题过程中，却不知道怎么使用，有时候还容易被递归给搞晕。也有好几个人来问我有没有快速掌握递归的捷径啊。说实话，哪来那么多捷径啊，不过，我还是想写一篇文章，谈谈我的一些经验，或许，能够给你带来一些帮助。

为了兼顾初学者，我会从最简单的题讲起！

举个从小就听过的例子：

从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：“ 从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：“ 从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：“ 从前有座山，山中有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：“太困了不讲了”，于是都回去睡觉了。”于是都回去睡觉了。”于是都回去睡觉了。”于是都回去睡觉了。

我晕，怎么讲了那么多故事，其实不然，我用不同颜色标记处来了每一层的对应关系，

很明显地看出颜色从头开始往中间逐渐变化，然后到一定程度（我们称之为递归的边界或是结束条件）就从内二外的层层返回。——这就是递归

类似于剥洋葱，一层套着一层，直到掰到最里层。

1.什么是递归？

那么什么是递归呢? 要理解递归，就得先了解什么是递归，实际上这句话就是一个递归。这么说可能不好理解，接下来我举个简单的例子来解释这段话的意义。

假设我们现在都不知道什么是递归，我们自然想到打开浏览器：输入到谷歌的网页，点击搜索递归，然后在为维基百科中了解到了递归的基本定义。在了解到了递归实际上是和栈有关的时候，你又蒙圈了，什么是栈呢？数据结构没学清楚，此时的你只能又打开谷歌，搜索什么是栈。接下来你依次了解了内存/操作系统。在你基本了解好知识之后，你通过操作系统了解了内存，通过内存了解了栈，通过栈了解了什么是递归这下你恍然大悟！原来这就是递归啊！

这下应该有点明白了吧，这个过程其实就是递归的过程，如果不了解递归，那就先了解什么是递归，可能你会说这是个循环并不是递归，我们前面说到，递归是需要终止条件的，那么你明白递归是什么其实就是终止条件。整个过程，搜索引擎充当递归函数(只是形象的假设)。在你去依次查找递归/栈/内存/操作系统的过程为前行阶段，在你都了解完之后，反回去了解含义的过程为退回阶段。如果还是不太清楚，可以接着看下面的例子。

实际上这张图就很形象地表达出了递归，这句吓得我抱起了抱着抱着抱着我的小鲤鱼的我的我的我如果从字面意义上看可能看不出是什么意思，那么我们可以通过代码来实现同样的效果:

void digui(int n){

cout<<"抱着";

if(!n){

cout<<"我的小鲤鱼";

}

else{

digui(n-1);

}

cout<<"的我";

return;

}

int main(){

cout<<"吓得我抱起了";

digui(2);

return 0;//完结撒花～

}

2.递归的思想

递归的基本思想是某个函数直接或者间接地调用自身，这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题，而不需要过分关注这个子问题是如何被解决的。

递归有三大要素

第一要素：明确你这个函数想要干什么

对于递归，我觉得很重要的一个事就是，这个函数的功能是什么，他要完成什么样的一件事，而这个，是完全由你自己来定义的。也就是说，我们先不管函数里面的代码什么，而是要先明白，你这个函数是要用来干什么。

例如，我定义了一个函数

// 算 n 的阶乘(假设n不为0)

int f(int n){

}

这个函数的功能是算 n 的阶乘。好了，我们已经定义了一个函数，并且定义了它的功能是什么，接下来我们看第二要素。

第二要素：寻找递归结束条件

所谓递归，就是会在函数内部代码中，调用这个函数本身，所以，我们必须要找出递归的结束条件，不然的话，会一直调用自己，进入无底洞。也就是说，我们需要找出当参数为啥时，递归结束，之后直接把结果返回，请注意，这个时候我们必须能根据这个参数的值，能够直接知道函数的结果是什么。

例如，上面那个例子，当 n = 1 时，那你应该能够直接知道 f(n) 是啥吧？此时，f(1) = 1。完善我们函数内部的代码，把第二要素加进代码里面，如下

// 算 n 的阶乘(假设n不为0)

int f(int n){

if(n == 1){

return 1;

}

}

有人可能会说，当 n = 2 时，那我们可以直接知道 f(n) 等于多少啊，那我可以把 n = 2 作为递归的结束条件吗？

当然可以，只要你觉得参数是什么时，你能够直接知道函数的结果，那么你就可以把这个参数作为结束的条件，所以下面这段代码也是可以的。

// 算 n 的阶乘(假设n>=2)

int f(int n){

if(n == 2){

return 2;

}

}

注意我代码里面写的注释，假设 n >= 2，因为如果 n = 1时，会被漏掉，当 n <= 2时，f(n) = n，所以为了更加严谨，我们可以写成这样：

// 算 n 的阶乘(假设n不为0)

int f(int n){

if(n <= 2){

return n;

}

}

第三要素：找出函数的等价关系式

第三要素就是，我们要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。

例如，f(n) 这个范围比较大，我们可以让 f(n) = n * f(n-1)。这样，范围就由 n 变成了 n-1 了，范围变小了，并且为了原函数f(n) 不变，我们需要让 f(n-1) 乘以 n。

说白了，就是要找到原函数的一个等价关系式，f(n) 的等价关系式为 n * f(n-1)，即

f(n) = n * f(n-1)。

举个栗子，还是从阶乘来出发

假设我们用递归来算阶乘 f(n)

f = n =>

n === 1 ? 1

: n * f(n-1)

f 里面用到了 f，怎么理解呢？

很简单，把式子展开即可：

看到递归了吗？

先递进，再回归——这就是「递归」。

3.递归的缺点

递归的缺点，从上图我们可以看出

在程序执行中，递归是利用堆栈来实现的。每当进入一个函数调用，栈就会增加一层栈帧，每次函数返回，栈就会减少一层栈帧。而栈不是无限大的，当递归层数过多时，就会造成 栈溢出 的后果。

显然有时候递归处理是高效的，比如归并排序；有时候是低效的，比如数孙悟空身上的毛，因为堆栈会消耗额外空间，而简单的递推不会消耗空间。

4.递归的程序特性

优雅性

相比其他解法（比如迭代法），使用递归法，你会发现只需少量程序就可描述出解题过程，大大减少了程序的代码量，而且很好理解。递归的能力在于用有限的语句来定义对象的无限集合。

反向性

由于递归调用程序需要维护调用栈，而栈（我们在上文提过）具有后进先出的特征，因此递归程序适合满足取反类需求。我们在第五部分有一些编程实践，比如字符串取反，链表取反等相关有趣的算法问题。

递推关系

递归程序可以较明显的发现递推关系，反过来也可以这么说，具有递推关系的问题基本都可以通过递归求解（当然也许有性能更佳的解法，但递归绝对是一种选择）。递推关系常见问题有杨辉三角、阶乘计算

5.什么时候用递归

说了那么多，那么我们什么时候可以用、应该用递归呢？

具有以下特征的问题可考虑递归求解：

当问题和子问题具有递推关系，比如杨辉三角、计算阶乘（后文讨论）。具有递归性质的数据结构，比如链表、树、图。反向性问题，比如取反。总结下来，最根本的还是要抓住问题本身是否可以通过层层拆解到最小粒度来得解。

6.递归总结

现在，我们更加相信递归是一种强大的技术，它使我们能够以一种优雅而有效的方式解决许多问题。同时，它也不是解决任务问题的灵丹妙药。由于时间或空间的限制，并不是所有的问题都可以用递归来解决。递归本身可能会带来一些不希望看到的副作用，如栈溢出。

有时，在解决实际问题时乍一看，我们并不清楚是否可以应用递归算法来解决问题。然而，由于递归的递推性质与我们所熟悉的数学非常接近，用数学公式来推导某些关系总是有帮助的，也就是说写出递推关系和基本情况是使用递归算法的前置条件。

只要有可能，就应用记忆化。在起草递归算法时，可以从最简单的策略开始。有时，在递归过程中，可能会出现重复计算的情况，例如斐波纳契数（Fibonacci）。在这种情况下，你可以尝试应用 Memoization 技术，它将中间结果存储在缓存中供以后重用，它可以在空间复杂性上稍加折中，从而极大地提高时间复杂性，因为它可以避免代价较高的重复计算。

当堆栈溢出时，尾递归可能会有所帮助。

使用递归实现算法通常有几种方法。尾递归是我们可以实现的递归的一种特殊形式。与记忆化技术不同的是，尾递归通过消除递归带来的堆栈开销，优化了算法的空间复杂度。更重要的是，有了尾递归，就可以避免经常伴随一般递归而来的堆栈溢出问题，而尾递归的另一个优点是，与非尾递归相比，尾部递归更容易阅读和理解。这是由于尾递归不存在调用后依赖（即递归调用是函数中的最后一个动作），这一点不同于非尾递归，因此，只要有可能，就应该尽量运用尾递归。

至此，这篇文章就到这里了~ 如果你觉得对你有一点帮助，或是还有疑问，亦或是文章哪写得不好，有什么问题，欢迎在下方留言。

留下你的赞，点个关注不迷路！