内容概览

• 前言
• 递归
• 思维要点
• 实战题目
• 总结

前言

在 3. 树、二叉树、二叉搜索树 —— Ficow 陪你学算法和数据结构 中，Ficow 和您分享了自己的学习笔记。本文将深入讲解常用的递归算法，而且文末还附有覃超老师推荐的练习题目。

提到递归，很多朋友都会皱起眉头。毕竟，递归比较抽象，用递归来解决问题更加抽象。
然而，很多企业在面试的时候都会有递归相关的题目。比如，树的面试题解法，一般都是基于递归的。

既然已经知道了这个龙门，那咱们就使劲练习、不断提高，逼一下自己就跳过去了~

在开始阅读后文之前，我强烈建议您学习覃超老师在 极客时间 上开设的 算法训练营体验课，我已经亲身学习过并推荐给了朋友、同事们。

该课程的内容主要是以视频为主，质量非常高，而且短小精悍。主要涉及：

• 复杂度分析
• 数组、链表、跳表
• 树、二叉树、二叉搜索树
• 递归（代码模板非常给力）

截止 Ficow 创作此文当日，该课程售价还是 9.9 元，性价比还是挺高的。极客时间的新用户还可以免费领取，有效期是一周。赶快行动吧~

因为本文属于 Ficow 陪你入门 系列文章，所以 Ficow 也会记录自己的学习历程，并和您分享我自己的 学习笔记。欢迎您留言和我交流，大家共同进步！

递归（Recursion）

递归其实本质上就是利用函数体来进行循环。在更底层的汇编语言实现中，递归其实就是程序在执行过程中跳回(JMP)到之前执行过的某个指令，如此反复跳回就形成了我们看到的递归调用。

生动有趣的故事：从前有座山，山里有座庙，庙里有个和尚在讲故事，讲什么呢？从前有座山，山里 ……

更有意思的例子：《盗梦空间》中的一层套一层的梦境，逐层深入，时间变得更慢，最终将某种状态从梦境中带回现实世界。

最简单的阶乘递归示例：

最终产生的递归栈：

实用的递归模板：

每次写递归代码的时候都先打好这个模板，然后再开始填充逻辑：

• 递归终止条件
• 处理当前递归层级的逻辑
• 进入到递归的下一层级
• 如果有必要的话，清理当前递归层级的状态（比如：调整全局变量的值）

思维要点

下面就展开来讲解这几个要点：

• 在写递归代码时，很多人会陷入人肉递归的情况（人脑模拟计算机去运行代码，很快就会晕头转向），这个其实是我们必须要警惕的思维误区。
• 能写成递归的代码，一定存在重复的子问题，找到了子问题就可以写出递归代码。而且，面试题的正确答案一般都比较简短，最多也就几十行。
• 思考当 n 为 1 时的情况，当 n 为 2 时的情况，当 n 为 3 时的情况，然后就不要再这样简单地重复下去。这时候，要找出重复的规律，而且要保证没有漏算的情况，保证结果是互斥且穷尽的(MECE: Mutually Exclusive, Collectively Exhaustive)。最后，找出的重复规律应当满足这个条件：当 n 为 n 时以及 n 为 n + 1 时也符合这个规律。

实战题目

爬楼梯：https://leetcode-cn.com/problems/climbing-stairs/
生成括号：https://leetcode-cn.com/problems/generate-parentheses/
二叉树的最大深度：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
二叉树的最小深度：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
验证二叉搜索树：https://leetcode-cn.com/problems/validate-binary-search-tree/
翻转二叉树：https://leetcode-cn.com/problems/invert-binary-tree/
二叉树的序列化和反序列化：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
二叉树的最近公共祖先：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
从前序与中序遍历序列构造二叉树：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
组合：https://leetcode-cn.com/problems/combinations/
全排列：https://leetcode-cn.com/problems/permutations/
全排列 II：https://leetcode-cn.com/problems/permutations-ii/

练题的操作步骤：

• 写出自己的思路，多种解法 都写下来，最后再去比较并找出最好的解法；
• 用代码实现自己的解法，然后用题目提供的测试数据进行测试（多尝试几组数据，比如特殊情况）；
• 测试通过后即可提交代码，然后查看该代码的审题结果，主要看耗时以及时间复杂度；
• 寻求反馈：Code Review（尽量这样做）、查看题解（跳过糟糕的解法），理解别人的思路还有代码的写法，然后自己实践几遍；
• 复制题解的网址，删除域名中的 -cn，然后打开 LeetCode 国际站，在 题目的 Discuss 页面选择 Most Votes，消化吸收各种优秀的解法，同时提升英语水平。
• 把这个题目刷 5遍，5遍，5遍！！！千万不要只刷一遍！！！

总结

互联网名企的笔试面试都会考察类似的题目，所以我们一定要做足充分的准备。在准备的过程中，要尽可能做到以下几点：

• 只是知道概念是没什么用的，一定要把题目练习到熟练并且专业的程度。如果不熟练，在笔试面试过程中会更加紧张，最后就很容易失误。
• 刻意练习，持续地刻意练习。深耕一个领域，需要有节奏有规划的刻意练习（一万小时定律）。
• 要锻炼分析、解决问题的能力。学知识、刷算法题，本质上是为了提升自己解决问题的能力。在这个过程中，我们会不断地提升抽象问题、分析问题的能力。
• 三人行必有我师，要善于向他人请教（比如：LeetCode 题解、去极客时间参加培训课）。

到本文创作完成之时，Ficow 已经把这个视频刷了 3 遍。接下来，Ficow 会去刻意练习这些题目，我想会是 5 遍。虽然有些题目在大学时期就已经做过，但是当时并没有按照覃超老师推荐的方法去练习，而且也远远没有达到熟练甚至专业的水平。

知道自己的不足是一件好事，至少自己还有比较清晰的努力方向！朋友，如果你也看到了自己的不足，那就赶快行动起来吧！！！💪💪💪

您有什么想和 Ficow 交流的，大可不必拘束，尽管留言吧~ 😄

参考内容：

极客时间
算法训练营体验课
LeetCode
LeetCode - 中文站