递归与堆栈

本文参考 https://zh.javascript.info/recursion#zhi-hang-shang-xia-wen-he-dui-zhan

什么是递归（Recursion）？

函数调用自身称为递归，这种函数称为递归函数。它经常被用于将一个任务分成若干相似子任务从而简化问题。

递归实例

如下 multiply() 调用了自身


function multiply(arr, n) {
    if (n <= 0) {
      return 1;
    } else {
      return multiply(arr, n - 1) * arr[n - 1];
    }
  }

该函数计算并返回 arr 数组的前 n 项积，可以看到，这种方法没有使用循环语句，但和循环语句一样拥有一个终止条件。这样做的好处是使函数逻辑更清晰，避免了使用相较更冗杂的循环语句。以上函数还可精简为以下写法：


function multiply(arr, n) {
  return (n <= 0) ? 1 : (multiply(arr, n - 1) * arr[n - 1]);
}

递归嵌套调用次数（递归深度）受 JavaScript 引擎影响是有上限的，通常是在 10000 次及以下时迭代是可靠的。

执行上下文和堆栈

有关正在运行的函数的执行过程的相关信息被存储在其执行上下文中。执行上下文是一个内部数据结构，它包含有关函数执行时的详细细节。

当一个函数进行嵌套调用时：

当前函数被暂停；

与它关联的执行上下文被一个叫做执行上下文堆栈的特殊数据结构保存；

执行嵌套调用；

嵌套调用结束后，从堆栈中恢复之前的执行上下文，并从停止的位置恢复外部函数。

观察以下代码


function countup(n) {
  if (n < 1) {
    return [];
  } else {
    const countArray = countup(n - 1);
    countArray.push(n);
    return countArray;
  }
}
console.log(countup(5));

直觉上 console.log(countup(5)) 会打印 [5, 4, 3, 2, 1] ，但实际上结果正好相反，这是因为当函数第一次执行到 const countArray = countup(n - 1); 时，下一步执行的是再次调用函数 countup() ，传入参数 n - 1 ，而非执行 countArray.push(n) 。因此，函数会在递归调用完成后才会将 n 写入 countArray 数组，故日志内容为 [1, 2, 3, 4, 5] 。