带累加器的JS递归函数仍触发栈溢出，二次调用成功求解决

我有一个值类型可为任意类型的对象：

const data = {
  a: { aa: 50, ab: 'hello', ac: 'xx_1' },
  b: 50,
  c: [
    { ca: 100, cb: 'by', cc: 'xx_2' },
    { ca: 101, cb: 'by1', cc: 'xx_3' },
  ],
  d: [],
  e: {
    ea: 50,
    eb: ['xx_1', 'xx_4'],
  },
}

我需要遍历该对象并替换符合特定模式的值，因此实现了递归函数exportContractFormatter，搭配非递归的数值转换函数exportContractConverter；为避免栈溢出，我在递归调用时使用了累加器（acc），并通过lodash的update方法基于路径更新累加器，代码如下：

export function exportContractFormatter(
  data: any[],
  exportContractConverter: (data:any, path:string[])=>any,
  acc: Record<string, any> = {},
  path: string[] = [],
  level = [] as number[]
): any {

  if (data.length === 0) return acc;
  const head = data[0];
  const tail = data.slice(1);

  // enter only if not empty array or not empty object
  if (
    typeof head[1] === 'object' &&
    head[1] !== null &&
    ((Array.isArray(head[1]) && head[1].length > 0) ||
      (!Array.isArray(head[1]) && Object.keys(head[1]).length > 0))
  ) {
    //if array use index as key
    const valueFormatted = Array.isArray(head[1])
      ? head[1].map((item, index) => [index, item])
      : Object.entries(head[1]);

    //initialize object or array thank to path
    update(acc, path.concat(head[0]).join('.'), (n) => (Array.isArray(head[1]) ? [] : {}));

    //recurse with one deeper level
    return exportContractFormatter(
      [...valueFormatted, ...tail],
      exportContractConverter,
      acc,
      [...path, head[0]],
      [...level, valueFormatted.length * -1]
    );
  } else {
    if (typeof head[1] === 'object' && head[1] !== null) {
      //empty object or array, no need to convert value
      update(acc, path.concat(head[0]).join('.'), (n) => (Array.isArray(head[1]) ? [] : {}));
    } else {
      //convert value
      update(acc, path.concat(head[0]).join('.'), (n) => {
        return exportContractConverter(head[1], path.concat(head[0]));
      });
    }
    const [newLevel, newPath] = getLevelAndPath(level, path);
    //recurse same level or shallower
    return exportContractFormatter(tail, exportContractConverter, acc, newPath, newLevel);
  }
}

exportContractFormatter(Object.entries(data), exportContractConverter);

当前遇到的问题：

• 当对象过大（包含大量嵌套对象或数组）时，会触发maximum call stack size错误；
• 存在异常现象：首次递归调用失败，二次调用却能成功。

相关辅助代码如下：

const referentialData = {
    ref_1: [
      {
        value: 'xx_1',
        displayText: 'CONVERTED_1',
      },
      {
        value: 'xx_2',
        displayText: 'NO',
      },
      {
        value: 'xx_3',
        displayText: 'NO',
      },
      {
        value: 'xx_4',
        displayText: 'CONVERTED_4',
      },
    ],
    ref_2: [
      {
        score_id: 'xx_1',
        label: 'NO',
      },
      {
        score_id: 'xx_2',
        label: 'CONVERTED_2',
      },
      {
        score_id: 'xx_3',
        label: 'CONVERTED_3',
      },
    ],
};
const usages = [
    {
      referential_name: 'ref_1',
      path: 'a.ac',
      widget_name: 'widget_1',
      kind: 'simple_referential',
    },
    {
      referential_name: 'ref_2',
      path: 'c.cc',
      widget_name: 'widget_2',
      kind: 'article',
    },
    {
      referential_name: 'ref_1',
      path: 'e.eb',
      widget_name: 'widget_1',
      kind: 'simple_referential',
    },
];
const result = {
    a: { aa: 50, ab: 'hello', ac: 'CONVERTED_1' },
    b: 50,
    c: [
      { ca: 100, cb: 'by', cc: 'CONVERTED_2' },
      { ca: 101, cb: 'by1', cc: 'CONVERTED_3' },
    ],
    d: [],
    e: {
      ea: 50,
      eb: ['CONVERTED_1', 'CONVERTED_4'],
    },
};
const exportContractConverter = exportContractConverterGenerator(referentialData, usages);

export function exportContractConverterGenerator(
  referentialData: Record<string, any[]>,
  usages: Array<Record<string, any>>
) {
  return (data: any, path: string[]): any => {
    if (!data || !usages) return data;
    const _path = path.filter((item) => typeof item !== 'number').join('.');

    const found = usages?.find((item) => item?.path === _path);

    if (!found || !found.referential_name) return data;
    if (found.kind === 'article') {
      return (
        (referentialData[found.referential_name]).find(
          (item) => item.score_id === data
        )?.label || data
      );
    } else {
      return (
        (referentialData[found.referential_name]).find(
          (item) => item.value === data
        )?.displayText || data
      );
    }
  };
}

1. 彻底替换递归为迭代（栈实现） #

当前实现本质还是尾递归变种，但JS引擎对尾递归的优化不稳定（仅严格模式下部分引擎支持），数据层级深或量大时必然栈溢出。改用迭代方式遍历，用栈存储待处理节点，完全规避栈溢出：

import { update } from 'lodash';

export function exportContractFormatterIterative(
  sourceData: Record<string, any> | any[],
  converter: (data: any, path: string[]) => any
): any {
  const acc = Array.isArray(sourceData) ? [] : {};
  // 栈元素：[当前节点数据, 当前路径, 父节点引用, 键名/索引]
  const stack: [any, string[], any, string | number][] = [];

  // 初始化栈，处理根节点
  if (Array.isArray(sourceData)) {
    sourceData.forEach((item, idx) => stack.push([item, [String(idx)], acc, idx]));
  } else {
    Object.entries(sourceData).forEach(([key, val]) => stack.push([val, [key], acc, key]));
  }

  while (stack.length > 0) {
    const [currentVal, currentPath, parent, key] = stack.pop()!;

    if (typeof currentVal === 'object' && currentVal !== null) {
      if (Array.isArray(currentVal)) {
        // 初始化空数组
        update(parent, key, () => []);
        // 倒序入栈，保证处理顺序正确
        for (let i = currentVal.length - 1; i >= 0; i--) {
          stack.push([
            currentVal[i],
            [...currentPath, String(i)],
            parent[key],
            i
          ]);
        }
      } else {
        const keys = Object.keys(currentVal);
        if (keys.length === 0) {
          // 空对象直接初始化
          update(parent, key, () => {});
        } else {
          // 初始化空对象
          update(parent, key, () => {});
          // 倒序入栈
          for (let i = keys.length - 1; i >= 0; i--) {
            const k = keys[i];
            stack.push([
              currentVal[k],
              [...currentPath, k],
              parent[key],
              k
            ]);
          }
        }
      }
    } else {
      // 非对象/数组，调用转换器更新值
      update(parent, key, () => converter(currentVal, currentPath));
    }
  }

  return acc;
}

// 调用方式：直接传入原始data，无需转Object.entries
exportContractFormatterIterative(data, exportContractConverter);

2. 优化路径匹配与引用数据查询逻辑 #

当前exportContractConverter每次调用都重复处理路径、遍历usages和引用数组，数据量大时开销极高，提前预构建映射表减少重复计算：

export function exportContractConverterGenerator(
  referentialData: Record<string, any[]>,
  usages: Array<Record<string, any>>
) {
  // 预构建引用数据的映射：referentialName -> { 原始值: 转换后文本 }
  const refMap = Object.entries(referentialData).reduce((map, [name, list]) => {
    map[name] = list.reduce((itemMap, item) => {
      if ('score_id' in item) {
        itemMap[item.score_id] = item.label;
      } else if ('value' in item) {
        itemMap[item.value] = item.displayText;
      }
      return itemMap;
    }, {} as Record<string, string>);
    return map;
  }, {} as Record<string, Record<string, string>>);

  // 预构建路径到配置的映射
  const pathMap = usages.reduce((map, item) => {
    map[item.path] = item;
    return map;
  }, {} as Record<string, typeof usages[0]>);

  return (data: any, path: string[]): any => {
    if (!data || !pathMap) return data;
    const _path = path.filter(item => typeof item !== 'number').join('.');
    const config = pathMap[_path];

    if (!config || !config.referential_name) return data;
    const itemMap = refMap[config.referential_name];
    if (!itemMap) return data;

    return itemMap[data] || data;
  };
}

3. 修复“首次调用失败、二次调用成功”的异常 #

这个问题根源是累加器acc的默认参数是引用类型：首次调用后acc被修改，二次调用时复用了修改后的acc，导致逻辑异常。

• 迭代实现中每次调用都会创建全新的acc，直接解决该问题；
• 若坚持用递归，必须保证每次调用时手动传入全新的acc，不能依赖默认参数的引用值。

内容的提问来源于stack exchange，提问作者Loutag