Рекурсивный алгоритм инкрементной корректности в JavaScript

Question

Псевдокод для приращения натуральных чисел с использованием рекурсивного алгоритма выглядит следующим образом (пример из Руководства по разработке алгоритмов Стивена С. Скиены):

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), чтобы округлить, ноЯ предполагаю, что эта функция должна работать независимо от округления в большую или меньшую сторону.Итак, мой вопрос, есть ли способ исправить эту рекурсивную функцию в JS без использования Math.floor?

Answer 1

Javascript не имеет целочисленного деления, поэтому вы не можете просто сделать 5/2 и ожидать, что он даст вам 2.

Если вы ищете альтернативу Math.floor, на этом сайте есть информация о вас.Он имеет все альтернативы, которые вы когда-либо хотели, и может проверить, какие из них будут самыми быстрыми в вашем браузере.

Answer 2

Это не имеет ничего общего с 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 как двойные.Только двоичные операторы обрабатывают числа в JavaScript как 32-разрядное целое число со знаком.