js递归匹配数据

在JavaScript中，递归是一种常用的编程技巧，特别是在处理嵌套数据结构时。递归匹配数据通常指的是使用递归函数来遍历和处理嵌套的数据结构，如数组或对象，以便查找符合特定条件的数据。

基础概念

递归函数是指在函数内部调用自身的函数。递归函数通常有两个主要部分：

基准情况（Base Case）：这是递归停止的条件，防止无限递归。
递归步骤（Recursive Step）：在这一步中，函数调用自身，通常处理数据的一个子集。

优势

简洁性：递归可以使代码更加简洁和易于理解。
通用性：递归可以处理任意深度的嵌套结构。

类型

数据遍历：如遍历树形结构或嵌套数组。
搜索算法：如深度优先搜索（DFS）。
数据转换：如将嵌套数据结构展平。

应用场景

树形结构操作：如文件系统的遍历。
图论算法：如寻找最短路径。
处理JSON数据：如查找特定键值对。

示例代码

假设我们有一个嵌套的数据结构，我们想要找到所有的数字类型字段，并计算它们的总和：

const data = {
  a: 1,
  b: {
    b1: 2,
    b2: {
      b21: 3,
      b22: 'hello'
    }
  },
  c: [4, { c1: 5 }]
};

function sumNumbers(obj) {
  let sum = 0;

  function recurse(current) {
    if (typeof current === 'number') {
      sum += current;
    } else if (Array.isArray(current)) {
      current.forEach(item => recurse(item));
    } else if (typeof current === 'object' && current !== null) {
      Object.values(current).forEach(value => recurse(value));
    }
  }

  recurse(obj);
  return sum;
}

console.log(sumNumbers(data)); // 输出应该是 1+2+3+4+5 = 15

遇到的问题及解决方法

栈溢出：如果数据结构过于深，可能会导致调用栈溢出。解决方法是使用尾递归优化（如果JavaScript引擎支持）或者改写为迭代算法。
性能问题：递归可能会导致性能问题，特别是在大数据集上。可以通过缓存结果（记忆化）或者优化递归逻辑来提高性能。
循环引用：如果数据结构中存在循环引用，递归将永远不会结束。可以通过维护一个已访问对象的集合来避免重复处理。

解决循环引用问题示例

function sumNumbersSafe(obj, visited = new WeakSet()) {
  let sum = 0;

  if (visited.has(obj)) {
    return sum;
  }

  visited.add(obj);

  function recurse(current) {
    if (typeof current === 'number') {
      sum += current;
    } else if (Array.isArray(current)) {
      current.forEach(item => recurse(item));
    } else if (typeof current === 'object' && current !== null) {
      Object.values(current).forEach(value => recurse(value));
    }
  }

  recurse(obj);
  return sum;
}

// 假设data中存在循环引用
data.b.b2.self = data.b;

console.log(sumNumbersSafe(data)); // 输出应该是 15，即使存在循环引用

在这个例子中，我们使用了WeakSet来跟踪已经访问过的对象，从而避免了循环引用导致的无限递归问题。