Алгоритм расчета показателя с использованием рекурсии и мод

Меня учили другому способу вычисления показателей, используя мод и рекурсию, но я не совсем понимаю это. Метод: Чтобы сделать b^e , мы можем разбить его так:

  q = e div 2
  r = e mod 2
then e = 2q+r, and r could be 0 or 1.

If r=0:

    b^e = (b^q)^2

If r=1:

    b^e = (b^q)^2 * b

base case: b^0 = 1.

Например: 2^2, b=2, e=2 .

q = 2/2 = 1
r = 2mod2 = 0

r=0, therefore 2^2 = 2^1^2

Я пытаюсь закодировать это.

pow :: Integer -> Integer -> Integer
pow b e
    | e == 0 = 1
    | r == 0 = pow (pow b q) 2
    | r == 1 = b * pow (pow b q) 2
  where
    (q, r) = divMod e 2

Но код не заканчивается в любое время, когда e!=0 , например, pow (-2) 4 или pow 1 1 продолжается вечно. Есть идеи почему?

haskell exponent

Всего 2 ответа

Если вы попытаетесь оценить pow b 2 вручную, вы быстро поймете, почему. Поскольку divMod 2 2 = (1, 0) , мы расширяемся от pow b 2 до pow (pow b 1) 2 . Обратите внимание, что это также имеет вид pow b' 2 , где b' = pow b 1 . Итак, мы просто получаем бесконечную цепочку:

pow b 2
=
pow (pow b 1) 2
=
pow (pow (pow b 1) 1) 2
=
pow (pow (pow (pow b 1) 1) 1) 2
=
...

Есть несколько способов решить это. Вы можете добавить базовый регистр для e == 2 или вместо того, чтобы рекурсивно вызывать pow дважды, вы можете просто сделать умножение самостоятельно (как при замене pow foo 2 на foo * foo в существующем коде).

Вам также нужно предоставить базовый случай, когда e равно 2 :

pow b 2 = b * b

Без этого ваша рекурсия не заканчивается, потому что она становится pow (pow b 1) 2 и вы никуда не денетесь.