JavaScript三向分治算法计算数组和出现undefined及栈溢出问题求解

问题根源 #

• 初始递归调用错误：代码递归时错误调用了仅接收数组单参数的divideAndConquerSum，而非设计用来处理子区间的divideAndConquerSumMerge，传入的low、high参数完全失效，逻辑紊乱直接返回undefined。
• 分割点未取整：JS中/运算符默认返回浮点数，而数组索引必须为整数，未做取整处理会导致边界判断high == low永远无法命中，递归无限执行最终触发栈溢出。
• 区间拆分逻辑错误：原有拆分方式跳过了mid1、mid2两个位置的元素，区间衔接存在断层，同时缺少对长度小于3的子数组的边界处理逻辑。

正确实现代码 #

function divideAndConquerSum(a) {
  // 空数组直接返回0
  if (a.length === 0) return 0;
  return divideAndConquerSumMerge(a, 0, a.length - 1);
}

function divideAndConquerSumMerge(a, low, high) {
  // 边界1：空区间返回0
  if (low > high) return 0;
  // 边界2：单个元素直接返回值
  if (high === low) return a[low];
  // 边界3：两个元素直接求和无需拆分
  if (high === low + 1) return a[low] + a[high];

  // 分割点向下取整保证是整数索引
  const mid1 = Math.floor(low + (high - low) / 3);
  const mid2 = Math.floor(mid1 + (high - low) / 3);

  // 三个连续区间求和，无遗漏无重叠
  return (
    divideAndConquerSumMerge(a, low, mid1) +
    divideAndConquerSumMerge(a, mid1 + 1, mid2) +
    divideAndConquerSumMerge(a, mid2 + 1, high)
  );
}

let a = [1, 5, -1, 4];
console.log(divideAndConquerSum(a)); // 输出9符合预期

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