4. 递归原理与树形结构

递归就是函数自己调用自己，把大问题拆成一模一样的小问题。

核心三要素：
① 终止条件——什么时候停（写最前面）
② 调用自己——把问题拆小
③ 返回值——每层把结果交还给上层

坑：忘了终止条件栈溢出、递归深度太大会卡、先画展开图再写代码。

4.1 先跑起来：阶乘递归展开图（递 + 归）

递归两个字拆开看：递 = 往下拆（5×4! → 4×3! → …），归 = 往回算（1 → 2 → 6 → 24 → 120）。上面的演示就是把这个"先下后上"的过程一步一步放给你看，看懂它，递归就懂了一半。

4.2 什么是递归 + 递归三要素

function fn() {
  // 调用自己，但【没有终止条件】→ 死循环！浏览器直接报栈溢出
  fn;
}

核心一句话：递归 = 递（往下拆）+ 归（往回返）。生活类比到处都是：俄罗斯套娃、一层层的文件夹、剥洋葱——剥到芯就必须停，这就是终止条件。如果你忘了写终止条件，函数会一直往下调自己，内存被一层层占满，最后浏览器报 栈溢出（Maximum call stack size exceeded）。

4.3 标准写法：终止条件必须写在最前面

// 求 n 的阶乘：n × (n-1) × ... × 1
function factorial(n) {
  // 防御：先处理非法输入（比如传了 0 或负数）→ 先把垃圾输入挡掉
  // n 小于 1 就不算了，返回 -1 表示出错
  if (n < 1) return -1;

  // 要素①：终止条件（★ 必须最先判断，写在最前面）→ 到底了就别再拆
  // 1 的阶乘就是 1，直接返回
  if (n === 1) return 1;

  // 要素② + ③：调用自己 + 把结果乘完返回 → 大问题 = n × 小一号的问题
  // n 的阶乘 = n × (n-1 的阶乘)，去调自己算小的
  return n * factorial(n - 1);
}

// 120 → 5! = 5×4×3×2×1 = 120
console.log(factorial(5));

为什么终止条件要写最前面？因为先判断"能不能停"，再决定"要不要继续拆"，顺序不能反。如果把它写在 return 后面，函数永远走不到那一行就开始无限拆了。

4.4 实战 1：遍历文件夹（找出所有文件名）

// 这是一棵文件夹树：文件夹里套文件夹，叶子是文件
const folder = {
  name: "根目录",
  type: "folder",
  // children 是它的下一层
  children: [{
    name: "图片",
    type: "folder",
    children: [{
        name: "2024年照片",
        type: "folder",
        children: [
          // type 是 file 表示到底了
          { name: "1.jpg", type: "file" }, { name: "2.jpg", type: "file" }
        ]
      },
      { name: "2025年照片", type: "folder", children: [{ name: "3.jpg", type: "file" }] }
    ]
  }, {
    name: "文档",
    type: "folder",
    children: [
      { name: "报告.docx", type: "file" }, { name: "说明.txt", type: "file" }
    ]
  }]
};

// 传进来一个节点（可能是文件夹也可能是文件）
function getFileNames(node) {
  // 终止条件：摸到【文件】了，就直接返回它自己的名字（包成数组）→ 到叶子就停
  // 是文件：把它的名字包成数组返回
  if (node.type === "file") return [node.name];

  // 是文件夹：遍历它的每个 children，把结果一个个【合并】起来
  // 先准备一个空数组装所有文件名字
  let result = [];

  // 把它的下一层挨个走一遍
  for (let i = 0; i < node.children.length; i++) {
    // 递归子节点，合并结果 → 每个子节点返回的数组拼进来
    result = result.concat(getFileNames(node.children[i]));
  }

  // 把这层汇总好的数组交还给上一层
  return result;
}

// 从根目录开始找
console.log(getFileNames(folder));
// ["1.jpg", "2.jpg", "3.jpg", "报告.docx", "说明.txt"] → 所有文件名字都被挖出来了

关键技巧：每层返回值的【类型要统一】。文件节点返回一个数组（就一个名字），文件夹节点也返回数组（把所有子节点的数组合并）。因为类型统一，每层才能用 concat 把结果拼起来。如果你这层返回字符串、那层返回数组，拼接的时候就对不上了。

4.5 实战 2：树形结构渲染（带展开/折叠）

// 画一棵树：data 是这层数据，level 是现在第几层
function renderTree(data, level) {
  // 没传层数就默认第 0 层
  level = level || 0;
  // 准备一个空字符串攒这层的 HTML
  let html = "";
  // 每层往里缩进一点 → 越深的层越往右缩
  let indent = level * 20;

  // 把这层的每个节点画一遍
  data.forEach(function (node) {
    // 每条开头按层缩进（字符串拼接）
    html += '<div style="padding-left:' + indent + 'px;">';

    // 如果这节点还有下一层
    if (node.children && node.children.length > 0) {
      // 有子节点：画展开按钮 + 名字 + 递归画子节点
      // 画一个折叠箭头 + 名字
      html += '<span class="toggle">▼</span> ' + node.name;
      // 递归画子层，层数+1
      html += '<div class="children">' + renderTree(node.children, level + 1) + '</div>';
    } else {
      // 叶子节点（终止条件）：只画名字 → 到底了，画个文件图标就行
      html += '📄 ' + node.name;
    }

    // 每条收尾
    html += '</div>';
  });

  // 把这层拼好的 HTML 交还给上一层
  return html;
}

// 展开/折叠：按钮是动态生成的，必须用【事件委托】绑到父级 → 按钮是后加的，绑的时候还不存在
// 干脆委托到整个 document 上，用选择器过滤
$(document).on("click", ".toggle", function () {
  // 箭头后面跟着的就是这组子节点
  const $children = $(this).next();
  // 后面没跟着 div 就不管
  if (!$children.length || !$children.is("div")) return;

  // 现在是收起的
  if ($children.css("display") === "none") {
    // 展开
    $children.css("display", "block");
    // 箭头朝下
    $(this).text("▼");
  } else {
    // 现在是展开的
    // 收起
    $children.css("display", "none");
    // 箭头朝右
    $(this).text("▶");
  }
});

递归渲染的本质是"函数自己拼自己"：每层只负责画当前这一层，剩下交给递归去画子层。注意——树上的展开按钮是JS 动态生成的，你不能直接给它们绑事件（绑的时候它们还不存在），必须用事件委托绑到父级 document 上，用 $(document).on("click", ".toggle", ...) 的选择器过滤出到底点的是哪个按钮。

4.6 递归 vs 循环（什么时候用哪个）

口诀：树形结构用递归，列表数组用循环。别为了炫技硬用递归——层数固定的扁平数据，老老实实 for 循环又快又稳。

4.7 写递归的正确姿势（5 步，别一上来就写代码）

第1步： 先写【 终止条件】（ 什么时候停、 直接返回什么）→ 先定 "拆到哪一步就停"
第2步： 画【 递归展开图】（ 把每一步手写出来， 确认逻辑对不对）→ 拿笔一步步拆出来看
第3步： 再写【 调用自己】 的代码（ 照着展开图写递推公式）→ 照着图翻译成代码
第4步： 确定【 返回值】（ 每层要把什么结果交给上一层）→ 想好每层交出什么
第5步： 测【 边界值】（ 用最小参数， 比如 n = 1、 空文件夹， 测能不能正确停住）→ 拿最小情况试， 看能不能正确停

核心原则：不要直接写代码，先画展开图！很多人递归写错，就是因为脑子里没想清楚就敲键盘，越写越乱。先拿笔把 factorial(3) 一层层写出来，逻辑清楚了再落成代码，错误率直线下降。

4.8 实战：用在哪 / 常见坑 / 怎么解决

① 可能在什么地方用：文件目录树、公司组织架构图、商品多级分类、菜单多级展开、评论楼中楼——只要是"一层套一层、层数不定"的数据，渲染和遍历都靠递归。

② 常见的问题：报 栈溢出（忘了写终止条件，或终止条件永远到不了）；拼出来的树错位/层数乱（缩进 level 没 +1）；点展开没反应（动态按钮没绑事件委托，直接绑了不存在的元素）；返回值类型不统一导致 concat 报错（有的层返回字符串有的返回数组）。

③ 解决思路：栈溢出就在递归函数第一行打印一下当前参数，看它是怎么一路变小（或不变）的，很快能发现哪一层没停下；树错位就 console.log 每一层的 level；按钮没反应就检查是不是把事件绑在动态生成的元素上——换成 $(document).on("click", ".toggle", ...) 事件委托绑到父容器。记住先画展开图。

本页重点