在方案中创建尾递归幂函数

Question

我想知道你如何在计划中实现尾部恢复功能？

我有一个为方案定义的递归方法:

(define power-is-fun
  (lambda (x y)
    (cond [(= y 0)
           1]
          [(> y 0)
           (* (power-is-fun x (- y 1)) x)])))

但我无法弄清楚另一个应该是怎样的.

Answer 1

答案类似,您只需将累积结果作为参数传递:

(define power-is-fun
  (lambda (x y acc)
    (cond [(= y 0)
           acc]
          [(> y 0)
           (power-is-fun x (- y 1) (* x acc))])))

像这样调用它,注意accis 的初始值1(你可以为它构建一个辅助函数,所以你不必记得1每次传递):

(power-is-fun 2 3 1)
> 8

一些将递归过程转换为尾递归的通用指针:

• 在函数中添加一个额外的参数以保存到目前为止累积的结果
• 在第一次调用过程时传递累加器的初始值,通常这与您在"正常"(非尾递归)递归中在基本情况下返回的值相同.
• 在递归的基本情况下返回累加器
• 在递归步骤中,使用新值更新累积结果并将其传递给递归调用
• 最重要的是:当调用递归时,请务必将其称为最后一个表达式,而不执行"额外工作".例如,在原始代码中,您在调用后执行了乘法power-is-fun,而在尾递归版本中,调用power-is-fun是在退出过程之前发生的最后一件事