• 原文地址： Functional-Light-JS
• 原文作者： Kyle Simpson－《You-Dont-Know-JS》作者

第 9 章：递归（上）

在下一页，我们将进入到递归的论题。

(本页剩余部分故意留白)

我们来谈谈递归吧。在我们入坑之前，请查阅上一页的正式定义。

我知道，这个笑话弱爆了 :)

大部分的开发人员都承认递归是一门非常强大的编程技术，但他们并不喜欢去使用它。在这个意义上，我把它放在与正则表达式相同的类别中。递归技术强大但又令人困惑，因此被视为 不值得我们投入努力 。

我是递归编程的超级粉丝，你，也可以的！在这一章节中我的目标就是说服你：递归是一个重要的工具，你应该将它用在你的函数式编程中。当你正确使用时，递归编程可以轻松地描述复杂问题。

定义

所谓递归，是当一个函数调用自身，并且该调用做了同样的事情，这个循环持续到基本条件满足时，调用循环返回。

警告： 如果你不能确保基本条件是递归的 终结者 ，递归将会一直执行下去，并且会把你的项目损坏或锁死；恰当的基本条件十分重要！

但是... 这个定义的书面形式太让人疑惑了。我们可以做的更好些。思考下这个递归函数：

function foo(x) {
    if (x < 5) return x;
    return foo( x / 2 );
}

设想一下，如果我们调用 foo(16) 将会发生什么：

在 step 2 中, x / 2 的结果是 8 ， 这个结果以参数的形式传递到 foo(..) 并运行。同样的，在 step 3 中， x / 2 的结果是 4 ，这个结果以参数的形式传递到另一个 foo(..) 并运行。但愿我解释得足够直白。

但是一些人经常会在 step 4 中卡壳。一旦我们满足了基本条件 x (值为4) < 5 ，我们将不再调用递归函数，只是（有效地）执行了 return 4 。 特别是图中返回 4 的虚线那块，它简化了那里的过程，因此我们来深入了解最后一步，并把它折分为三个子步骤：

该次的返回值会回过头来触发调用栈中所有的函数调用（并且它们都执行 return ）。

另外一个递归实例：

function isPrime(num,divisor = 2){
    if (num < 2 || (num > 2 && num % divisor == 0)) {
        return false;
    if (divisor <= Math.sqrt( num )) {
        return isPrime( num, divisor + 1 );
    return true;
}

这个质数的判断主要是通过验证，从2到 num 的平方根之间的每个整数，看是否存在某一整数可以整除 num ( % 求余结果为 0 )。如果存在这样的整数，那么 num 不是质数。反之，是质数。 divisor + 1 使用递归来遍历每个可能的 divisor 值。

递归的最著名的例子之一是计算斐波那契数，该数列定义如下：

fib( 0 ): 0
fib( 1 ): 1
fib( n ):
    fib( n - 2 ) + fib( n - 1 )

注意: 数列的前几个数值是： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 每一个数字都是数列中前两个数字之和。

直接用代码来定义斐波那契：

function fib(n) {
    if (n <= 1) return n;
    return fib( n - 2 ) + fib( n - 1 );
}

函数 fib(..) 对自身进行了两次递归调用，这通常叫作二分递归查找。后面我们将会更多地讨论二分递归查找。

在整个章节中，我们将会用不同形式的 fib(..) 来说明关于递归的想法，但不太好的地方就是，这种特殊的方式会造成很多重复性的工作。 fib(n-1) 和 fib(n-2) 运行时候两者之间并没有任何的共享，但做的事情几乎又完全相同，这种情况一直持续到整个整数空间(译者注：形参 n )降到 0 。

在第五章的性能优化方面我们简单的谈到了记忆存储技术。本章中，记忆存储技术使得任意一个传入到 fib(..) 的数值只会被计算一次而不是多次。虽然我们不会在这里过多地讨论这个技术话题，但不论是递归或其它任何算法，我们都要谨记，性能优化是非常重要的。

相互递归

当一个函数调用自身时，很明显，这叫作直接递归。比如前面部分我们谈到的 foo(..) ， isPrime(..) 以及 fib(..) 。如果在一个递归循环中，出现两个及以上的函数相互调用，则称之为相互递归。

这两个函数就是相互递归：

function isOdd(v) {
    if (v === 0) return false;
    return isEven( Math.abs( v ) - 1 );
function isEven(v) {
    if (v === 0) return true;
    return isOdd( Math.abs( v ) - 1 );
}

是的，这个奇偶数的判断笨笨的。但也给我们提供了一些思路：某些算法可以根据相互递归来定义。

回顾下上节中的二分递归法 fib(..) ；我们可以换成相互递归来表示：

function fib_(n) {
    if (n == 1) return 1;
    else return fib( n - 2 );
function fib(n) {
    if (n == 0) return 0;
    else return fib( n - 1 ) + fib_( n );
}

注意： fib(..) 相互递归的实现方式改编自 “用相互递归来实现斐波纳契数列” 研究报告( https://www.researchgate.net/publication/246180510_Fibonacci_Numbers_Using_Mutual_Recursion ) 。

虽然这些相互递归的示例有点不切实际，但是在更复杂的使用场景下，相互递归是非常有用的。

为什么选择递归？

现在我们已经给出了递归的定义和说明，下面来看下，为什么说递归是有用的。

递归深谙函数式编程之精髓，最被广泛引证的原因是，在调用栈中，递归把(大部分)显式状态跟踪换为了隐式状态。通常，当问题需要条件分支和回溯计算时，递归非常有用，此外在纯迭代环境中管理这种状态，是相当棘手的；最起码，这些代码是不可或缺且晦涩难懂。但是在堆栈上调用每一级的分支作为其自己的作用域，很明显，这通常会影响到代码的可读性。

简单的迭代算法可以用递归来表达：

function sum(total,...nums) {
    for (let i = 0; i < nums.length; i++) {
        total = total + nums[i];
    return total;
// vs
function sum(num1,...nums) {
    if (nums.length == 0) return num1;
    return num1 + sum( ...nums );
}

我们不仅用调用栈代替了 for 循环，而且用 return s 的形式在回调栈中隐式地跟踪增量的求和（ total 的间歇状态），而非在每次迭代中重新分配 total 。通常，FPer 倾向于尽可能地避免重新分配局部变量。

像我们总结的那样，在基本算法里，这些差异是微乎其微的。但是，随着算法复杂度的提升，你将更加能体会到递归带来的收益，而不是这些命令式状态跟踪。

声明式递归

数学家使用 Σ 符号来表示一列数字的总和。主要原因是，如果他们使用更复杂的公式而且不得不手动书写求和的话，会造成更多麻烦（而且会降低阅读性！），比如 1 + 3 + 5 + 7 + 9 + .. 。符号是数学的声明式语言！

正如 Σ 是为运算而声明，递归是为算法而声明。递归说明：一个问题存在解决方案，但并不一定要求阅读代码的人了解该解决方案的工作原理。我们来思考下找出入参最大偶数值的两种方法：

function maxEven(...nums) {
    var num = -Infinity;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] % 2 == 0 && nums[i] > num) {
            num = nums[i];
    if (num !== -Infinity) {
        return num;
}

这种实现方式不是特别难处理，但它的一些细微的问题也不容忽视。很明显，运行 maxEven() ， maxEven(1) 和 maxEven(1,13) 都将会返回 undefined ？最终的 if 语句是必需的吗？

我们试着换一个递归的方法来对比下。我们用下面的符号来表示递归：

maxEven( nums ):
    maxEven( nums.0, maxEven( ...nums.1 ) )

换句话说，我们可以将数字列表的 max-even 定义为其余数字的 max-even 与第一个数字的 max-even 的结果。例如：

maxEven( 1, 10, 3, 2 ):
    maxEven( 1, maxEven( 10, maxEven( 3, maxEven( 2 ) ) )

在 JS 中实现这个递归定义的方法之一是：

function maxEven(num1,...restNums) {
    var maxRest = restNums.length > 0 ?
            maxEven( ...restNums ) :
            undefined;
    return (num1 % 2 != 0 || num1 < maxRest) ?
        maxRest :
        num1;
}

那么这个方法有什么优点吗？

首先，参数与之前不一样了。我专门把第一个参数叫作 num1 ，剩余的其它参数放在一起叫作 restNums 。我们本可以把所有参数都放在 nums 数组中，并从 nums[0] 获取第一个参数。这是为什么呢？

函数的参数是专门为递归定义的。它看起来像这样：

maxEven( num1, ...restNums ):
    maxEven( num1, maxEven( ...restNums ) )

你有发现参数和递归之间的相似性吗？

当我们在函数体签名中进一步提升递归的定义，函数的声明也会得到提升。如果我们能够把递归的定义从参数反映到函数体中，那就更棒了。

但我想说最明显的改进是， for 循环造成的错乱感没有了。所有循环逻辑都被抽象为递归回调栈，所以这些东西不会造成代码混乱。我们可以轻松的把精力集中在一次比较两个数字来找到最大偶数值的逻辑中 —— 不管怎么说，这都是很重要的部分！

从思想上来讲，这如同一位数学家在更庞大的方程中使用 Σ 求和一样。我们说，“数列中剩余值的最大偶数是通过 maxEven(...restNums) 计算出来的，所以我们只需要继续推断这一部分。”

另外，我们用 restNums.length > 0 保证推断更加合理，因为当没有参数的情况下，返回的 maxRest 结果肯定是 undefined 。我们不需要对这部分的推理投入额外的精力。这个基本条件（没有参数情况下）显而易见。

接下来，我们把精力放在对比 num1 和 maxRest 上 —— 算法的主要逻辑是如何确定两个数字中的哪一个（如果有的话）是最大偶数。如果 num1 不是偶数（ num1 % 2 != 0 ），或着它小于 maxRest ，那么，即使 maxRest 的值是 undefined ， maxRest 会 return 掉。否则，返回结果会是 num1 。

在阅读整个实现过程中，与命令式的方法相比，我所做这个例子的推理过程更加直接，核心点更加突出，少做无用功；比 for 循环中引用 无穷数值 这一方法 更具有声明性 。

小贴士： 我们应该指出，除了手动迭代或递归之外，另一种（可能更好的）建模的方法是我们在在第7章中讨论的列表操作。我们先把数列中的偶数用 filter(..) 过滤出来，然后通过递归 reduce(..) 函数（对比两个数值并返回其中较大的数值）来找到最大值。在这里，我们只是使用这个例子来说明在手动迭代中递归的声明性更强。

还有一个递归的例子：计算二叉树的深度。二叉树的深度是指通过树的节点向下（左或右）的最长路径。还有另一种通过递归来定义的方式：任何树节点的深度为1（当前节点）加上来自其左侧或右侧子树的深度的最大值：

depth( node ):
    1 + max( depth( node.left ), depth( node.right ) )

直接转换为二分法递归函数：

function depth(node) {
    if (node) {
        let depthLeft = depth( node.left );