- 链表
当我们需要存储一个有序的对象子列表时，首先想到的是数组，但是对于大型数据来说删除和插入使用shift和unshift会很耗时操作代价非常大，因为他们必须对所有元素重新编号，唯一使用的快速的是在末尾添加，但是有时必须在首位添加时，引出另一个数据结构--链表
队列-两头同的管道，先进先出
栈-放在桌子上的卡牌，后进先出
递归
递归是一种编程模式，在一个任务可以自然地拆分成多个相同类型但更简单的任务的情况下非常有用。或者，在一个任务可以简化为一个简单的行为加上该任务的一个更简单的变体的时候可以使用。或者，就像我们很快会看到的那样，处理某些数据结构。
当一个函数解决一个任务时，在解决的过程中它可以调用很多其它函数。在部分情况下，函数会调用 自身。这就是所谓的 递归。
- 两种思考方式
简单起见，让我们写一个函数 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 n 次
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)，递归变体经过了下面几个步骤：
pow(2, 4) = 2 * pow(2, 3)
pow(2, 3) = 2 * pow(2, 2)
pow(2, 2) = 2 * pow(2, 1)
pow(2, 1) = 2
因此，递归将函数调用简化为一个更简单的函数调用，然后再将其简化为一个更简单的函数，以此类推，直到结果变得显而易见。
最大的嵌套调用次数（包括首次）被称为 递归深度。在我们的例子中，它正好等于 n。
最大递归深度受限于 JavaScript 引擎。对我们来说，引擎在最大迭代深度为 10000 及以下时是可靠的，有些引擎可能允许更大的最大深度，但是对于大多数引擎来说，100000 可能就超出限制了。有一些自动优化能够帮助减轻这种情况（尾部调用优化），但目前它们还没有被完全支持，只能用于简单场景。
这就限制了递归的应用，但是递归仍然被广泛使用。有很多任务中，递归思维方式会使代码更简单，更容易维护。
- 执行上下文和堆栈
现在我们来研究一下递归调用是如何工作的。为此，我们会先看看函数底层的工作原理。
有关正在运行的函数的执行过程的相关信息被存储在其 执行上下文 中。
执行上下文是一个内部数据结构，它包含有关函数执行时的详细细节：当前控制流所在的位置，当前的变量，this 的值（此处我们不使用它），以及其它的一些内部细节。
一个函数调用仅具有一个与其相关联的执行上下文。
当一个函数进行嵌套调用时，将发生以下的事儿：
1.当前函数被暂停；
2.与它关联的执行上下文被一个叫做 执行上下文堆栈 的特殊数据结构保存；
3.执行嵌套调用；
4..嵌套调用结束后，从堆栈中恢复之前的执行上下文，并从停止的位置恢复外部函数。
本示例中的递归深度为：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。
任何递归都可以用 循环 来重写。通常循环变体更有效。
……但有时重写很难，尤其是函数根据条件使用不同的子调用，然后合并它们的结果，或者分支比较复杂时。而且有些优化可能没有必要，完全不值得。
递归可以使代码更短，更易于理解和维护。并不是每个地方都需要优化，大多数时候我们需要一个好代码，这就是为什么要使用它。
递归遍历
- 案例
1.js 树递归案例
网友评论