首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >(方案)尾递归模幂运算

问(方案)尾递归模幂运算
EN

Stack Overflow用户
提问于 2018-10-04 05:28:27
回答 1查看 300关注 0票数 1

我有一个任务是做一个尾递归函数,它有3个整数(可能非常大),p,q和r,然后计算除法(p^q)的模数(/r)。我想出了如何做一个达到目标的函数,但它不是尾递归函数。

代码语言:javascript
复制
(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)))))

我很难把这个尾递归包起来,我不知道如何才能“累积”剩下的部分。在这项任务中,我只能使用基本的数学运算符、商和余数。

EN

回答 1

Stack Overflow用户

发布于 2019-04-25 05:29:28

我看到你正在实现二进制求幂,还有一个额外的特性,那就是它的模数减少了。

您可能想要做的是采用普通(尾部递归)二进制求幂算法,并简单地将2元函数+和*更改为您自己定义的3元函数+/mod和*/mode,这些函数也采用r并在返回之前减少结果mod r。

现在,如何在尾部递归方式中进行二进制求幂?你需要main函数来调用一个辅助函数,该函数需要一个额外的累加器参数-初始值1。这有点类似于使用辅助函数REVAPPEND的尾递归反转-如果你熟悉的话。

希望这对你有所帮助,如果你需要更多信息,请随时询问。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/52635937

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档