一文读懂递归算法

冷不防 2021-12-07 14:41 358阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640][]

作者 | 刘毅

来源 | https://www.61mon.com/index.php/archives/208/

递归的学习绝对是一个持久战，没有人可以一蹴而就。一年两年的，很寻常。

问题的复杂，加上递归本身的细节，我们想要 "学会"，"学好"，再 "用好"，是需要一个漫长的过程的。所以还希望读者有足够的耐心。

## **一：什么是递归** ##

所谓递归，简单点来说，就是一个函数直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

我们可以把” 递归 “比喻成 “查字典 “，当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第二个词。

可惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头，然后你开始后退，逐个明白之前查过的每一个词，最终，你明白了最开始那个词的意思。（摘自知乎的一个回答）

我们以阶乘作为：

> **int**Factorial(**int**n)\{ 
> 
> **if**(n == 0)**return**1;
> 
> **return**
> 
> n \* Factorial(n \- 1);
> 
> \}

##     ##

## **二：递归与栈的关系** ##

常常听到 “递归的过程就是出入栈的过程”，这句话怎么理解？我们以上述代码为例，取 n=3，则过程如下：

![640?wx\_fmt=png][640_wx_fmt_png]

*  第 1~4 步，都是入栈过程，`Factorial(3)`调用了`Factorial(2)`，`Factorial(2)`又接着调用`Factorial(1)`，直到`Factorial(0)`；
 *  第 5 步，因 0 是递归结束条件，故不再入栈，此时栈高度为 4，即为我们平时所说的递归深度；
 *  第 6~9 步，`Factorial(0)`做完，出栈，而`Factorial(0)`做完意味着`Factorial(1)`也做完，同样进行出栈，重复下去，直到所有的都出栈完毕，递归结束。

**每一个递归程序都可以把它改写为非递归版本。**我们只需利用栈，通过入栈和出栈两个操作就可以模拟递归的过程，二叉树的遍历无疑是这方面的代表。

`但是并不是每个递归程序都是那么容易被改写为非递归的。某些递归程序比较复杂，其入栈和出栈非常繁琐，给编码带来了很大难度，而且易读性极差，所以条件允许的情况下，推荐使用递归。`

## **三：如何思考递归** ##

在初学递归的时候, 看到一个递归实现, 我们总是难免陷入不停的验证之中，比如上面提及的阶乘，求解`Factorial(n)`时，我们总会情不自禁的发问，`Factorial(n-1)`可以求出正确的答案么？接着我们就会再用`Factorial(n-2)`去验证，，，不停地往下验证直到`Factorial(0)`。

对递归这样的不适应，和我们平时习惯的思维方式有关。我们习惯的思维是：已知`Factorial(0)`，乘上 1 就等于`Factorial(1)`，再乘以 2 就等于`Factorial(2)`，，，直到乘到 n。

**而递归和我们的思维方式正好相反。**

那我们怎么判断这个递归计算是否是正确的呢？Paul Graham 提到一种方法，如下：

> 如果下面这两点是成立的，我们就知道这个递归对于所有的 n 都是正确的。
> 
> 1.  当 n=0,1 时，结果正确；
> 2.  假设递归对于 n 是正确的，同时对于 n+1 也正确。

这种方法很像数学归纳法，也是递归正确的思考方式，上述的第 1 点称为基本情况，第 2 点称为通用情况。

在递归中，我们通常把第 1 点称为终止条件，因为这样更容易理解，其作用就是终止递归，防止递归无限地运行下去。

下面我们用两个例子来具体说明这种数学归纳法：

##### 例 1 汉诺塔展开目录 #####

![640?wx\_fmt=png][640_wx_fmt_png 1]

问题描述为：有三根杆子 A，B，C。A 杆上有 N 个穿孔圆盘，盘的尺寸由上到下依次变大，B，C 杆为空。要求按下列规则将所有圆盘移至 C 杆：

1.  每次只能移动一个圆盘；
2.  大盘不能叠在小盘上面。

问：如何移？最少要移动多少次？

首先看下基本情况，即终止条件：N=1 时，直接从 A 移到 C。

再来看下通用情况：当有 N 个圆盘在 A 上，我们已经找到办法将其移到 C 杠上了，我们怎么移动 N+1 个圆盘到 C 杠上呢？很简单，我们首先用将 N 个圆盘移动到 C 上的方法将 N 个圆盘都移动到 B 上，然后再把第 N+1 个圆盘（最后一个）移动到 C 上，再用同样的方法将在 B 杠上的 N 个圆盘移动到 C 上，问题解决。

代码如下：

> **void**Hanoi(**int**n,**char**a,**char**b,**char**c)\{ *//终止条件*
> 
> **if**(n == 1)
> 
> \{ 
> 
> cout << a << "-->" << c << endl;
> 
> **return**;
> 
> \}*//通用情况*
> 
> Hanoi(n \- 1,a,c,b);
> 
> Hanoi(1,a,b,c);
> 
> Hanoi(n \- 1,b,a,c);
> 
> \}

##### **例 2 求二叉树节点个数展开目**录 #####

![640?wx\_fmt=png][640_wx_fmt_png 2]

首先看下基本情况，即终止条件：当为空树时，节点数为 0；

再来看下通用情况：当前节点的左，右子树节点数都被求出，则以当前结点为根的二叉树的节点总数就是 “左子树 + 右子树 + 1”。

代码如下：

> **int**GetNodes(Node \* node)\{ *//终止条件*
> 
> **if**(node == nullptr)
> 
> **return**0;*//通用情况*
> 
> **return**
> 
> GetNodes(node\->left) \+ GetNode(node\->right) \+ 1;
> 
> \}

##  ##

##     ##

## **四：什么时候该用递归** ##

当我们遇到一个问题时，我们是怎么判断该题用递归来解决的？

> 问题可用递归来解决需具备的条件：
> 
> 1.  子问题需与原问题为同样的事，且规模更小；
> 2.  程序停止条件。

## END ##

## ![640?wx\_fmt=png][640_wx_fmt_png 3] ##

**原 创 热 文 推 荐**

☞[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[☞][Link 2][一道腾讯面试题：厉害了我的杯][Link 3]

[☞][Link 4][十大经典排序算法动画与解析，看我就够了][Link 5]

[☞][Link 4][这或许是东半球分析十大排序算法最好的一篇文章][Link 6]

[☞][Link 4][面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

![640?wx\_fmt=png][640_wx_fmt_png 4] 你点的每个“在看”，我都认真当成了喜欢

[640]: /images/20211207/77f3bff1691b491eb1010b94c0bcebd6.png
[640_wx_fmt_png]: /images/20211207/ce51710ea7364359b64f404fd8b7dbe0.png
[640_wx_fmt_png 1]: /images/20211207/55816d2441fa4f98a17dd2139232c176.png
[640_wx_fmt_png 2]: /images/20211207/494ef618d6ba46cead90e0ad3418d349.png
[640_wx_fmt_png 3]: /images/20211207/1c3fd0a3497443ceb4ab471fc2cccc57.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzA5MzY4NTQwMA==&mid=2651011536&idx=3&sn=fd5ff61a84fe2180a7c21d15acf71659&chksm=8bad8a27bcda03319570ae23d05392d287390a51ca94014422dd199450b25f43467aaaedb59e&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzA5MjcxNjc2Ng==&mid=2650560116&idx=1&sn=f9e86fa3e7b15624177b29ef1a785be4&chksm=88601dc5bf1794d30fd595d413491da189584b44fd2b2e5e40c665e58760e162616585811647&scene=21#wechat_redirect
[Link 5]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 6]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/92825279
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[640_wx_fmt_png 4]: /images/20211207/7faaa9be3ea34869a603f9bb21f36356.png