（Scheme）尾递归模幂运算

Question

我有一个赋值来做一个尾递归函数，它取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)))))

我很难缠绕我的头部使这个尾部递归，我不知道如何“累积”其余部分。我几乎只限于使用基本的数学运算符和商和余数来完成这项任务。

Answer 1

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

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

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

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