JavaScript递归求二维数组最小路径和的结果不一致问题

你的代码问题出在变量r和d没有使用let或const声明，导致它们成为全局变量。在递归嵌套调用过程中，后续的递归会覆盖这些全局变量的值，从而让前面的递归拿到错误结果。

具体问题分析 #

结合你提供的调试日志，处理节点(1,1)时的错误逻辑如下：

1. 首先调用右侧路径f(s,2,1)：
   • 进入(2,1)的递归后，调用下方路径f(s,2,2)，返回值1被赋值给全局变量d
   • (2,1)计算完成后返回8，此时全局变量r被设为8
2. 回到(1,1)处理下方路径f(s,1,2)：
   • 调用右侧路径f(s,2,2)，返回值1被赋值给全局变量r
   • (1,2)计算完成后返回8，此时全局变量d被设为8
3. 回到(1,1)的逻辑时，本应拿到右侧路径的返回值8和下方路径的返回值8，但r已经被后续递归覆盖成1，最终错误选择1作为较小值，导致路径和计算偏小。

修复后的代码 #

给r和d加上let声明，让它们成为函数的局部变量，每个递归栈帧都拥有独立的变量副本：

const a = [
  [ 3, 8, 8 ],
  [ 1, 4, 7 ],
  [ 8, 7, 1 ]
]
const w = a[0].length-1
const h = a.length-1
const f = (s,x,y) => {
  s += a[y][x]
  console.error([s, x, y, x<w, y<h])
  if(x == w && y == h) return s
  // 用let声明局部变量r和d
  let r = x < w ? f(s,x+1,y) : 9999
  let d = y < h ? f(s,x,y+1) : 9999
  console.error([s, x, y, r, d, r < d ? r : d])
  return r < d ? r : d
}
console.log(f(0,0,0))

运行修复后的代码，会得到正确结果16。

额外提醒 #

在JavaScript中，未声明的变量会自动挂载到全局作用域，这种行为极易引发难以排查的bug。养成变量先声明再使用的习惯，优先用const，需要修改时用let，避免使用未声明的变量。

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