递归和堆栈

我们回到函数,深入研究一下。

我们的第一个主题是递归

如果你不是刚接触编程,那么你可能已经很熟悉它,可以跳过这一章了。

递归是一种编程模式,用于一个任务可以被分割为多个相似的更简单的任务的场景。或者用于一个任务可以被简化为一个容易的行为加上更简单的任务变体。或者像我们随后会看到的,用来处理特定类型的数据结构。

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

两种思考方式

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

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

有两种实现方式。

  1. 迭代思路:for 循环:

    run
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    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. 递归思路:简化任务,调用自身:

    run
    1
    2
    3
    4
    5
    6
    7
    8
    9
    function pow(x, n) {
    if (n == 1) {
    return x;
    } else {
    return x * pow(x, n - 1);
    }
    }

    alert( pow(2, 3) ); // 8

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

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

1
2
3
4
5
              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