递归

在之前的章节中，我们学习了不同的可迭代数据结构。从下一章开始，我们要使用一种特殊 的方法使操作树和图数据结构变得更简单，那就是递归。但是学习树和图之前，我们需要先理解 递归是如何工作的。 本章内容包括：  理解递归  计算一个数的阶乘  斐波那契数列  JavaScript 调用栈 9.1 理解递归 有一句编程的至理名言是这样的： “要理解递归，首先要理解递归。” ——佚名 递归是一种解决问题的方法，它从解决问题的各个小部分开始，直到解决最初的大问题。递 归通常涉及函数调用自身。 递归函数是像下面这样能够直接调用自身的方法或函数。 function recursiveFunction(someParam){ recursiveFunction(someParam); } 能够像下面这样间接调用自身的函数，也是递归函数。 function recursiveFunction1(someParam){ recursiveFunction2(someParam); 第9章 162 第 9 章 递归 } function recursiveFunction2(someParam){ recursiveFunction1(someParam); } 假设现在必须要执行 recursiveFunction，结果是什么？单就上述情况而言，它会一直执 行下去。因此，每个递归函数都必须有基线条件，即一个不再递归调用的条件（停止点），以防 止无限递归。 回到之前的编程至理名言，在理解了什么是递归之后，我们也就解决了最初的问题。如果我 们把这句话翻译成 JavaScript 代码的话，可以写成下面这样。 function understandRecursion(doIunderstandRecursion) { const recursionAnswer = confirm('Do you understand recursion?'); if (recursionAnswer === true) { // 基线条件或停止点 return true; } understandRecursion(recursionAnswer); // 递归调用 } understandRecursion 函数会不断地调用自身，直到 recursionAnswer 为真（true）。 recursionAnswer 为真就是上述代码的基线条件。 下面来看看一些著名的递归算法。 9.2 计算一个数的阶乘 作为递归的第一个例子，我们来看看如何计算一个数的阶乘。数 n 的阶乘，定义为 n!，表示 从 1 到 n 的整数的乘积。 5 的阶乘表示为 5!，和 5 × 4 × 3 × 2 × 1 相等，结果是 120。 9.2.1 迭代阶乘 如果尝试表示计算任意数 n 的阶乘的步骤，可以将步骤定义如下：(n) * (n - 1) * (n - 2) * (n - 3) * ... * 1。 可以使用循环来写一个计算一个数阶乘的函数，如下所示。 function factorialIterative(number) { if (number < 0) return undefined; let total = 1; for (let n = number; n > 1; n--) { total = total * n; } 9.2 计算一个数的阶乘 163 1 2 3 4 5 5 6 7 8 9 0 1 2 3 4 return total; } console.log(factorialIterative(5)); // 120 我们可以从给定的 number 开始计算阶乘，并减少 n，直到它的值为 2，因为 1 的阶乘还是 1， 而且它已经被包含在 total 变量中了。零的阶乘也是 1。负数的阶乘不会被计算。 9.2.2 递归阶乘 现在我们试着用递归来重写 factorialIterative 函数，但是首先使用递归的定义来定义 所有的步骤。 5 的阶乘用 5 × 4 × 3 × 2 × 1 来计算。4(n  1)的阶乘用 4 × 3 × 2 × 1 来计算。计算 n  1 的阶 乘是我们计算原始问题 n!的一个子问题，因此可以像下面这样定义 5 的阶乘。 (1) factorial(5) = 5 * factorial(4)：我们可以用 5 × 4!来计算 5!。 (2) factorial(5) = 5 * (4 * factorial(3))：我们需要计算子问题 4!，它可以用 4 × 3! 来计算。 (3) factorial(5) = 5 * 4 * (3 * factorial(2))：我们需要计算子问题 3!，它可以 用 3 × 2!来计算。 (4) factorial(5) = 5 * 4 * 3 * (2 * factorial(1))：我们需要计算子问题 2!，它 可以用 2 × 1!来计算。 (5) factorial(5) = 5 * 4 * 3 * 2 * (1)：我们需要计算子问题 1!。 (6) factorial(1)或 factorial(0)返回 1。1!等于 1。我们也可以说 1! = 1 × 0!，0!也等于 1。 使用递归的 factorial 函数定义如下。 function factorial(n) { if (n === 1 || n === 0) { // 基线条件 return 1; } return n * factorial(n - 1); // 递归调用 } console.log(factorial(5)); // 120

1. 调用栈 我们在第 4 章学习了栈数据结构。我们来看看在实际应用中用递归形式使用它的例子。每当 一个函数被一个算法调用时，该函数会进入调用栈的顶部。当使用递归的时候，每个函数调用都 会堆叠在调用栈的顶部，这是因为每个调用都可能依赖前一个调用的结果。 我们可以用浏览器看到调用栈的行为，如下图所示。 164 第 9 章 递归 如果执行 factorial(3)，打开浏览器的开发者工具，打开 Sources 标签页，在 Factorial.js 文件中增加一个断点，当 n 的值为 1 时，我们可以看到 Call Stack 里有三个 factorial 函数的调 用。如果继续执行，会看到当 factorial(1)被返回后，Call Stack 开始弹出 factorial 的调用。 我们也可以在函数开头添加 console.trace()来在浏览器的控制台中查看结果。 function factorial(n) { console.trace(); // 函数逻辑 } 当 factorial(3)被调用时，我们能在控制台中得到下面的结果。 factorial @ 02-Factorial.js:18 (anonymous) @ 02-Factorial.js:25 // console.log(factorial(3))调用 当 factorial(2)被调用时，我们能在控制台中得到下面的结果。 factorial @ 02-Factorial.js:18 factorial @ 02-Factorial.js:22 // factorial(3)在等待 factorial(2) (anonymous) @ 02-Factorial.js:25 // console.log(factorial(3))调用 最后，当 factorial(1)被调用时，我们能在控制台中得到下面的结果。 factorial @ 02-Factorial.js:18 factorial @ 02-Factorial.js:22 // factorial(2)在等待 factorial(1) factorial @ 02-Factorial.js:22 // factorial(3)在等待 factorial(2) (anonymous) @ 02-Factorial.js:25 // console.log(factorial(3))调用 下图展示了执行的各个步骤和调用栈中的行为。 9.3 斐波那契数列 165 1 2 3 4 5 5 6 7 8 9 0 1 2 3 4 当 factorial(1)返回 1 时，调用栈会开始弹出调用，返回结果，直到 3 * factorial(2) 被计算。
2. JavaScript 调用栈大小的限制 如果忘记加上用以停止函数递归调用的基线条件，会发生什么呢？递归并不会无限地执行下 去，浏览器会抛出错误，也就是所谓的栈溢出错误（stack overflow error）。 每个浏览器都有自己的上限，可用以下代码测试。 let i = 0; function recursiveFn() { i++; recursiveFn(); } try { recursiveFn(); } catch (ex) { console.log('i = ' + i + ' error: ' + ex); } 在 Chrome v65 中，该函数执行了 15 662 次，而后浏览器抛出错误 RangeError: Maximum call stack size exceeded（超限错误：超过最大调用栈大小）。在 Firefox v59 中，该函数 执行了 188 641 次，然后浏览器抛出错误 InternalError: too much recursion（内部错误： 递归次数过多）。在 Edge v41 中，该函数执行了 17 654 次。 根据操作系统和浏览器的不同，具体数值会所有不同，但区别不大。 ECMAScript 2015 有尾调用优化（tail call optimization）。如果函数内的最后一个操作是调用 函数（就像示例中加粗的那行），会通过“跳转指令”（jump）而不是“子程序调用”（subroutine call）来控制。也就是说，在 ECMAScript 2015 中，这里的代码可以一直执行下去。因此，具有 停止递归的基线条件非常重要。 有关尾调用优化的更多相关信息，请访问 https://www.chromestatus.com/feature/ 5516876633341952。 9.3 斐波那契数列 斐波那契数列是另一个可以用递归解决的问题。它是一个由 0、1、1、2、3、5、8、13、21、 34 等数组成的序列。数 2 由 1 + 1 得到，数 3 由 1 + 2 得到，数 5 由 2 + 3 得到，以此类推。斐波 那契数列的定义如下。 166 第 9 章 递归  位置 0 的斐波那契数是零。  1 和 2 的斐波那契数是 1。  n（此处 n > 2）的斐波那契数是（n  1）的斐波那契数加上（n  2）的斐波那契数。 9.3.1 迭代求斐波那契数 我们用迭代的方法实现了 fibonacci 函数，如下所示。 function fibonacciIterative(n) { if (n < 1) return 0; if (n <= 2) return 1; let fibNMinus2 = 0; let fibNMinus1 = 1; let fibN = n; for (let i = 2; i <= n; i++) { // n >= 2 fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2) fibNMinus2 = fibNMinus1; fibNMinus1 = fibN; } return fibN; } 9.3.2 递归求斐波那契数 fibonacci 函数可以写成下面这样。 function fibonacci(n){ if (n < 1) return 0; // {1} if (n <= 2) return 1; // {2} return fibonacci(n - 1) + fibonacci(n - 2); // {3} } 在上面的代码中，有基线条件（行{1}和行{2}）以及计算 n > 2 的斐波那契数的逻辑（行{3}）。 如果我们试着寻找 fibonacci(5)，下面是调用情况的结果。 图灵社区会员 道法小自然(903567778@qq.com) 专享 尊重版权 9.4 为什么要用递归？它更快吗 167 1 2 3 4 5 5 6 7 8 9 0 1 2 3 4 9.3.3 记忆化斐波那契数 还有第三种写 fibonacci 函数的方法，叫作记忆化。记忆化是一种保存前一个结果的值的 优化技术，类似于缓存。如果我们分析在计算 fibonacci(5)时的调用，会发现 fibonacci(3) 被计算了两次，因此可以将它的结果存储下来，这样当需要再次计算它的时候，我们就已经有它 的结果了。 下面的代码展示了使用记忆化的 fibonacci 函数。 function fibonacciMemoization(n) { const memo = [0, 1]; // {1} const fibonacci = (n) => { if (memo[n] != null) return memo[n]; // {2} return memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo); // {3} }; return fibonacci; } 在上面的代码中，我们声明了一个 memo 数组来缓存所有的计算结果（行{1}）。如果结果已 经被计算了，我们就返回它（行{2}），否则计算该结果并将它加入缓存（行{3}）。 9.4 为什么要用递归？它更快吗 我们运行一个检测程序来测试本章三种不同的 fibonacci 函数。 迭代的版本比递归的版本快很多，所以这表示递归更慢。但是，再看看三个不同版本的代码。 递归版本更容易理解，需要的代码通常也更少。另外，对一些算法来说，迭代的解法可能不可用， 而且有了尾调用优化，递归的多余消耗甚至可能被消除。 所以，我们经常使用递归，因为用它来解决问题会更简单。 图灵社区会员 道法小自然(903567778@qq.com) 专享 尊重版权 168 第 9 章 递归 9.5 小结 本章，我们学习了怎样写两种著名算法的迭代版本和递归版本：数的阶乘和斐波那契数列。 我们学习了一种叫作记忆化的优化技术，它可以防止递归算法重复计算一个相同的值。 我们还比较了斐波那契算法的迭代版本和递归版本的性能，了解了尽管迭代版本可能更快， 但是递归算法会使人更容易阅读和理解它正在做什么。 在下一章，我们将会学习树数据结构。我们会创建 Tree 类，而它的大部分方法会使用递归。