极客时间已完结课程限时免费阅读

12｜JS语义分析该用迭代还是递归？

12｜JS语义分析该用迭代还是递归？-极客时间

12｜JS语义分析该用迭代还是递归？

2022-10-15 石川 来自北京
《JavaScript进阶实战课》
课程介绍

讲述：石川

时长10:31大小9.65M

你好，我是石川。
在前面两讲中，我们学习了 JavaScript 语言的数据类型，通过堆栈的数据结构了解了闭包的原理。这一讲，我们来聊聊算法。前面我们在讲到编程模式时提到，如果说函数式编程是输入、计算和输出，那中间的计算部分就可能用到算法了。而迭代和递归可以说是非常基础的算法。
迭代相对比较好理解，只要用过 for loop 的话，你对它就不会太陌生，而递归比较难理解。但和闭包一样，一旦你掌握了它的运用技巧，就会体会到它的强大之处。
我们在讲到函数式编程的时候，也说过一个很重要的思想就是“副作用”，而递归就自带很多副作用，相应地也出现了很多的解决方案。今天，我们就来看看它都有哪些副作用，以及解决这些副作用我们可以用哪些方法。
那在这之前，我们先来看看迭代和递归分别是什么。

迭代和递归的区别

首先我们得搞清楚迭代和递归有什么区别？
先说迭代，举个例子。做过软件工程的同学都经历过迭代吧，如果是一个敏捷的项目，它的过程就是一个小步快跑的过程，功能不是一下子都做出来的，而是根据优先级，先做优先级高的，再做优先级低的。这就是一个通过循环往复不断完善的过程。
而递归呢，就好比我们寄快递。寄出去的过程是递，收到签收的回执就是归，但是这个过程中间可不只一个人，而是在寄出去的过程，是一个人先运到中转站，再有人运到联络处，最后才到我们手中。哪怕回去的回执是电子的，但在网络世界里，信息的传递也是需要经过每个节点。这样的一去一回就是递归。
而同样的一个问题，我们可能既可以用迭代的方式来做，也可以用递归的方式来做。
比如我们要计算阶乘。7 的阶乘是“7!”，等于 7 * 6 * 5 * 4 * 3 * 2 * 1，结果是 5040。如果用一个迭代函数来计算，大概是如下的方式。在每一次的迭代循环过程中，我们都用之前的乘积乘以下一个要迭代的 n 递减的数字。
function factorialIterative(number) {
if (number < 0) return undefined;
let total = 1;
for (let n = number; n > 1; n--) {
total = total * n;
}
return total;
}
console.log(factorialIterative(7)); // 5040
如果我们用递归的方式来解决会是什么样子呢？
在递归里面，通常有两个基本元素，一个是基本条件（base case），也叫做终止条件（stop point）；另外一个是递归本身。
现在我们可以看到，如果我们把上面的例子转变成递归的形式，即如下。在递归中调用的函数一般就是函数本身。
function factorialRecursive(n) {
// 基本条件
if (n === 1 || n === 0) {
return 1;
}
// 递归调用
return n * factorialRecursive(n - 1);
}
console.log(factorialRecursive(7)); // 5040
上面这段代码在执行中如下。我们可以看到前面 7 步，都是递的过程。在碰到基本条件后，开始了归的过程。

递归中用到的分治

下面我们再来用经典的斐波那契（Fibonacci Sequence）数列对比下迭代和递归。斐波那契数列的特点就是这个数列从第 3 项开始，每一项都等于前两项之和。按照这样的规则，到第 10 项的时候，相加的值应该是 55。
1，1，2，3，5，8，13，21，34，55
如果用迭代的方式来写计算第 n 项的斐波那契数的函数的话，大致如下：
function fibIterative(n) {
if (n < 1) return 0;
if (n <= 2) return 1;
let fibNMinus2 = 0;
let fibNMinus1 = 1;
let fibN = n;
// n >= 2
for (let i = 2; i <= n; i++) {
// f(n-1) + f(n-2)
fibN = fibNMinus1 + fibNMinus2;
fibNMinus2 = fibNMinus1;
fibNMinus1 = fibN;
}
return fibN;
}
console.log(fibIterative(10)); // 55
如果我们使用的是递归的话，从代码上看就简洁多了。在这里我们也使用了另外一个核心算法思想，就是分治（divide and conquer）。分治的意思就是分而治之。因为前面我们说了，斐波那契数列的特点就是这个数列从第 3 项开始，每一项都等于前两项之和。所以在这里，我们就先分别调用 fibRecursive(n - 1) 和 fibRecursive(n - 2) 这两个递归函数来分别计算前两项，之后我们再把它们相加，得到最终的结果。
function fibRecursive(n){
// 基本条件
if (n < 1) return 0;
// 基本条件
if (n <= 2) return 1;
// 递归+分治
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
console.log(fibRecursive(10)); // 55
但是这里有一个问题，当我们在计算 fibRecursive(5) 的时候，fibRecursive(3) 被计算了两次。
那么有没有什么办法，能够记住之前计算的结果，来避免这种重复的计算呢？

递归中的记忆函数

对了，我们可以利用上节课学到的作用域和闭包，在这里它又一次展示了它的强大。我们可以用闭包把递归函数中加入记忆（memoization）。在这里，fibonacci 是一个递归，但是我们让它调用了一个外部的 memo 参数，这样一来 memo 就带有了“记忆”。我们可以用它来存储上一次计算的值，就可以避免重复计算了。所以记忆函数经常和递归结合起来使用。这里解决的重复计算问题，在算法中也被称为重叠子问题，而记忆函数就是一个备忘录。
function fibMemo(n, memo = [0, 1, 1]) {
if (memo[n]) {
return memo[n];
}
// 递归+分治+闭包
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
console.log(fibMemo(10)); // 55

递归中的尾递归

在上面的例子里，我们可以看到它的时间复杂度是 。那有没有办法能够把时间和空间复杂度都降低到 呢？这里面我们可以看看尾递归。尾递归的意思就是在函数的尾部执行递归的调用。通过用尾递归的方式，最多递归 n 次，因为在每次递归的过程中都会 n-1。
function fibTailRecursive(n, lastlast, last){
if (n == 0) {
return lastlast;
}
if (n == 1) {
return last;
}
return fibTailRecursive(n-1, last, lastlast + last);
}
console.log(fibTailRecursive(10, 0, 1)); // 55

递归中的内存管理

在上一讲中，我们在了解闭包的原理的过程中也了解了函数调用栈的概念。在国外，有一个很有名的技术问答网站叫做 stack overflow，翻译成中文就是栈溢出。在我们用递归的时候，如果没有很好的控制，就会遇到这个性能问题。所以下面，我们再来看看递归中的内存管理。
在前面的例子中，我们看到在用递归来代替迭代的方案中，虽然它的写法比迭代要简便，但付出的是性能上的代价。因为这是一个函数不断自己调用自己的过程，会占用大量栈的空间，所以除了时间复杂度，它会有较高的空间复杂度需要考虑。而且稍有不慎，当它不能停止被调用的时候，可能会引起栈溢出。
比如在前面乘阶的例子中，我们可以在调用栈（call stack）中看到函数每次被调用的过程。
JavaScript 从 ES6 版本的标准开始，定义了尾调用优化。里面提到，如果一个函数是一个函数里的最后一个动作，它会被当做跳转而不是子程序来处理。也就是说这个代码会不停地被重复，所以这也是为什么要有一个基本条件的重要性。在实际操作中，绝大多数浏览器都会自己定义一个防止栈溢出的限制，比如 Chrome 在下面的一个无限循环的例子中调用了 13952 次之后，就出现了一个超出最大栈范围的错误消息，并且停止了递归。
let i = 0;
function recursiveFn() {
i++;
recursiveFn();
}
try {
recursiveFn();
} catch (ex) {
console.log('i = ' + i + ' error: ' + ex);
}

延伸：递归复杂度计算

在迭代中，Big-O 的分析相对简单，因为循环可以清楚地定义什么时候增加、减少或者停止。但是在分析递归的时候，我们就需要分析两个部分了，一个是基础条件，一个是递归。所以在做递归的复杂度计算，通常会用到主定理（master theorem）。我们先来看看这个定理的组成部分。
在这里面，n 是问题规模的大小，a 是子问题个数，n/b 是每个子问题的大小， 是将原问题分解和将子问题的解合并的时间。
基于 和 的对比，会有三种结果。 代表了 ，即解决当前层问题所需要的时间复杂度； 代表了 ，即将原问题分解和将子问题的解合并的时间。
当然我们说并不是所有递归问题都符合主定理公式的形式，那么遇到这种问题该怎么办呢？在这种情况下，我们也可以尝试使用递推公式和递归树。
下面，我们先来看看使用递推公式的方式。递推公式可以帮助我们在写递归的时候，设计递归函数。同时，它还有另外一个作用就是计算复杂度。如果我们用递推公式来计算斐波那契的时间复杂度的话，要先提炼出它的递推公式及时间复杂度的推导过程。这里，你可以看到，每一次函数调用会产生两次额外的调用，计算呈指数级增加。
// 斐波那契递推公式
T (n) = T (n − 1) + T (n − 2)
// 时间复杂度的推导
T(n) = T(n − 1) + T(n − 2) + O(1);
T(n − 1) = T(n − 2) + T(n − 3) + O(1);
T(n − 2) = T(n − 3) + T(n − 4) + O(1);
// 每次指数级的增加
f(6) * <-- 一次
f(5) *
f(4) **
f(3) ****
f(2) ********
f(1) **************** <-- 16
f(0) ******************************** <-- 32
上面通过递推公式计算复杂度的方式还是很复杂的，那么还有没有更简单直观的计算方式呢？我们来看看递归树。递归树的方式，我们可以更直观地看出结果。这里当长路径为 n 的话，对应的耗时为 ，所以最高的时间复杂就是 。

总结

这节课我们学习了算法中最核心的两种方法，迭代和递归。就和我们讲 JavaScript 编程范式的时候，讲到函数中的闭包和对象中的 this 一样，你会发现，我们后面讲到的 80% 算法都离不开它的影子。请记住这个二八定律，只要把迭代和递归的概念吃透搞明白，对算法的学习，可以说是有着事半功倍的效果。
如果要对比迭代和递归的话，从整体的性能来说，迭代是优于递归的。而如果从代码的整洁性来看，递归看起来更简洁。而且递归和作用域、闭包结合起来形成的记忆函数和尾递归，都能从一定程度上减少其“副作用”。下面我们就结合这张图，总结下针对这些副作用的解决方法吧。
所以在算法中我们应该用迭代还是递归呢？这里同样没有绝对，应用上，你可以根据它们的优劣势，结合实际情况来应用。我个人认为，我们写的代码主要还是给人读的，而不是最终的机器码。所以我的建议是以代码的“简洁可读性”为先，然后再针对机器无法替我们优化的“副作用”的部分所产生的问题做手动的优化。

思考题

前面我们讲到了针对栈溢出的尾调用优化，你知道尾递归调用优化是如何实现的吗？
期待在留言区看到你的分享，我们一起交流讨论。另外，也欢迎你把今天的内容分享给更多的朋友。
分享给需要的人，Ta购买本课程，你将得18元
生成海报并分享

赞 1

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
11｜通过JS引擎的堆栈了解闭包原理
下一篇
13 | JS引擎如何实现数组的稳定排序？
unpreview
 写留言

精选留言(2)

  • 卡卡
    2022-10-18 来自北京
    尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用记录，取代外层函数的调用记录就可以了。对于尾递归来说，由于只存在一个调用记录，所以永远不会发生"栈溢出"错误。

    作者回复: 很好的说明

    3
  • 穷精致
    2023-02-03 来自北京
    您好，我这边对尾调用代码进行debugger，在浏览器sourcemap的调用堆栈里，还是会保留外层函数的调用记录的，所以尾调用优化是什么呢？如何知道浏览器是不是开启了尾调用优化呢