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

你好，我是石川。

在前面两讲中，我们学习了JavaScript语言的数据类型，通过堆栈的数据结构了解了闭包的原理。这一讲，我们来聊聊算法。前面我们在讲到编程模式时提到，如果说函数式编程是输入、计算和输出，那中间的计算部分就可能用到算法了。而迭代和递归可以说是非常基础的算法。

迭代相对比较好理解，只要用过for loop的话，你对它就不会太陌生，而递归比较难理解。但和闭包一样，一旦你掌握了它的运用技巧，就会体会到它的强大之处。

我们在讲到函数式编程的时候，也说过一个很重要的思想就是“副作用”，而递归就自带很多副作用，相应地也出现了很多的解决方案。今天，我们就来看看它都有哪些副作用，以及解决这些副作用我们可以用哪些方法。

那在这之前，我们先来看看迭代和递归分别是什么。

## 迭代和递归的区别

首先我们得搞清楚迭代和递归有什么区别？

先说迭代，举个例子。做过软件工程的同学都经历过迭代吧，如果是一个敏捷的项目，它的过程就是一个小步快跑的过程，功能不是一下子都做出来的，而是根据优先级，先做优先级高的，再做优先级低的。这就是一个通过循环往复不断完善的过程。

而递归呢，就好比我们寄快递。寄出去的过程是递，收到签收的回执就是归，但是这个过程中间可不只一个人，而是在寄出去的过程，是一个人先运到中转站，再有人运到联络处，最后才到我们手中。哪怕回去的回执是电子的，但在网络世界里，信息的传递也是需要经过每个节点。这样的一去一回就是递归。

![图片](assets/ea68479c41444e39ac6f6c8370edc220.jpg)

而同样的一个问题，我们可能既可以用迭代的方式来做，也可以用递归的方式来做。

比如我们要计算阶乘。7的阶乘是“7!”，等于 7 * 6 * 5 * 4 * 3 * 2 * 1，结果是5040。如果用一个迭代函数来计算，大概是如下的方式。在每一次的迭代循环过程中，我们都用之前的乘积乘以下一个要迭代的 n 递减的数字。

```javascript
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）；另外一个是**递归本身**。

现在我们可以看到，如果我们把上面的例子转变成递归的形式，即如下。在递归中调用的函数一般就是函数本身。

```javascript
function factorialRecursive(n) {
  // 基本条件
  if (n === 1 || n === 0) {
    return 1;
  }
  // 递归调用
  return n * factorialRecursive(n - 1);
}
console.log(factorialRecursive(7)); // 5040
```

上面这段代码在执行中如下。我们可以看到前面7步，都是递的过程。在碰到基本条件后，开始了归的过程。

![图片](assets/a6af95a1f9ad4dca8705af60960f84fd.jpg)

## 递归中用到的分治

下面我们再来用经典的斐波那契（Fibonacci Sequence）数列对比下迭代和递归。斐波那契数列的特点就是这个数列从第3项开始，每一项都等于前两项之和。按照这样的规则，到第10项的时候，相加的值应该是55。

```javascript
1，1，2，3，5，8，13，21，34，55
```

如果用迭代的方式来写计算第n项的斐波那契数的函数的话，大致如下：

```javascript
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)这两个递归函数来分别计算前两项，之后我们再把它们相加，得到最终的结果。

```javascript
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)被计算了两次。

![图片](assets/be024d34af884cdd8f1e8811ff0c13af.jpg)

那么有没有什么办法，能够记住之前计算的结果，来避免这种重复的计算呢？

## 递归中的记忆函数

对了，我们可以利用上节课学到的作用域和闭包，在这里它又一次展示了它的强大。我们可以用闭包把递归函数中加入记忆（memoization）。在这里，fibonacci是一个递归，但是我们让它调用了一个外部的memo参数，这样一来memo就带有了“记忆”。我们可以用它来存储上一次计算的值，就可以避免重复计算了。所以**记忆函数经常和递归结合起来使用**。这里解决的重复计算问题，在算法中也被称为重叠子问题，而记忆函数就是一个备忘录。

```javascript
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
```

## 递归中的尾递归

在上面的例子里，我们可以看到它的时间复杂度是\(O(2^{n})\)。那有没有办法能够把时间和空间复杂度都降低到\(O(n)\)呢？这里面我们可以看看尾递归。尾递归的意思就是在函数的尾部执行递归的调用。通过用尾递归的方式，最多递归n次，因为在每次递归的过程中都会n-1。

```javascript
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）中看到函数每次被调用的过程。

![图片](assets/9dec773312c946b59aec5d24da199acb.jpg)

JavaScript从ES6版本的标准开始，定义了尾调用优化。里面提到，如果一个函数是一个函数里的最后一个动作，它会被当做跳转而不是子程序来处理。也就是说这个代码会不停地被重复，所以这也是为什么要有一个基本条件的重要性。在实际操作中，绝大多数浏览器都会自己定义一个防止栈溢出的限制，比如Chrome在下面的一个无限循环的例子中调用了13952次之后，就出现了一个超出最大栈范围的错误消息，并且停止了递归。

```javascript
let i = 0;
function recursiveFn() {
  i++;
  recursiveFn();
}
try {
  recursiveFn();
} catch (ex) {
  console.log('i = ' + i + ' error: ' + ex);
}
```

![图片](assets/2226a9f624724534966a4439f4051cda.jpg)

## 延伸：递归复杂度计算

在迭代中，Big-O的分析相对简单，因为循环可以清楚地定义什么时候增加、减少或者停止。但是在分析递归的时候，我们就需要分析两个部分了，一个是基础条件，一个是递归。所以在做递归的复杂度计算，通常会用到**主定理（master theorem）**。我们先来看看这个定理的组成部分。

在这里面，n是问题规模的大小，a是子问题个数，n/b是每个子问题的大小，\(O(n^{c})\)是将原问题分解和将子问题的解合并的时间。

\[T(n) = aT(n/b)+O(n^{c})\]

基于\(c\)和\(log\_{b}(a)\)的对比，会有三种结果。\(log\_{b}(a)\)代表了\(aT(n/b)\)，即解决当前层问题所需要的时间复杂度；\(c\)代表了\(O(n^{c})\)，即将原问题分解和将子问题的解合并的时间。

![图片](assets/326ac4f97c0d41eaa7b9d178bd7a0ac6.jpg)

当然我们说并不是所有递归问题都符合主定理公式的形式，那么遇到这种问题该怎么办呢？在这种情况下，我们也可以尝试使用**递推公式**和**递归树**。

下面，我们先来看看使用递推公式的方式。递推公式可以帮助我们在写递归的时候，设计递归函数。同时，它还有另外一个作用就是计算复杂度。如果我们用递推公式来计算斐波那契的时间复杂度的话，要先提炼出它的递推公式及时间复杂度的推导过程。这里，你可以看到，每一次函数调用会产生两次额外的调用，计算呈指数级增加。

```typescript
// 斐波那契递推公式
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的话，对应的耗时为\(2^{n}-1\)，所以最高的时间复杂就是\(2^{n}\)。

![图片](assets/b45d53a71f0c40608b7aca73993ae18f.jpg)

## 总结

这节课我们学习了算法中最核心的两种方法，迭代和递归。就和我们讲JavaScript编程范式的时候，讲到函数中的闭包和对象中的this一样，你会发现，我们后面讲到的80%算法都离不开它的影子。请记住这个**二八定律**，只要把迭代和递归的概念吃透搞明白，对算法的学习，可以说是有着事半功倍的效果。

如果要对比迭代和递归的话，从整体的性能来说，迭代是优于递归的。而如果从代码的整洁性来看，递归看起来更简洁。而且递归和作用域、闭包结合起来形成的记忆函数和尾递归，都能从一定程度上减少其“副作用”。下面我们就结合这张图，总结下针对这些副作用的解决方法吧。

![图片](assets/91c188e1ae014dc78b95c95bdea8b9b9.jpg)

所以在算法中我们应该用迭代还是递归呢？这里同样没有绝对，应用上，你可以根据它们的优劣势，结合实际情况来应用。我个人认为，我们写的代码主要还是给人读的，而不是最终的机器码。所以我的建议是以代码的“**简洁可读性**”为先，然后再针对机器无法替我们优化的“副作用”的部分所产生的问题做手动的优化。

## 思考题

前面我们讲到了针对栈溢出的尾调用优化，你知道尾递归调用优化是如何实现的吗？

期待在留言区看到你的分享，我们一起交流讨论。另外，也欢迎你把今天的内容分享给更多的朋友。
