栈

我们需要对栈的工作原理有一个基本的了解，才能理解下一节内容。如果你从未听说过栈这种数据结构，我将在本节中对其进行简要介绍。但我仍然建议你在继续之前进行更深入的研究，因为这在你的编程生涯中非常重要。

想象一下，栈就像一个 JavaScript 数组，但其中的元素无法直接访问。假设有一个栈 S，你只能对它执行以下操作：

• S.length：检查栈的长度
• S.push(element)：将一个元素压入栈中
• S.pop()：移除栈顶元素并返回它

你无法访问或修改栈中除位置 S.length - 1 外的任何元素。在练习 1 中，你将有机会使用 ES6 实现一个栈。

你有两种可用的内存类型：栈 和 堆。堆用于动态内存分配，而栈用于静态内存分配。访问栈的速度非常快，但栈的大小是固定的。

每个程序运行时都会创建一个用于全局作用域的栈帧。每当调用一个函数时，就会在栈顶添加一个新的栈帧。这些栈帧依次叠加在一起。

在执行 JavaScript 代码时，你拥有的是一个大小有限的栈。为了了解实际中典型的栈大小限制，可以参考 这个页面。

无论使用哪种浏览器，从 0 迭代到一百万的 for 循环都很容易完成。

1console.time('for loop');
2let sum = 0;
3for (let i = 0; i < 1000000; ++i) {
4    sum += i;
5}
6console.timeEnd('for loop');
7// for loop: 119.11ms

但同样的迭代如果通过递归实现，则会变得非常困难，大多数浏览器都无法完成，因为栈空间已达到上限。虽然执行速度很快，但由于栈的限制，无法完成一百万次递归调用。

1function sumToN(n) {
2    if (n <= 1) return n;
3    return n + sumToN(n - 1);
4}
5
6console.time('recursion');
7console.log(sumToN(1000000));
8console.timeEnd('recursion');

让我们分析以下程序在栈上的执行过程：

1function sumToN(n) {
2    if (n <= 1) return n;
3    return n + sumToN(n - 1);
4}
5
6console.log(sumToN(2));

1. 最初，在全局栈帧中创建对 sumToN 函数的引用。

2. 当调用 sumToN(2) 时，创建一个新的栈帧，包含变量 n 的值、预期的返回值以及对 sumToN 的引用。

3. 当调用 sumToN(1) 时，再创建一个栈帧，包含新的 n 值、预期返回值以及对 sumToN 的引用。

4. 当 sumToN 返回值 1 后，最后一个栈帧被销毁。

5. 当 sumToN(2) 的计算完成后，步骤 (2) 创建的栈帧也被销毁。

当栈深度超过五位数时，程序执行将停止，并抛出 JavaScript 错误。我们将通过尾调用优化来解决这一问题。