← 返回目录

4. 递归原理与树形结构

把这页想成"俄罗斯套娃"：一个大娃娃里装着小娃娃，小娃娃里又装着更小的娃娃……你必须知道最小的那个娃娃长什么样（终止条件），才能一层层打开。递归就是函数自己调用自己，把一个大问题拆成一模一样的小问题，拆到最小就停。学会它，你就能优雅地处理树形结构——文件夹、组织架构、商品分类，全是"一棵树"。

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

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

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

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

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

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

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

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

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

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

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

const folder = {                     // 这是一棵文件夹树：文件夹里套文件夹，叶子是文件
  name: "根目录",
  type: "folder",
  children: [{                        // children 是它的下一层
    name: "图片",
    type: "folder",
    children: [{
        name: "2024年照片",
        type: "folder",
        children: [
          { name: "1.jpg", type: "file" }, { name: "2.jpg", type: "file" }  // 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：树形结构渲染（带展开/折叠）

function renderTree(data, level) {   // 画一棵树：data 是这层数据，level 是现在第几层
  level = level || 0;                 // 没传层数就默认第 0 层
  let html = "";                      // 准备一个空字符串攒这层的 HTML
  const indent = level * 20; // 每层往里缩进一点 → 越深的层越往右缩
  data.forEach(function (node) {      // 把这层的每个节点画一遍
    html += `<div style="padding-left:${indent}px;">`;  // 每条开头按层缩进
    if (node.children &amp;&amp; node.children.length > 0) {  // 如果这节点还有下一层
      // 有子节点：画展开按钮 + 名字 + 递归画子节点 → 是个能点开的文件夹
      html += `<span class="toggle">▼</span> ${node.name}`;  // 画一个折叠箭头 + 名字
      html += `<div class="children">` + renderTree(node.children, level + 1) + `</div>`; // 递归画子层，层数+1
    } else {
      // 叶子节点（终止条件）：只画名字 → 到底了，画个文件图标就行
      html += `📄 ${node.name}`;
    }
    html += `</div>`;                 // 每条收尾
  });
  return html;                        // 把这层拼好的 HTML 交还给上一层
}

// 展开/折叠：按钮是动态生成的，必须用【事件委托】绑到父级 → 按钮是后加的，绑的时候还不存在
document.addEventListener("click", function (e) {  // 干脆绑到整个 document 上
  if (!e.target.classList.contains("toggle")) return;  // 点的不是折叠箭头就不管
  const children = e.target.nextElementSibling();  // 箭头后面跟着的就是这组子节点
  if (children.style.display === "none") {  // 现在是收起的
    children.style.display = "block";             // 展开
    e.target.textContent = "▼";                   // 箭头朝下
  } else {                                        // 现在是展开的
    children.style.display = "none";             // 收起
    e.target.textContent = "▶";                    // 箭头朝右
  }
});

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

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

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

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

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

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

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

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

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

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