递归自引用与链表结构

递归函数直接引用自身名有什么风险？

function factorial(num) {
  if (num <= 1) return 1;
  return num * factorial(num - 1);
}

• 风险: 函数名是指向函数对象的指针, 若外部改写了这个名字, 递归调用就会失效;

const anotherFactorial = factorial;
factorial = null;
anotherFactorial(4); // TypeError; 内部仍引用名为 factorial 的指针

• 规避: 使用命名函数表达式, 让内部递归引用一个不会外泄的名字;

const factorial = function self(num) {
  return num <= 1 ? 1 : num * self(num - 1);
};

如何用递归遍历嵌套结构？

• 两种情形: 参数是数组即为叶子 (递归基: 可直接求解、不再调用自身), 直接循环求和; 参数是对象则对每个子部门递归调用并合并结果 (递归步: 化简为一次同类小规模调用);

const company = {
  sales: [{ salary: 1000 }, { salary: 1600 }],
  development: { sites: [{ salary: 2000 }], internals: [{ salary: 1300 }] },
};
function sumSalaries(dep) {
  if (Array.isArray(dep)) return dep.reduce((prev, cur) => prev + cur.salary, 0);
  return Object.values(dep).reduce((sum, sub) => sum + sumSalaries(sub), 0);
}
sumSalaries(company); // 5900

• 递归数据结构: 自身定义里引用自身, 如部门 (数组或子部门对象)、HTML 标签 (文本、注释或子标签);

链表与数组各有什么取舍？

• 链表节点是递归结构: 每个对象含 value 与指向下一节点的 next (末尾为 null);

let list = { value: 1, next: { value: 2, next: { value: 3, next: null } } };
list = { value: "new", next: list }; // 头部插入
list.next = list.next.next; // 删除中间节点

• 数组痛点: unshift/shift 要重排全部索引, 大队列很慢; 只有 push/pop 不重排;
• 优点: 插入、删除、拆分、合并只改指针, 没有重编号; 缺点: 不能按下标直接访问, 取第 N 个要从头走 N 次;
• 适用: 队列、双端队列等「两端频繁增删, 不访问中间」的结构; 可加 prev/tail 增强;