基于递归实现数组归约求和的优化与递归逻辑疑问

问题背景 #

给定一个长度为n的数组，需通过不断将相邻索引的元素配对相加，直到数组仅剩单个元素。
示例：

[1, 2, 3, 4, 5] => 48
解释：

• 下一个数组为[3, 5, 7, 9]，由[1+2, 2+3, 3+4, 4+5]得到
• 下一个数组为[8, 12, 16]，由[3+5, 5+7, 7+9]得到
• 下一个数组为[20, 28]，由[8+12, 12+16]得到
• 最终结果为[48]，由[20+28]得到，此时无足够元素可继续相加

现有代码与疑问 #

我已经写出了下面的JavaScript解决方案，但觉得有更简洁的实现方式。目前正在学习递归，搞不懂递归调用时为什么要用(n-1)或(n+1)来触发基准条件，也不知道该选哪一个；同时也不明白返回辅助函数时传递这些参数的原因。

现有代码 #

function reduceSum(input) {
  function simplify(input, index) {
    if (index === 1) {
      return input[0];
    }

    if (index === 0) {
      return 0;
    }

    for (let i = 0; i < input.length; i++) {
      input[i] += input[i + 1];
    }

    return simplify(input, index - 1);
  }

  return simplify(input, input.length);
}

// 测试用例
console.log(reduceSum([1, 2, 3, 4]) == 20)
console.log(reduceSum([5]) == 5)
console.log(reduceSum([]) == 0)
console.log(reduceSum([1, 3, 5]) == 12)
console.log(reduceSum([-5, 5]) == 0)
console.log(reduceSum([-5, 5, -5, 5]) == 0)
console.log(reduceSum([-5, 5, 5, -5]) == 20)

递归逻辑解析与优化方案 #

递归中n-1/n+1的选择逻辑 #

递归的核心是逐步缩小问题规模，直到触达基准条件。拿你的代码来说：

• 初始传入的index是数组的长度input.length，每一轮相邻累加后，数组的有效处理长度会从k变成k-1（比如长度5→4→3→2→1）
• 所以用index-1是因为每处理一次，问题的规模（当前需要处理的数组长度）就减1，直到index===1（只剩一个元素）或者index===0（空数组）的基准条件，这时候直接返回结果，停止递归。

如果用n+1，通常是问题需要从小规模逐步扩大到某个上限（比如从1开始累加直到n），但你的问题是从n缩小到1，所以必然用n-1。选择的关键看：你的递归是要把大问题拆解成更小的子问题，还是从小问题逐步构建大问题。

辅助函数传递参数的原因 #

你代码里的index参数是用来跟踪当前需要处理的数组“目标长度”——因为你在循环里直接修改了原数组的内容，但原数组的实际长度并没有实时缩短（比如原数组长度是5，第一次循环后你修改了前4个元素，但数组长度还是5），这时候用index来标记下一轮需要按长度为4的逻辑处理。不过这种直接修改原数组的方式容易产生副作用，不是最优写法。

更简洁的递归实现 #

我们可以不用修改原数组，每一轮生成新的相邻和数组，逻辑更清晰，也不需要额外的index参数：

function reduceSum(input) {
  // 基准条件：空数组返回0，单元素返回自身
  if (input.length === 0) return 0;
  if (input.length === 1) return input[0];
  // 生成下一轮数组：取前n-1个元素，每个和下一个元素相加
  const nextArr = input.slice(0, -1).map((num, i) => num + input[i+1]);
  // 递归处理下一轮数组
  return reduceSum(nextArr);
}

这个版本的逻辑直观：每一步基于当前数组生成下一轮的相邻和数组，再递归处理这个新数组，直到触达基准条件。

进一步优化：数学公式法（非递归） #

其实这个问题可以用数学规律简化：原数组中每个元素的权重是组合数C(n-1, k)，其中n是原数组长度，k是元素的索引（从0开始）。比如原数组[1,2,3,4,5]，n=5，各元素的权重是C(4,0)=1，C(4,1)=4，C(4,2)=6，C(4,3)=4，C(4,4)=1，计算得11 + 24 +36 +44 +5*1 = 48，和示例一致。

用这个规律可以直接计算，效率远高于递归/迭代：

// 计算组合数C(a,b)
function comb(a, b) {
  if (b === 0 || b === a) return 1;
  b = Math.min(b, a - b);
  let res = 1;
  for (let i = 1; i <= b; i++) {
    res = res * (a - b + i) / i;
  }
  return res;
}

function reduceSum(input) {
  const n = input.length;
  if (n === 0) return 0;
  return input.reduce((sum, num, idx) => sum + num * comb(n-1, idx), 0);
}

这个方法的时间复杂度是O(n)，比递归/迭代的O(n²)效率高很多，适合处理长数组。

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