JavaScript 中函数怎么使用递归函数解决分治与树状结构遍历问题-js教程-PHP中文网

递归函数通过自我调用将大问题分解为相同结构的子问题，直至边界条件终止；适用于快排分治、树dfs遍历及嵌套结构处理，但须设明确终止条件以防栈溢出。

javascript 中函数怎么使用递归函数解决分治与树状结构遍历问题

递归函数是 JavaScript 中处理分治思想和树状结构遍历最自然、最直接的方式——核心在于：把大问题拆成结构相同的小问题，函数自己调用自己，直到触达边界条件（base case）停止。

分治问题：用递归实现快速排序

分治（Divide and Conquer）要求“分—治—合”。以快排为例：选一个基准值，把数组分成小于和大于它的两部分，再分别对这两部分递归排序。

关键点：

每次递归只处理子数组，原数组不被修改（推荐返回新数组或用索引控制范围）
边界条件是子数组长度 ≤ 1，此时直接返回，不再递归
避免在递归中重复创建大量中间数组，可用原地分区 + 索引参数提升性能

示例（简洁版）：

function quickSort(arr) {
  if (arr.length  x  x > pivot);
  const mid = arr.filter(x => x === pivot);
  return [...quickSort(left), ...mid, ...quickSort(right)];
}

树的深度优先遍历（DFS）：递归是最直观写法

树天然具有递归结构：每个节点的子树与整棵树结构一致。因此前序、中序、后序遍历都可直接用递归表达。

以二叉树前序遍历（根→左→右）为例：

Alibabacloud Sdk Client Initialization For Java

在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。

下载

当前节点为空（null/undefined），直接 return（边界条件）
否则先访问根节点（如 push 到结果数组），再递归遍历左子树，再递归遍历右子树
无需手动维护栈，调用栈自动保存每层状态

示例：

function preorderTraversal(root, result = []) {
  if (!root) return result;
  result.push(root.val);
  preorderTraversal(root.left, result);
  preorderTraversal(root.right, result);
  return result;
}

处理嵌套对象或 DOM 树：递归遍历任意层级结构

现实中的树状数据未必是标准二叉树，比如配置对象、菜单数据、DOM 节点树。只要结构有“自身 + 子集”特征，就适合递归。

关键技巧：

用 Array.isArray() 或 node.children 判断是否含子节点
对每个子项统一调用同一函数，不预设层级深度
可传入回调函数（callback）实现灵活处理，如收集特定属性、查找匹配项、转换结构

示例（遍历嵌套菜单，提取所有路由 path）：

function collectPaths(menu, paths = []) {
  for (const item of menu) {
    if (item.path) paths.push(item.path);
    if (Array.isArray(item.children)) {
      collectPaths(item.children, paths);
    }
  }
  return paths;
}