Javascript 中的递归不一致

Question

我编写了一些简短的递归代码，尝试通过 Javascript 中的 2D 数组找到最小路径和，仅从左上到右下向右或向下移动。代码对我来说似乎不错，但基本上它似乎对堆栈函数调用的输出感到困惑......

const a = [
  [ 3, 8, 8 ],
  [ 1, 4, 7 ],
  [ 8, 7, 1 ]
]
const w = a[0].length-1
const h = a.length-1
f = (s,x,y) => {
  s += a[y][x]
  console.error([s, x, y, x<w, y<h])
  if(x == w && y == h) return s
  r = x < w ? f(s,x+1,y) : 9999
  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))

对于此数组，它输出 11 而不是 16。在线尝试此操作！

仔细观察，问题出现在 (1,1) 处，它测试路径 4+7+1（右下）和 4+7+1（下右）。将最后一行更改为

console.log(f(4,1,1))

可以更容易看到。您将得到返回值

9

和以下错误输出：

[ 8, 1, 1, true, true ]
[ 7, 2, 1, false, true ]
[ 1, 2, 2, false, false ]
[ 7, 2, 1, 9999, 1, 8 ]
[ 7, 1, 2, true, false ]
[ 1, 2, 2, false, false ]
[ 7, 1, 2, 1, 9999, 8 ]
[ 8, 1, 1, 1, 8, 9 ]

(2, 1) 和 (1, 2) 路径都正确地将其路径总和评估为

8

(7+1)。但是当我们回到树中的 (1, 1) 节点时，它似乎认为正确的路径评估为

1

而不是

8

，因此它始终低估路径长度 7。我不能似乎明白为什么会发生这种情况。我是 JavaScript 新手。有人可以解释一下这里出了什么问题吗？

Answer 1

您得到 11 而不是 16 的原因是您没有将

r

定义为局部变量，而是（隐式）定义为全局变量。这意味着为

f

赋值的每次

r

执行都会对所有这些执行共享的 same 变量执行此操作。

因此，在对 r 赋值之后

进行的递归调用仍可能会更改 

r

 的值，因此会覆盖在进行递归调用的执行上下文中分配的内容。

如果将

r

 的赋值前缀加上 

const

，则输出将是预期的 16。

为了避免出现这样的意外，最好养成以下习惯：

• 使用

  let

  、

  const

   或 

  var

   声明变量，并且永远不要让它们隐式定义为全局变量。您可以通过在严格模式下运行来强制执行此习惯。

• 正确缩进您的代码。代码块的左大括号后面不应跟同一行的语句。属于代码块的缩进行。添加间距以使代码更具可读性。

• 用分号分隔您的语句。不要依赖自动分号插入系统来为您完成这项工作，而是要控制这方面。

• 使用描述性的变量名称。

  r

   和 

  d

   并没有立即表明它们的含义。 

  right

   和 

  down

   是更清晰的名称，使代码更容易理解。

这是应用了这些准则的代码，没有进行任何其他更改：

"use strict";

const matrix = [
    [ 3, 8, 8 ],
    [ 1, 4, 7 ],
    [ 8, 7, 1 ]
];

const maxX = matrix[0].length - 1;
const maxY = matrix.length - 1;
const getMinPathCost = (cost, x, y) => {
    cost += matrix[y][x];
    if (x == maxX && y == maxY) return cost;
    const right = x < maxX ? getMinPathCost(0, x + 1, y) : 9999;
    const down = y < maxY ? getMinPathCost(0, x, y + 1) : 9999;
    return right < down ? cost + right : cost + down;
}
console.log(getMinPathCost(0, 0, 0));

此代码还有更多可以改进的地方，例如：

使用
• Infinity

  代替9999来表示可能的最高成本

使用
• Math.min

   代替条件运算符来选择最小成本

使用动态规划（制表）以避免多次执行相同的
• x

  和

  y

  相同的过程

...但这超出了你的问题范围。