浅谈递归 II

递归这个方法很简单，很实用，不过需要花时间理解和练习。最好能从多方面来思考它，同时尽力应用到实际中去，这样有助于我们冒出一些有趣的奇思妙想。今天从数学上简单的递归生成函数推广到一类相似的问题。

递归可以这样拆分：基本情况（base case）和构造器（constructor），说起来玄之又玄，来举个例子，让我来生成一下所有自然数吧！我们可以这样递归地生成：

基本情况：规定 0 属于集合 S 。
构造器：如果一个数 x 属于集合 S ，那么 x + 1 也属于集合 S 。

这个很容易理解吧，就好比集合里放一个初始数，然后通过无限调用构造器，生成了整个自然数集合。如果要生成所有整数的集合呢？可以添加一个构造器：

第二个构造器：如果一个数 x 属于集合 S ，那么 -x 也属于集合 S 。

显然，通过这个构造器和第一个结合，就可以生成整个整数集合了。看到这里，你应该提问：凭什么要这样定义第二个构造器呢，

我定义一个：如果一个数 x 属于集合 S ，那么 x - 1 也属于集合 S 。

我认为这个定义非常优秀，因为它在数学上确实能完成任务，不过稍作思考，我似乎从算法分析的角度发现问题：这个递归过程存在冗余计算。我这么说，你是不是觉得有些道理？不过很遗憾，如果你动笔写一下这个生成过程，发现它们是一样的，只要我们那个构造器每次选取做小的那个元素进行生成，而另一个每次选取最大的那个数生成就行了（这是题外话）。

上面只是一个开胃菜，意在让读者有个 “构造器” 这样的概念，下面用这个思路来举两个算法问题。

第一个问题很好理解：给一个正整数 n ，返回所有包含 n 对括号的合法括号序列。比如给 3 ，我们得返回这样一个序列（集合）： ["((()))","(()())","(())()","()(())","()()()"] ，以此类推。

问题有点难度，显然要配合递归思想了，递归解题一定要用好数学归纳法（日后写一篇具体介绍），你这样想：如果我知道了规模为 n - 1 的问题的解，那么我如何解这个问题呢？我的讲解力求具体，这里具体来说就是：如果我知道了如何生成 n - 1 对括号的所有合法解的序列，如何生成 n 对括号的解？不知道。

下一步，加强归纳假设：假设我知道了如何生成任意 x (x <= n - 1) 对括号的所有合法解的序列，如何生成 n 对括号的解？这里似乎还是不好使，我就算知道了子问题的解，如何才能凑出原问题的解呢？问题在于规模为 n 的问题的解并不是规模为 n - 1 的子问题进行简单拼凑就能获得，而是要把这第 n 对括号在子问题里的解进行组合才行，怎么组合呢？

这里先跳过这题，看完第二题后就有点思路了：给一个正整数 n ，返回所有包含 n 个节点的合法的二叉树，比如 n = 3 就要返回下图：（题目和示例来自 LeetCode 中的 Unique Binary Search Trees II ）

1[
2  [1,null,3,2],
3  [3,2,null,1],
4  [3,1,null,null,2],
5  [2,1,3],
6  [1,null,2,null,3]
7]
8   1         3     3      2      1
9    \       /     /      / \      \
10     3     2     1      1   3       2
11    /     /       \                    \
12   2     1         2                     3

用归纳法分析：假设我知道了如何生成任意 x (x <= n - 1) 个节点的所有合法二叉树的序列，如何生成 n 个节点的解？根据二叉树的基本结构构造：左子树 <- 当前节点 -> 右子树可以想到解法。

用具体例子解释下，比如说生成 3 个节点的所有合法二叉树，就有以下几种情况：根节点自己可以是 1, 2, 3，然后分析左右子树；可以左边挂 1 节点的二叉树，右边挂 1 节点的二叉树；或者左边 0 节点，右边 2 节点；或者左边 2 节点，右边 1 节点。这就是所有情况，刚才假设知道了如何生成任意 x (x <= n - 1) 个节点的所有合法二叉树的序列，所以以上分析的几种情况的解都是已知的。这道二叉树的题目略难，因为要控制取值边界，代码放最后，看懂括号生成的解法后有助理解。

继续讲括号生成，问题在于我们没办法像二叉树那样，有一个明确的构造器（左子树 <- 当前节点 -> 右子树）。那我们自己造一个（事实上是正确的）：任何一个合法括号串都能分解为 [s]t 其中 s 和 t 都是合法括号串（规定空字符串也是合法的）。我们可以把这个规律设为构造器，运用归纳法：假设我知道了如何生成任意 x (x <= n - 1) 对括号的所有合法解的序列，如何生成 n 对括号的解？可以，generate(n) = "(" + generate(i) + ")" + generate(j) ，其中 i + j == n - 1 ，因为构造器里有一对括号。

类比刚才的数学问题，我们模仿一下，生成求解的集合 S：

基本情况：规定空串 "" 属于 S
构造器：S 中的任意两个串 s 和 t 这样组合得到 v = (s)t，v 也属于 S

你可以试一下，这样两条定义就可以生成所有合法括号串。按照这个逻辑基础，我们可以写代码了（别忘了之前说的，明确递归函数是干什么的）：

1vector<string> generateParenthesis(int n) {
2    if (n == 0) return {""}; // 基本情况
3    vector<string> ans;
4    for (int i = 0; i < n; i++)
5        for (string left : generateParenthesis(i)) // 挑选 s
6            for (string right : generateParenthesis(n - i - 1)) // 挑选 t
7                ans.push_back("(" + left + ")" + right); // 构造
8    return ans;
9}

应该不难理解，如果有问题，可以回头看下上面的文字分析。下面是二叉树的代码（重点是利用构造器的思路，如果实在搞不清取值问题，就算了）：

1vector<TreeNode*> generateTrees(int n) {
2    if (n == 0) return {};
3    return helper(1, n);
4}
5
6vector<TreeNode*> helper(int lo, int hi) {
7    if (lo == hi) return { new TreeNode(lo) };
8    if (lo > hi) return { nullptr };
9    vector<TreeNode*> res;
10    for (int i = lo; i <= hi; i++)
11        for (TreeNode* left : helper(lo, i - 1)) // 构造左子树
12            for (TreeNode* right : helper(i + 1, hi)) { // 构造右子树
13                auto cur = new TreeNode(i); // 组装
14                cur->left = left;
15                cur->right = right;
16                res.push_back(cur); // 加入解集
17            }
18    return res;

总结：学习新东西后时时刻刻都要想着怎么用出来，数学、算法本身就是很多问题的抽象，学得好是一方面，怎么把抽象的东西实例化，应该时刻惦记着。

更多相关文章

随机推荐