跳到主要内容

递归与尾调用

递归由哪两部分构成？​

  • 递归基 (base): 参数小到可直接得出答案, 不再调用自身;
  • 递归步 (step): 把任务化简成一次简单运算 + 一次规模更小的同类调用;
  • 过程: pow(2, 4) = 2 * pow(2, 3) = 2 * (2 * pow(2, 2)) = …, 直到 pow(2, 1) = 2;
// 递归式: 每层只留一个乘数, 层层向递归基收敛
function pow(x, n) {
  return n == 1 ? x : x * pow(x, n - 1);
}
  • 特点: 递归写法通常更短更好读, 代价见下面的栈与取舍;
  • 铁律: 递归基必须可达, 否则无限递归直至栈溢出;

递归调用时执行上下文栈如何变化？​

  • 上下文: 每次调用对应一个执行上下文 (存变量、this、执行到哪一步); 嵌套调用时外层上下文压入栈并暂停, 子调用结束后弹出并继续;

  • 深度: 递归深度 = 栈中同时存在的上下文数量 = 最大嵌套调用层数;

  • 轨迹 (pow(2, 3)): 进入 pow(2, 2) 时栈为 {x:2,n:2}/{x:2,n:3}; 再进入 pow(2, 1) 时栈有 3 层; 返回时逐层弹出, 各自用子结果完成乘法;

  • 内存: 求 x 的 n 次幂要 n 个上下文, 空间开销随深度线性增长;

  • 对照: 迭代版只用一个上下文反复改写 i 与 result, 内存小且与 n 无关;

递归的深度限制与迭代取舍是什么？​

  • 上限: 引擎限制最大嵌套调用数, 可依赖约 10000, 多数引擎到不了 100000;
  • 后果: 超出即抛 RangeError: Maximum call stack size exceeded;
  • 缓解: 尾调用优化本可复用栈帧, 但支持不完整且只对简单情形生效, 具体限制见下文;
  • 结论: 任何递归都能改写成循环, 迭代通常更省内存; 但改写有时很别扭 (分支多、要合并多个子调用结果), 只在深度或性能成为瓶颈时才做;

尾调用优化做了什么？​

  • 机制: 外部函数的返回值就是某个内部函数的返回值时, 销毁外部函数的栈帧, 只保留一层栈帧;
  • 前提: 严格模式, 且返回值直接是对尾调用函数的调用, 返回后不再做额外运算;
  • 不可检测: 引擎不暴露优化是否生效, 只能按条件编写;

哪些写法会阻止尾调用优化？​

  • 四类失效: 尾调用没有返回、没有直接返回、返回后还要转型、尾调用是引用外层自由变量的闭包;
"use strict";
function noReturn() {
  innerFunction(); // 尾调用没有返回
}
function storeFirst() {
  const result = innerFunction(); // 尾调用没有直接返回
  return result;
}
function convert() {
  return innerFunction().toString(); // 返回后还要转型
}
function closure() {
  const foo = "bar";
  return function () {
    return foo; // 尾调用是引用外层自由变量的闭包
  };
}

如何把递归改写成可尾调用的形式？​

  • 思路: 用累加参数把中间结果一路传给下一次调用, 使返回值只剩一次可直接复用栈帧的尾调用;
// 优化前: 返回后还要做加法, 无法复用栈帧
function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

// 优化后: 用累加参数把中间结果传给下一次调用
("use strict");
function fib(n) {
  return fibImpl(0, 1, n);
}
function fibImpl(a, b, n) {
  if (n === 0) return a;
  return fibImpl(b, a + b, n - 1);
}