递归就是这么简单(结论篇)

一、背景

之前写过《 递归就是这么简单(原理篇) 》，看了原理，发现递归很简单。

但是实际做题做项目的时候，会发现递归很难实现。

这里其实不是递归难，而是我们没有想清楚自己要做什么。

这篇文章简单的总结一下该如何做。

二、递归关系与记忆化

我们知道，递归是一个可以优雅而有效解决很多问题的强大技术。

但是递归不是银弹 silver bullet 。

由于时间或空间的限制，并不是所有的问题都可以使用递归解决。

比如有时候递归可能不可预期的问题，如爆栈、死循环等。

When in doubt, write down the recurrence relationship.

有时候，初次看到一个问题的时候，我们并不是马上能想出来怎么用递归解决这个问题。

然而，我们通过梳理问题之间的关系，并用数学式子表达出来后，就会发现可以用递归解决。

这是因为递归的性质和数学式子是很类似的。

通过数学式子，我们可以清晰的看清楚递归关系，并发现问题之间的几何意义。

Whenever possible, apply memoization.

对于某些递归关系，我们很快的实现了对应的代码。

但是有时候，会发现存在重复计算问题，比如斐波纳契数。

此时我们就可以使用记忆化技术，将计算过的结果缓存起来，下次需要的时候直接返回结果。

就这样，我们通过空间换时间的方法，避免重复计算，从而可以大大的降低时间复杂度。

三、合并两个有序链表

题意：给两个有序链表，求合并后的链表。

思路：使用循环的方法也可以做，这里我们使用递归的方法来实现。

递归函数的定义就是题意，即传入两个有序链表，返回合并后的链表头。

当某一个链表为空时，显然可以直接返回另一个链表。

而两个链表都不为空时，链表头肯定是两个链表里面值最小的那个。

所以这里递归就可以找到最小的链表头结点，剩下的递归合并。

最后链表串起来，返回链表头即可。

四、构造二叉搜索树

题意：给 1~n 数字，求构造所有合法的二叉搜索树。

思路：咋一看这道题，可能会没有思路。

但是看一下所有的二叉搜索树的根，会发现分别是 1~n ，如果我们依次求出所有根的二叉搜索树，合并起来就是所有的二叉搜索树了。

而二叉搜索树有一个性质：左子树的值都小于根，右子树的值都大于根。

这个对应到构造数字上，就是一颗二叉搜索树，其数字区间是连续的。

假设我们要构造 [start, end] 这个区间的二叉搜索树，依次枚举根为 i ，则左子树区间是 [start, i-1] ，右子树区间是 [i+1, end] 。

而一个区间构造的子树有多个，左子树和右子树相交，即可得到所有根为 i 的二叉搜索树了。

五、爬楼梯

题意：楼梯有 n 层，你需要从第 1 层往第 n 层爬到楼顶。

每次你可以爬一层或者两层，问有多少种不同的方法爬到楼顶。

思路：可以很容易写出一个数学公式来。

大概是 f(n) = f(n-1) + f(n-2) 。

而对于 n<=1 时， f(n)=1 。

简单的实现递归代码后，发现 n 比较大的时候，数据要很久才能跑出来。

这是因为我们重复计算了很多冗余的数据。

如下图

f(10) = f(9) + f(8)  
f(9) = f(8) + f(7)  
f(8) = f(7) + f(6)

我们计算 f(10) 的时候需要计算 f(9) 和 f(8) 。

而计算 f(9) 的时候，又需要计算 f(8) 和 f(7) 。

计算 f(8) 的时候，需要计算 f(7) 和 f(6) 。

也就是计算 f(10) 的时候，我们计算了两次 f(8) 和三次 f(7) 。

而且这个递归的层数越深，重复计算的次数越多。

这就导致时间复杂度变成指数级别的了。

而我们将计算过的结果保存下来后，每个数字只需要计算一次，复杂度将是 O(n) 的了。

六、最后

其实，递归和动态规划是一个东西。

不过两个东西不是一个概念。

递归是一种具体的技术，通过并调用自己，最终计算出结果来。

而动态规划是一种算法思想，通过将问题转化子问题，并用数学公式表达出来。

一般这个数学公式会依赖于自身，所以此时通过递归来解决，就是所谓的 push down ，而通过循环递推的解决，则是所谓的 push up 。

这里的关键是理解一个问题的转化关系，也就是使用数学公式表达这个问题，剩下的就是代码实现了。

突然发现这个和做项目一样，问题的转化关系，就是项目的架构设计，而架构设计好了，剩下的也是代码实现了。

突然发现，上一篇文章最后提的问题在这里已经得到了解释。

当时提的问题是：

对于递归，已经写过程序的人都会感觉这个很简单。
但是如果看过语法解析或者协议解析的代码，比如json库、protobuf库，就会发现这些库也就是一些递归函数的互相调用。

那为什么说起递归会感觉简单，实现一个json库或者程序语言的语法分析很多人认为很难呢？

你看出这个问题的答案了吗？

-EOF-