Gauss Zhou

# 函数进阶-递归和堆栈

TIP

主要内容来自现代 JavaScript 指南

递归是一种编程模式，在一个任务可以自然地拆分成多个相同类型但更简单的任务的情况下非常有用。或者，在一个任务可以简化为一个简单的行为加上该任务的一个更简单的变体的时候可以使用。或者，就像我们很快会看到的那样，处理某些数据结构。

当一个函数解决一个任务时，在解决的过程中它可以调用很多其它函数。在部分情况下，函数会调用 自身。这就是所谓的 递归。

简单起见，让我们写一个函数 pow(x, n)，它可以计算 x 的 n 次方。换句话说就是，x 乘以自身 n 次

// 迭代思路：使用 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

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

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

最大的嵌套调用次数（包括首次）被称为 递归深度。在我们的例子中，它正好等于 n。

最大递归深度受限于 JavaScript 引擎。对我们来说，引擎在最大迭代深度为 10000 及以下时是可靠的，有些引擎可能允许更大的最大深度，但是对于大多数引擎来说，100000 可能就超出限制了。有一些自动优化能够帮助减轻这种情况（尾部调用优化），但目前它们还没有被完全支持，只能用于简单场景。

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

……但有时重写很难，尤其是函数根据条件使用不同的子调用，然后合并它们的结果，或者分支比较复杂时。而且有些优化可能没有必要，完全不值得。

递归可以使代码更短，更易于理解和维护。并不是每个地方都需要优化，大多数时候我们需要一个好代码，这就是为什么要使用它。

# 递归遍历

递归的另一个重要应用就是递归遍历。

比如在 DOM 树中找到 ele 元素的最近的父元素，该父元素具有 classN 的类名

findParent(ele, classN) {
  if (ele.className.indexOf(classN) > -1) {
    return ele;
  } else {
    return this.findParentData(ele.parentElement, classN);
  }
}

比如在一棵树 tree 中找到 target 节点的父元素，不过这里使用的是广度优先遍历

function findParent(tree, target) {
  let queue = [];
  let result = null;
  if (Object.prototype.toString.call(tree) == "[object Array]") {
    queue.push(...tree);
  } else {
    queue.push(tree);
  }
  while (queue.length) {
    let candidate = queue.shift();
    if (candidate.children.some((item) => item.id == target.id)) {
      result = candidate;
    } else {
      if (candidate.children && candidate.children.length) {
        queue.push(...candidate.children);
      }
    }
  }
  return result;
}

# 递归结构

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

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

正常的选择会是一个数组：

let arr = [obj1, obj2, obj3];

……但是用数组有个问题。“删除元素”和“插入元素”的操作代价非常大。

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

链表元素 是一个使用以下元素通过递归定义的对象：

  • value。
  • next 属性引用下一个 链表元素 或者代表末尾的 null。

例如：

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

链表的图形表示：

该链表可以很容易被拆分为多个部分

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

然后再重新组装回去：

list.next.next = secondList;

要从中间删除一个值，可以修改前一个元素的 next：

list.next = list.next.next

删除前

删除后

我们让 list.next 从 2 跳到值 3。现在值 2 就被从链表中移除了。

垃圾回收

如果它没有被存储在其它任何地方，那么它会被自动从内存中删除。

链表可以得到增强：

  • 我们可以在 next 之外，再添加 prev 属性来引用前一个元素，以便轻松地往回移动。
  • 我们还可以添加一个名为 tail 的变量，该变量引用链表的最后一个元素（并在从末尾添加/删除元素时对该引用进行更新）。
  • ……数据结构可能会根据我们的需求而变化。

递归遍历
递归结构