recursion - （方案）尾递归模幂

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)))))

我很难把头绕在这个尾递归上，我不知道如何“累积”剩余部分。对于这项任务，我几乎只能使用基本的数学运算符以及商和余数。

标签： recursionschememodulotail-recursionmodular-arithmetic

Answer 1

我看到您正在实现二进制求幂，并具有减少 mod r 的额外功能。

您可能想要做的是采用普通（尾递归）二进制求幂算法，只需将 2 元函数 + 和 * 更改为您自己的用户定义的 3 元函数 +/mod 和 */mode，它们也需要 r 和 reduce返回之前的结果 mod r。

现在你如何以尾递归的方式进行二进制取幂？您需要 main 函数调用一个辅助函数，该函数接受一个额外的累加器参数 - 初始值 1。这有点类似于使用辅助函数 REVAPPEND 的尾递归 REVERSE - 如果您熟悉的话。

希望对您有所帮助，并随时询问您是否需要更多信息。