(Схема) Хвостовое рекурсивное модульное возведение в степень

У меня есть задание сделать функцию хвостовой рекурсии, которая принимает 3 целых числа (возможно, очень больших), p q и r и вычисляет модуль деления (p ^ q)/r. Я понял, как сделать функцию, которая достигает цели, но не является хвостовой рекурсией.

(define (mod-exp p q r)
  (if (= 0 p)
      0
      (if (= 0 q)
          1
          (if (= 0 (remainder r 2))
              (remainder (* (mod-exp p (quotient q 2) r)
                            (mod-exp p (quotient q 2) r))
                         r)
              (remainder (* (remainder p r)
                            (remainder (mod-exp p (- q 1) r) r))
                         r)))))

Мне трудно обдумать, как сделать эту хвостовую рекурсию, я не понимаю, как я могу «накапливать» остаток. Я в значительной степени ограничен использованием основных математических операторов, частного и остатка для этой задачи.


person gunnnnii    schedule 03.10.2018    source источник
comment
Начните с обычного возведения в степень с хвостовой рекурсией, затем добавьте remainder по мере необходимости. (Необходимо добавить параметр накопления.)   -  person molbdnilo    schedule 04.10.2018


Ответы (1)


Я вижу, что вы реализуете двоичное возведение в степень с дополнительной функцией, заключающейся в уменьшении по модулю r.

Что вы можете сделать, так это взять нормальный (хвостовой рекурсивный) двоичный алгоритм возведения в степень и просто изменить 2-мерные функции + и * на ваши собственные 3-мерные функции, определенные пользователем +/mod и */mode, которые также принимают r и уменьшают результат mod r перед его возвратом.

Теперь, как вы делаете двоичное возведение в степень хвостовым рекурсивным способом? Вам нужна основная функция для вызова вспомогательной функции, которая принимает дополнительный параметр-аккумулятор — начальное значение 1. Это похоже на хвостовую рекурсию REVERSE с использованием вспомогательной функции REVAPPEND — если вы знакомы с этим.

Надеюсь, что это поможет, и не стесняйтесь спрашивать, нужна ли вам дополнительная информация.

person rain1    schedule 24.04.2019