javascript - JavaScript 中的增量正确性递归算法

Question

使用递归算法递增自然数的伪代码如下(示例来自 Steven S. Skiena 的算法设计手册):

Increment(y)
 if y = 0 then return(1) else
  if (y mod 2) = 1 then
      return(2 * Increment(y/2))
  else return(y + 1)

我在这里用 JavaScript 实现了它:https://repl.it/@danielmai/IncrementalNaturalNumbers

function increment(y) {
  if(y == 0) return 1
  if(y % 2 == 1) {
    return 2 * increment(y / 2)
  }
  else return y + 1
}

它不适用于奇数。我发现 JavaScript 将数字取整为 0.5 或更高，因此如果 y 是奇数，它将递增两次，即 5 -> 7。

我可以使用 Math.floor(y/2) 使其向下舍入，但我认为无论向上或向下舍入，此函数都应该有效。所以我的问题是，有没有一种方法可以在不使用 Math.floor 的情况下更正 JS 中的这个递归函数？

Answer 1

这与 javascript 将数字四舍五入为 0.5 或更高无关。

您的增量函数假设 x/2 将返回一个整数，但在 javascript 中，这将在奇数时给出一个小数。所以在执行 increment(3) 时，你是在递归调用 increment(1.5)。因为 1.5 % 2 = 1.5，它不是 == 1，所以它最终返回 2.5。所以最后，您最终会返回 2.5 * 2 = 5。

此函数确实适用于 C++，如果您使用整数，除法将去除尾随小数。但是，在 JavaScript 中，加法 +、减法 -、乘法 *、除法/、幂 ** 和模 % 都将 JavaScript 中的数字视为 double 。只有二​​元运算符将 JavaScript 中的数字视为带符号的 32 位整数。