递归程序中shortestCombination为何不每次调用都重置？以bestSum为例

核心关键点：每个bestSum递归调用里的shortestCombination都是当前函数作用域的局部变量，不同层级的递归调用之间，这个变量完全独立，互不干扰。你看到的[3]、[3,2]、[5]其实是不同作用域下的shortestCombination被赋值的结果，下面用你的例子一步步拆解执行流程：

示例执行全流程（targetSum=5，numbers=[2,3,5]） #

1. 初始调用：bestSum(5, [2,3,5]) #

• 初始化当前作用域的shortestCombination = null

• 进入for循环，逐个遍历数组元素：

  第一个元素num=2

  • 计算remainder = 5-2 = 3，调用bestSum(3, [2,3,5])
  • 进入这个子调用的作用域：
    • 初始化shortestCombination = null
    • 遍历数组元素：
      • num=2：remainder=3-2=1，调用bestSum(1, [2,3,5])，该调用中所有num相减后remainder都小于0，最终返回null，跳过处理
      • num=3：remainder=3-3=0，调用bestSum(0, [2,3,5])，触发base case返回[]
        • 生成combination：[...[], 3] = [3]
        • 因为当前shortestCombination是null，直接赋值为[3]
      • num=5：remainder=3-5=-2，返回null，跳过处理
    • 该子调用结束，返回[3]
  • 回到初始调用的num=2处理：生成combination = [...[3], 2] = [3,2]
  • 初始调用的shortestCombination是null，赋值为[3,2]

  第二个元素num=3

  • 计算remainder=5-3=2，调用bestSum(2, [2,3,5])
  • 子调用作用域：
    • 初始化shortestCombination=null
    • num=2：remainder=0，返回[]，生成combination=[2]，赋值给shortestCombination
    • num=3、5的remainder都小于0，返回null，跳过
    • 子调用返回[2]
  • 初始调用中生成combination=[...[2], 3] = [2,3]，长度和当前shortestCombination的2相等，不更新

  第三个元素num=5

  • 计算remainder=5-5=0，调用bestSum(0, [2,3,5])返回[]
  • 生成combination=[...[],5] = [5]，长度1 < 当前shortestCombination的长度2，所以更新shortestCombination为[5]

• 初始调用结束，返回[5]

总结 #

你误以为是同一个shortestCombination在变化，但实际上每次递归调用都会创建一个全新的局部变量。上层调用的shortestCombination只会被当前循环中下层调用返回的有效组合更新，最终初始调用的shortestCombination会留存遍历所有可能后最短的组合。

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