js id pid 递归

在JavaScript中，id 和 pid 通常用于表示节点的唯一标识符和父节点的标识符。递归是一种编程技巧，可以在函数内部调用自身来解决问题。结合 id 和 pid，递归常用于处理树形结构的数据，例如组织架构、分类目录等。

基础概念

id: 节点的唯一标识符。
pid: 节点的父节点标识符。
递归: 函数自己调用自己的过程。

应用场景

假设我们有一个树形结构的数据，需要将其转换为另一种格式，或者需要遍历这个树形结构来执行某些操作。

示例代码

数据结构

const data = [
  { id: 1, pid: 0, name: 'Root' },
  { id: 2, pid: 1, name: 'Child 1' },
  { id: 3, pid: 1, name: 'Child 2' },
  { id: 4, pid: 2, name: 'Grandchild 1' },
  { id: 5, pid: 2, name: 'Grandchild 2' },
];

递归函数

假设我们要将这个扁平化的数据结构转换为树形结构：

function buildTree(data, parentId = 0) {
  return data
    .filter(item => item.pid === parentId)
    .map(item => ({
      ...item,
      children: buildTree(data, item.id)
    }));
}

const tree = buildTree(data);
console.log(JSON.stringify(tree, null, 2));

解释

filter: 筛选出所有父节点ID为当前 parentId 的节点。
map: 对每个筛选出的节点，递归调用 buildTree 函数来构建其子节点。
children: 将递归结果赋值给当前节点的 children 属性。

常见问题及解决方法

栈溢出: 递归深度过大可能导致栈溢出。可以通过优化递归逻辑或使用迭代方法解决。
性能问题: 递归调用可能会导致性能问题，特别是在大数据集上。可以通过缓存中间结果或使用尾递归优化来解决。

示例：避免栈溢出

对于非常深的树形结构，可以考虑使用迭代方法来避免栈溢出：

function buildTreeIterative(data) {
  const map = new Map();
  const roots = [];

  data.forEach(item => {
    map.set(item.id, { ...item, children: [] });
  });

  data.forEach(item => {
    if (item.pid === 0) {
      roots.push(map.get(item.id));
    } else {
      const parent = map.get(item.pid);
      if (parent) {
        parent.children.push(map.get(item.id));
      }
    }
  });

  return roots;
}

const treeIterative = buildTreeIterative(data);
console.log(JSON.stringify(treeIterative, null, 2));