递归和堆栈

让我们回到函数，并更深入地研究它们。

我们的第一个主题将是递归。

如果你不是编程新手，那么它可能很熟悉，你可以跳过本章。

递归是一种编程模式，当一个任务可以自然地分解成几个同类但更简单的任务时，它很有用。或者当一个任务可以简化为一个简单的动作加上一个更简单的同类任务变体时。或者，正如我们很快就会看到的，处理某些数据结构。

当一个函数解决一个任务时，在此过程中它可以调用许多其他函数。部分情况下，一个函数会调用自身。这称为递归。

两种思考方式

从简单的事情开始——让我们编写一个函数 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;
   
     // multiply result by x n times in the loop
     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. 否则，我们可以将 pow(x, n) 表示为 x * pow(x, n - 1)。在数学中，可以写成 xn = x * xn-1。这称为递归步骤：我们将任务转换为一个更简单的动作（乘以 x）和对同一任务的更简单的调用（pow，其中 n 较低）。下一步进一步简化，直到 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

因此，递归将函数调用简化为更简单的调用，然后简化为更简单的调用，依此类推，直到结果变得明显。

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

嵌套调用的最大数量（包括第一个调用）称为递归深度。在我们的例子中，它将恰好为 n。

最大递归深度受 JavaScript 引擎限制。我们可以依赖它为 10000，一些引擎允许更多，但 100000 可能超出大多数引擎的限制。有一些自动优化可以帮助缓解这种情况（“尾调用优化”），但它们尚未得到广泛支持，并且仅适用于简单的情况。

这限制了递归的应用，但它仍然非常广泛。在许多任务中，递归思维方式提供了更简单的代码，更易于维护。

执行上下文和堆栈

现在让我们研究递归调用如何工作。为此，我们将深入了解函数。

正在运行的函数的执行过程的信息存储在其执行上下文中。

执行上下文是一个内部数据结构，其中包含有关函数执行的详细信息：当前的控制流、当前变量、this 的值（我们在此处不使用它）和其他一些内部详细信息。

一个函数调用恰好有一个与其关联的执行上下文。

当函数进行嵌套调用时，将发生以下情况

• 当前函数暂停。
• 与其关联的执行上下文被记住在一个称为执行上下文堆栈的特殊数据结构中。
• 嵌套调用执行。
• 在它结束之后，从堆栈中检索旧的执行上下文，并且外部函数从它停止的地方恢复。

让我们看看在 pow(2, 3) 调用期间发生了什么。

pow(2, 3)

在调用 pow(2, 3) 的开始，执行上下文将存储变量：x = 2, n = 3，执行流在函数的第 1 行。

我们可以将其勾勒为

• 上下文：{ x: 2, n: 3, at line 1 } pow(2, 3)

那时函数开始执行。条件 n == 1 为假，因此流继续进入 if 的第二个分支

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) );

变量相同，但行发生变化，因此上下文现在是

• 上下文：{ x: 2, n: 3, at line 5 } pow(2, 3)

要计算 x * pow(x, n - 1)，我们需要使用新参数 pow(2, 2) 对 pow 进行子调用。

pow(2, 2)

为了进行嵌套调用，JavaScript 在执行上下文堆栈中记住当前执行上下文。

在这里，我们调用相同的函数 pow，但这绝对无关紧要。该过程对所有函数都是相同的

1. 当前上下文在堆栈的顶部被“记住”。
2. 为子调用创建新的上下文。
3. 当子调用完成时，将从堆栈中弹出先前的上下文，并且其执行继续。

当我们进入子调用 pow(2, 2) 时，这是上下文堆栈

• 上下文：{ x: 2, n: 2, 在第 1 行} pow(2, 2)
• 上下文：{ x: 2, n: 3, at line 5 } pow(2, 3)

新的当前执行上下文在顶部（加粗），之前记住的上下文在下面。

当我们完成子调用时，很容易恢复之前的上下文，因为它保留了变量和代码停止的确切位置。

pow(2, 1)

该过程重复：在第 5 行进行新的子调用，现在带有参数 x=2、n=1。

创建了一个新的执行上下文，将之前的执行上下文压入堆栈顶部

• 上下文：{ x: 2, n: 1, 在第 1 行} pow(2, 1)
• 上下文：{ x: 2, n: 2, 在第 5 行} pow(2, 2)
• 上下文：{ x: 2, n: 3, at line 5 } pow(2, 3)

现在有 2 个旧上下文和 1 个当前正在运行的 pow(2, 1)。

退出

在执行 pow(2, 1) 时，与之前不同，条件 n == 1 为真，因此 if 的第一个分支有效

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

没有更多嵌套调用，因此函数完成，返回 2。

当函数完成时，不再需要它的执行上下文，因此它从内存中删除。将之前的执行上下文从堆栈顶部恢复

• 上下文：{ x: 2, n: 2, 在第 5 行} pow(2, 2)
• 上下文：{ x: 2, n: 3, at line 5 } pow(2, 3)

恢复 pow(2, 2) 的执行。它具有子调用 pow(2, 1) 的结果，因此它还可以完成 x * pow(x, n - 1) 的求值，返回 4。

然后恢复之前的上下文

• 上下文：{ x: 2, n: 3, at line 5 } pow(2, 3)

当它完成时，我们得到 pow(2, 3) = 8 的结果。

在这种情况下，递归深度为：3。

从上面的插图中可以看出，递归深度等于堆栈中的最大上下文数。

注意内存需求。上下文占用内存。在我们的例子中，求 n 次方实际上需要 n 个上下文的内存，对于 n 的所有较低值。

基于循环的算法更省内存

function pow(x, n) {
  let result = 1;

  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

迭代 pow 使用单个上下文，在此过程中更改 i 和 result。它的内存需求很小，固定且不依赖于 n。

任何递归都可以重写为循环。循环变体通常可以变得更有效。

…但有时重写并非易事，尤其是在函数根据条件使用不同的递归子调用并合并其结果或分支更复杂时。并且优化可能是不必要的，完全不值得付出努力。

递归可以提供更短的代码，更容易理解和支持。并非所有地方都需要优化，我们大多数时候需要的是良好的代码，这就是它被使用的原因。

递归遍历

递归的另一个伟大应用是递归遍历。

想象一下，我们有一家公司。员工结构可以表示为一个对象

let company = {
  sales: [{
    name: 'John',
    salary: 1000
  }, {
    name: 'Alice',
    salary: 1600
  }],

  development: {
    sites: [{
      name: 'Peter',
      salary: 2000
    }, {
      name: 'Alex',
      salary: 1800
    }],

    internals: [{
      name: 'Jack',
      salary: 1300
    }]
  }
};

换句话说，一家公司有部门。

• 一个部门可能有一个员工数组。例如，sales 部门有 2 名员工：John 和 Alice。

• 或者一个部门可能分为子部门，比如 development 有两个分支：sites 和 internals。它们各自有自己的员工。

• 当一个子部门发展壮大时，也有可能将其划分为子子部门（或团队）。

  例如，sites 部门将来可能会分为 siteA 和 siteB 团队。而且它们有可能进一步细分。这不在图片中，只是需要记住的事情。

现在，假设我们想要一个函数来获得所有工资的总和。我们如何做到这一点？

迭代方法并不容易，因为结构并不简单。第一个想法可能是对 company 进行 for 循环，并对第一级部门进行嵌套子循环。但是，然后我们需要更多嵌套子循环来迭代第二级部门（如 sites）中的员工……然后在未来可能出现的第三级部门中再进行另一个子循环？如果我们在代码中放置 3-4 个嵌套子循环来遍历单个对象，它会变得相当难看。

我们尝试递归。

正如我们所看到的，当我们的函数获得一个要汇总的部门时，有两种可能的情况

1. 要么它是一个带有员工数组的“简单”部门——然后我们可以在一个简单的循环中对工资求和。
2. 要么它是一个带有 N 个子部门的对象——然后我们可以进行 N 个递归调用来获得每个子部门的总和，并将结果组合起来。

第一种情况是递归的基础，当我们得到一个数组时，这是平凡的情况。

当我们得到一个对象时的第二种情况是递归步骤。一个复杂的任务被分解为较小部门的子任务。它们可能反过来再次分解，但迟早分解将在 (1) 处结束。

该算法可能从代码中更容易读取

let company = { // the same object, compressed for brevity
  sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 1600 }],
  development: {
    sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
    internals: [{name: 'Jack', salary: 1300}]
  }
};

// The function to do the job
function sumSalaries(department) {
  if (Array.isArray(department)) { // case (1)
    return department.reduce((prev, current) => prev + current.salary, 0); // sum the array
  } else { // case (2)
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // recursively call for subdepartments, sum the results
    }
    return sum;
  }
}

alert(sumSalaries(company)); // 7700

代码很短，很容易理解（希望如此？）。这就是递归的力量。它也适用于任何级别的子部门嵌套。

以下是调用图

我们可以轻松地看到原理：对于对象 {...} 进行子调用，而数组 [...] 是递归树的“叶子”，它们给出立即结果。

请注意，代码使用了我们之前介绍过的智能功能

• 方法 arr.reduce 在章节 数组方法 中进行了说明，用于获取数组的总和。
• 循环 for(val of Object.values(obj)) 用于遍历对象值：Object.values 返回一个数组。

递归结构

递归（递归定义）数据结构是一种在部分中复制自身结构。

我们刚刚在上面的公司结构示例中看到了它。

一家公司的部门是

• 一个人员数组。
• 或者一个具有部门的对象。

对于 Web 开发人员来说，还有更著名的示例：HTML 和 XML 文档。

在 HTML 文档中，HTML 标签可能包含以下列表

• 文本片段。
• HTML 注释。
• 其他HTML 标签（反过来可能包含文本片段/注释或其他标签等）。

这又一次是一个递归定义。

为了更好地理解，我们将介绍另一个名为“链表”的递归结构，在某些情况下它可能是数组更好的替代方案。

链表

想象一下，我们要存储一个有序的对象列表。

自然的选择将是一个数组

let arr = [obj1, obj2, obj3];

…但数组存在问题。“删除元素”和“插入元素”操作很昂贵。例如，arr.unshift(obj) 操作必须对所有元素重新编号以容纳新的 obj，如果数组很大，则需要时间。arr.shift() 也是如此。

不需要大量重新编号的唯一结构修改是对数组末尾进行的操作：arr.push/pop。因此，当我们必须处理开头时，对于大型队列，数组可能会非常慢。

或者，如果我们确实需要快速插入/删除，我们可以选择另一种称为 链表 的数据结构。

链表元素递归定义为具有以下内容的对象

• 值.
• next 属性引用下一个链表元素或 null（如果这是结尾）。

例如

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

列表的图形表示

用于创建的备用代码

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };
list.next.next.next.next = null;

在这里，我们可以更清楚地看到有多个对象，每个对象都有指向邻居的 value 和 next。list 变量是链中的第一个对象，因此从它跟踪 next 指针，我们可以到达任何元素。

列表可以轻松地分成多个部分，然后重新连接

let secondList = list.next.next;
list.next.next = null;

加入

list.next.next = secondList;

当然，我们可以在任何位置插入或移除项目。

例如，要添加一个新值，我们需要更新列表的头部

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };

// prepend the new value to the list
list = { value: "new item", next: list };

要从中间移除一个值，更改前一个值的next

list.next = list.next.next;

我们让list.next跳过1到值2。值1现在从链中排除。如果它没有存储在其他任何地方，它将自动从内存中移除。

与数组不同，没有大规模重新编号，我们可以轻松地重新排列元素。

当然，列表并不总是比数组好。否则，每个人都只会使用列表。

主要缺点是，我们无法通过其编号轻松访问元素。在数组中，这很容易：arr[n]是一个直接引用。但在列表中，我们需要从第一个项目开始，并nextN次才能获得第 N 个元素。

…但我们并不总是需要这样的操作。例如，当我们需要一个队列甚至一个双端队列时——有序结构必须允许从两端非常快速地添加/移除元素，但不需要访问其中间。

列表可以增强

• 除了next之外，我们还可以添加属性prev来引用前一个元素，以便轻松返回。
• 我们还可以添加一个名为tail的变量，引用列表的最后一个元素（并在从末尾添加/移除元素时更新它）。
• …数据结构可能会根据我们的需要而有所不同。

总结

术语

• 递归是一个编程术语，表示从自身调用函数。递归函数可以用来以优雅的方式解决任务。

  当一个函数调用自身时，称为递归步骤。递归的基础是函数参数，这些参数使任务变得非常简单，以至于函数不会进行进一步的调用。

• 一个递归定义的数据结构是一个可以使用自身定义的数据结构。

  例如，链表可以定义为一个包含引用列表（或 null）的对象的数据结构。

  list = { value, next -> list }

  像 HTML 元素树或本章中的部门树这样的树也是自然递归的：它们有分支，每个分支都可以有其他分支。

  递归函数可以用来遍历它们，正如我们在sumSalary示例中看到的那样。

任何递归函数都可以重写为迭代函数。有时需要这样做来优化内容。但对于许多任务来说，递归解决方案足够快，而且更容易编写和支持。