递归

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

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

两种思考方式

简单起见,我们写一个函数 pow(x, n),它可以计算 xn 次方,即用 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 的乘法)和更简单的同类任务调用(更小的 npow)。后面步骤继续简化直到 n 等于 1

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

recursive diagram of pow

比如,为了计算 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 很可能就超过了限制。有一些自动优化能够缓解这个(「尾部调用优化」),但是它们还没有被完全支持,只能用于简单场景。

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

递归算法的秘诀

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

文档更新时间: 2022-06-29 14:08   作者:张老师