6. 递归

递归

递归是一种编程模式，用于一个任务可以被分割为多个相似的更简单的任务的场景。

当一个函数解决一个任务时，在该过程中它可以调用很多其它函数。那么当一个函数调用自身时，就称其为递归。

1. 两种思考方式

简单起见，我们写一个函数 pow(x, n)，它可以计算 x 的 n 次方，即用 x 乘以自身 n 次。

pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16

有两种实现方式。

1. 迭代思路：for 循环：

   function pow(x, n) {
       let result = 1;
   
       // 在循环中用 x 乘以 result
       for (let i = 0; i < n; i++) {
           result *= x;
       }
   
       return result;
   }
   
   alert(pow(2, 3)); // 8
   

2. 递归思路：简化任务，调用自身：

   function pow(x, n) {
       if (n == 1) {
           return x;
       } else {
           return x * pow(x, n - 1);
       }
   }
   
   alert(pow(2, 3)); // 8

注意递归方式完全不相同。

当 pow(x, n) 被调用时，执行分为两个分支：

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)

1. 如果 n == 1，所有事情都会很简单，这叫做递归的基础(跳出条件)，因为它立即得到显而易见的结果：pow(x, 1) 等于 x。
2. 否则，我们可以用 x * pow(x, n - 1) 表示 pow(x, n)。在数学里，可能会这么写 xn = x * xn-1。这叫做一个递归步骤：我们将任务转变为更简单的行为（x 的乘法）和更简单的同类任务调用（更小的 n 给 pow）。后面步骤继续简化直到 n 等于 1。

我们也可以说 pow 递归的调用自身 直到 n == 1。

比如，为了计算 pow(2, 4)，递归变体经过了下面几个步骤：

1. pow(2, 4) = 2 * pow(2, 3)
2. pow(2, 3) = 2 * pow(2, 2)
3. pow(2, 2) = 2 * pow(2, 1)
4. pow(2, 1) = 2

所以，递归生成了更简单的函数调用，然后 —— 更加简单，继续，直到结果变得很明显。

“递归一般更简洁”

递归解决方案一般比迭代更简洁。

这里我们可以使用三元运算符 ? 来替换 if 语句，从而让 pow(x, n) 更简洁并且可读性依然很高：

function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

最大的嵌套调用次数（包括首次）称为递归深度。在我们的例子中，它正好等于 n。

最大递归深度受限于 JavaScript 引擎。我们可以确信基本是 10000，有些引擎可能允许更大，但是 100000 很可能就超过了限制。有一些自动优化能够缓解这个（「尾部调用优化」），但是它们还没有被完全支持，只能用于简单场景。

这就限制了递归的应用，但是递归仍然被广泛使用。有很多任务使用递归思路会让代码更简单，更容易维护。

2. 递归算法的秘诀

写递归算法的关键是要明确函数的「定义/作用」是什么，然后相信这个定义，利用这个定义推导最终结果，绝不要跳入递归的细节。