我有一个任务是做一个尾递归函数,它有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)))))我很难把这个尾递归包起来,我不知道如何才能“累积”剩下的部分。在这项任务中,我只能使用基本的数学运算符、商和余数。
发布于 2019-04-25 05:29:28
我看到你正在实现二进制求幂,还有一个额外的特性,那就是它的模数减少了。
您可能想要做的是采用普通(尾部递归)二进制求幂算法,并简单地将2元函数+和*更改为您自己定义的3元函数+/mod和*/mode,这些函数也采用r并在返回之前减少结果mod r。
现在,如何在尾部递归方式中进行二进制求幂?你需要main函数来调用一个辅助函数,该函数需要一个额外的累加器参数-初始值1。这有点类似于使用辅助函数REVAPPEND的尾递归反转-如果你熟悉的话。
希望这对你有所帮助,如果你需要更多信息,请随时询问。
https://stackoverflow.com/questions/52635937
复制相似问题