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

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

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

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

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

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

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

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

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

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

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

相关文章
相关标签/搜索