迪杰斯特拉是对的——递归本不该这么难

几乎每种编程语言都有各种控制结构，比如 if…else／switch…case 块，以及 for、while 这类迭代结构。大多数新手程序员最先学的都是迭代式的控制结构。

但还有另一种非常强大的控制结构：递归。递归是计算机科学中最重要的思想之一，却常被视为编程里较难掌握的部分之一。书本介绍它的时机，往往比迭代结构晚得多。

网上有那么多人在问，为什么递归或递归程序这么难懂，这可能会让你觉得递归确实是一门高级技巧。但它并不非得这么难。

诚然，要识别出一个问题的递归本质并想出解法，需要几分直觉，但这种直觉可以通过练习培养出来。本文将介绍并讲解若干概念与思路，在你练习递归题目时派得上用场。

为什么要用递归？

你可能听过这个玩笑——要理解递归，你必须先理解递归。它呼应了一个常见的定义：递归就是一个调用自身的函数。

这样的定义容易让人以为，这类调用会导致无限回退，但定义得当的递归解法永远不是无限的。原因在于：递归子调用从不解决与原函数完全相同的问题，而总是在解决原问题的一个更简单的版本。到了某个时刻，这个版本会简单到可以直接解出来——递归也就到此为止。

这引出了递归最重要的用途：用递归来降低手头问题的复杂度。

来看个例子。假设你想计算一个数组中所有元素之和，而这个数组里还嵌套着子数组。也就是说，当函数收到下面这样的嵌套数组时：

[1,[11,42,[8, 1], 4, [22,21]]]

它返回所有元素的和：

1+11+42+8+1+4+22+21 = 110。

窍门在于：先找出并解决那个更简单的问题，然后用这个简单情形来表述原问题。接着不断施加递归，直到抵达并解决那个情形。这么一来，通往原问题的所有其他递归步骤也随之解决了。

手头这个问题的最简单情形，是不含嵌套子数组的数组。对这样的数组，计算函数可以长这样：

function sum(a) {
    let result = 0;

    for (let i = 0; i < a.length; i++) {
        result += a[i];
    }
    return result;
}

assert.equal(sum([1, -5, 100]), 96);

现在我们有了函数 sum，它接收一个数组并返回其中所有元素之和。接下来解决原来那个更难的问题。题目说某些元素可能是数组，而当前实现假定数组里所有元素都是数字。所以我们只需检查某个元素是不是数组；如果是，我们已经有 sum 函数可以算出那个数组里所有元素的和了。把 sum 函数稍作调整：

function sum(a) {
    let result = 0;

    for (let i = 0; i < a.length; i++) {
        if (Array.isArray(a[i])) {
            result += sum(a[i])
        } else {
            result += a[i];
        }
    }
    return result;
}

assert.equal(sum([1,[11,42,[8, 1], 4, [22,21]]]), 110);

就这样。我们先解决了一个更简单的问题，再用那个解法去解决更难的问题。这道题也可以用迭代解法，但会麻烦得多，因为我们得嵌套 for 循环，却不知道到底嵌套了多深。嵌套层数未知，是所有本质上属于递归的问题的共同特征，看到它就该想到需要递归解法。

除了帮助降低问题复杂度，递归还有一项重要能力——回溯。需要回溯的问题通常涉及遍历树或图，例如各种迷宫。这类问题是一步一步解决的。通用算法如下：

1. 如果算法的当前步骤就是问题的解，返回结果。
2. 如果当前步骤不是解，看看从这里还能往哪里走。
3. 如果还有地方可走，选一个走过去，看看是不是解。
4. 如果无处可走了——回溯。

来看个例子。给定下面这棵树：

它以带子节点的节点形式表示：

let tree = {
    name: 'A',
    value: 4,
    children: [
        {
            name: 'B', value: 7,
            children: [{name: 'C', value: 9, children: []}]
        },
        {
            name: 'D', value: 11,
            children: [{name: 'E', value: 9, children: []}]
        },
        {name: 'F', value: 55, children: []},
        {
            name: 'G', value: 65,
            children: [
                {name: 'H', value: 21, children: []},
                {name: 'I', value: 33, children: []}
            ]
        }
    ]
};

任务是找出值为 21 的节点。

我们打算这么做：

1. 先检查节点 A。
2. 如果不是我们要找的，就走到 B，再走到 C。
3. 路径上没有节点满足条件，而且从这里无处可去，于是我们回溯到 A。
4. 接着检查 D 和 E。没戏。
5. 回溯。F。
6. 再回溯。检查 G。还是没戏。

但我们还有地方可去。终于到了 H。这就是我们要找的节点。

下面是一个简单的实现：

function find(node, value) {
    if (node.value === value) {
        return node;
    } else {
        for (let i = 0; i < node.children.length; i++) {
            let found = find(node.children[i], value);
            if (found !== null) {
                return found;
            }
        }

        return null;
    }
}

assert.equal(find(tree, 21).name, 'H');

设计解法

初学者在设计递归解法时常犯的一个错误，是试图想象递归调用内部发生了什么，而不是干脆相信它会返回正确的结果。在嵌套数组那道题里，面对这段解法

if (Array.isArray(a[i])) {
    result += sum(a[i])

不要去想 sum 函数执行时会发生什么。这不是思考递归的有效方式。相反，请相信它会返回数组 a[i] 中所有元素的正确和。另外，不要把递归程序当成一连串执行步骤，也别试图在脑子里重建执行树。对某些复杂问题来说，这非常困难，而且帮不到你想出解法。

着手求解时，想一想原问题如何能表述为「一个更简单的问题 + 一些额外操作」。找出这个更简单的问题，大概是解决递归问题中最难的一步。 对上面例子里那种简单题，这或许是显而易见的，但对许多更难的题目，看出其中的模式是需要功力的。练得越多，就越擅长。

找出更简单的问题之后，接着去找你的函数需要解决的最简单的问题。这个最简单的问题称为基准情形（base case）。它通常表现为一个终止递归的条件。在前面的例子里，它体现为 for 循环检查数组中是否还有元素（sum），或节点是否还有子节点（find）。有时在简单题里，那个帮你解决原问题的更简单问题，同时也就是基准情形。但在更难的题目里就不是这样了，比如著名的「汉诺塔」问题：

你有三根柱子和若干大小不同的圆盘，圆盘可以移动到任意柱子上。一开始，这些圆盘按大小升序整齐地叠在一根柱子上。游戏的目标是把所有圆盘移到第 3 号塔。但你一次只能移动一个圆盘，而且不能把大盘放在小盘上面。

这里你需要看出来的更简单问题是这样的：

1. 把 n-1 个圆盘移到辅助柱上。

2. 把最后一个圆盘从源柱移到目标柱。

3. 移完最后一个圆盘后，辅助柱上剩下的圆盘就可以移到目标柱了。

这里的关键是：不要去推演圆盘是怎么一步步被移到辅助柱上的，而要假定它们已经在那儿了，于是我们可以移走最后一个圆盘，再把剩下的移过去。我们为这种情形写出代码：

function move(n, src, aux, dest) {

    // 把除最后一个之外的所有圆盘从源柱移到辅助柱；
    // 这就是为什么函数调用中 aux 和 dest 两根柱子互换了位置，
    // 好让 aux 成为目标柱
    move(n - 1, src, dest, aux);

    // 把最后一个圆盘从源柱移到目标柱
    dest.push(src.pop());

    // 把剩下的圆盘从辅助柱移到目标柱；
    // 这就是为什么函数调用中 aux 和 src 两根柱子互换了位置，
    // 好让辅助柱成为源柱
    move(n - 1, aux, src, dest);
}

有了更简单的问题，我们还需要找到最简单的基准情形。这个大概不难看出来：

如果只剩一个圆盘，直接把它移到目标柱就行：

function move(n, src, aux, dest) {
    if (n === 1) {
        dest.push(src.pop());
    } else {
        move(n - 1, src, dest, aux);
        dest.push(src.pop());
        move(n - 1, aux, src, dest);
    }
}

这就是终止递归的基准情形。而它并不是那个帮你解决原问题的、更简单的问题。

现在，试着把上面学到的东西用到下面这两道题上：

1. 求嵌套数组之和

写一个函数，对可能包含嵌套子数组的数组求出其中所有数字之和。不要使用循环。

2. 生成二进制字符串

写一个函数，生成 n 个比特位上 1 和 0 的所有可能组合。例如，如果函数收到的位数是 2，它应当产生下面这 4 种组合：00,01,10,11。不能使用任何数学运算符。

在琢磨解法时，请试着通过「找出更简单的问题和基准情形」来思考，而不是靠一步步构造执行流程。另外也可以这样想：假设你此刻正站在某个中间步骤上，下一步该做什么操作才能朝解法推进？

解答与讲解见文末。

尾调用优化

你可能听过 调用栈 这个词。它多数时候用在调试中，用来搞清楚出错的那个函数是被谁调用的。所以，如果你在文件 index.js 里有这样一段代码：

function a(n) {
    let a = 1;
    return a + n;
}

function b(n) {
    let b = 5;
    let value = a(n);  // 行 B
    return b + value;
}

function c() {
    let c = 3;
    let v = b(c);  // 行 C
    console.log(v);
}

c();  // 行 A

并在 a 内部打一个断点，你会看到大致如下的调用栈：

a() (return to: {b(): B}, locals: {a=1, n=3})
b() (return to: {c(): C}, locals: {b=5, n=3})
c() (return to: {index.js: A}, locals: {c=3, v=undefined})

它表明函数 a 是从 b 调用的，而 b 是从 c 调用的。「调用栈」这个名字正由此而来——一摞函数调用。栈中的每一项称为栈帧（stack frame），它保存的信息包括：局部变量，以及返回地址（当前函数退出时该回到哪里）。要紧的是，栈上帧的数量和大小是有限的。这意味着如果你不停地调用函数，调用得够多，就会得到栈溢出错误。这个上限并不固定，随环境而异，还取决于每个具体函数的帧大小。

递归函数会反复调用自身，所以存在栈溢出的潜在风险。例如，下面这个简单的递归函数计算一个数的阶乘：

function fact(n) {
    if (n === 0 || n === 1) {
        return 1;
    }
    return n * fact(n - 1);
}

如果我们传入一个相当大的数，比如 100 000，在大多数环境下都会报错。这种阶乘的递归实现通常并不推荐作为递归的示例，因为同样的结果用迭代解法要容易得多。除了潜在的栈溢出错误，这种递归解法还会占用额外的栈帧、进而占用更多内存，给性能带来额外开销。

不过，对 Lisp、Scheme 这类许多函数式语言而言，这却是首选的解法。那它们是怎么避开上述问题的呢？答案是尾调用优化。我们来看看上面那个栈示例改写后的代码：

function a(n, p) {
    let a = 1;
    return a + n + p;
}

function b(n) {
    let b = 5;
    return a(n, b);
}

function c() {
    let c = 3;
    let v = b(c);  // 行 C
    console.log(v);
}

c();  // 行 A

现在看来，为函数 b 创建栈帧已经没有意义了，因为它所做的全部就是调用 a，之后不再执行任何动作。编译器注意到了这一点，于是优化这些调用，不再为 b 创建栈帧。优化后的栈现在长这样：

a() (return to: {c(): C}, locals: {a=1, n=3, p=5})
c() (return to: {index.js: A}, locals: {c=3, v=undefined})

看看函数 b 改写前后的差别：

// 没有尾调用优化
let value = a(n);
return b + value;

// 有尾调用优化
return a(n, b);

所以主要差别在于：函数 a 返回之后不再有其他动作。我们把阶乘函数改写成符合尾调用优化条件的形式：

function fact(acc, n) {
    if (n === 1) {
        return acc;
    } else {
        return fact(acc * n, n - 1);
    }
}

可以看到，我们不再是等递归调用返回后拿到返回值再算结果，而是先把结果算好，然后一路传给下一次递归调用。也就是说，在第一种未做尾调用优化的实现里，你先执行递归调用，然后拿递归调用的返回值去计算结果。这样一来，在从每一层递归调用返回之前，你都拿不到计算结果。

要把实现改造成尾递归，你要先做计算，再执行递归调用，把当前步骤的结果传给下一个递归步骤。这样一来，当条件满足时，最后那次递归调用只需返回累积下来的值即可。从根本上说，任何一个递归步骤的返回值，都与下一次递归调用的返回值相同。由此带来的结果是：一旦你准备好执行下一个递归步骤，当前这个栈帧就不再需要了。

在某些函数式语言中，尾调用优化也可以通过续延传递风格（CPS）——也就是回调——来实现。使用回调时不需要 return 语句，因此编译器可以优化递归调用。虽然 JavaScript 对回调模型支持得相当好，但它目前并不支持通过 CPS 实现的尾调用优化。

解答

那么，第一道题是：

写一个函数，对可能包含嵌套子数组的数组求出其中所有数字之和。不要使用循环。

我们可以先找出更简单的问题——也就是不含嵌套子数组的数组。用同样的问法来解决这个更简单的问题：

1. 更简单的问题是什么？更简单的问题是：我已经有了 n-1 个元素的和，只需要把当前元素加进去。
2. 最简单的情形是什么？最简单的情形是没有元素可加了——返回 0。

于是实现如下：

function sum(a, i) {
    if (i < 0) {
        return 0;
    } else {
        return a[i] + sum(a, i - 1);
    }
}

let input = [1, 2, 0, 3];
assert.equal(sum(input, input.length - 1), 6);

现在我们解决了不含嵌套数组的更简单问题。接下来要把嵌套数组考虑进来。我们需要检查某个元素是不是数组，如果是，就对它运行 sum 函数。这里要紧的是别忘了取回嵌套子数组中元素的和，并把它加进结果值里。最终实现如下：

function sum(a, i) {
    if (i < 0) {
        return 0;
    }

    let current = a[i];

    if (Array.isArray(a[i])) {
        current = sum(a[i], a[i].length - 1);
    }

    return current + sum(a, i - 1);
}

let input = [1, 2, [1, 2], 3, [5]];
assert.equal(sum(input, input.length - 1), 14);

现在来看第二道题：

写一个函数，生成 n 个比特位上 1 和 0 的所有可能组合。例如，如果函数收到的位数是 2，它应当产生下面这 4 种组合：00,01,10,11。不能使用任何数学运算符。

这里最简单的情形是什么？我们只需为一个比特位产生字符串。为此会有两个字符串：1 和 0。也就是说，我们有一个函数，当位数为 1 时输出 1 和 0。把它写下来，假设存在一个持有数组的全局变量 a：

function binary(n) {
    if (n === 1) {

        a[n - 1] = 0;
        console.log(a.join(''));

        a[n - 1] = 1;
        console.log(a.join(''));
    }
}

当前这个实现里有重复的 console.log 语句，所以我们可以改进代码：把打印放到最后一步，也就是没有更多比特位可设置的时候。重写实现：

function binary(i) {
    if (i === 0) {
        console.log(a.join(''));
    } else {
        a[i - 1] = 0;
        binary(i - 1);
        a[i - 1] = 1;
        binary(i - 1);
    }
}

现在来看看 2 个比特位会有哪些组合。

我们从一个比特位都没设置开始。然后把第 n 位设为 0。接着对第 n-1 位做同样的事。我们沿着这个模式走下去，直到没有比特位可设置为止。打印出这个组合，然后回溯一层。接着把第 n 位设为 1。可以清楚看出，每一步中函数只关心设置当前这一位，然后调用函数去处理剩下的位。

而这正是我们在处理单个比特位的实现里已经有的东西。事实证明，仅仅通过改写基准情形，我们就得到了一个对任意位数都适用的解法。