在Scheme中创建一个尾递归的幂函数

Question

我想知道如何在Scheme中实现尾递归幂函数？

我已经定义了Scheme中的递归函数：

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

但是我无法弄清楚另一个应该是什么意思。

- Fedtekansler

Answer 1

答案类似，您只需要将累积结果作为参数传递：

(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是在退出过程之前发生的最后一件事情

- Óscar López

---

非常感谢您...这是在其他地方很难获得的信息 :) - Fedtekansler

Answer 2

顺便提一下，实现整数指数的更快方法是，而不是一次又一次地将 x 乘以 y 次（这使时间复杂度为 O(y)），有一种O(log y)的方法：

(define (integer-expt x y)
  (do ((x x (* x x))
       (y y (quotient y 2))
       (r 1 (if (odd? y) (* r x) r)))
      ((zero? y) r)))

如果你不喜欢do（像我认识的很多Scheme程序员一样），这里有一个显式地尾递归的版本（当然，你也可以用命名的let来写）：

(define (integer-expt x y)
  (define (inner x y r)
    (if (zero? y) r
        (inner (* x x)
               (quotient y 2)
               (if (odd? y) (* r x) r))))
  (inner x y 1))

顺便说一下，任何一个好的Scheme实现都应该将两个版本扩展成完全相同的代码。另外，就像Óscar的解决方案一样，我使用了一个累加器，只不过这里我把它称为r（表示“结果”）。

- C. K. Young

Answer 3

Óscar的建议清晰明了。

如果你想更深入地了解迭代（又称线性递归）和树形递归过程，那么一定不要错过SICP中的精彩讲解：

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2

- soegaard