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

Question

У меня есть задание создать хвостовую рекурсивную функцию, которая принимает 3 целых числа (возможно, очень больших), pq и 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)))))

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

Answer 1

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

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

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

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