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

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))])))

像这样调用它，注意它的初始值acc是1（你可以为此构建一个辅助函数，所以你不必记住1每次都传递）：

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

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

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

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（就像我认识的许多 Schemers 一样），这里有一个显式地尾递归的版本（let当然，你也可以用 named 来写它）：

(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（用于“结果”）。）

Answer 3

Óscar's list of advice is excellent.

If you like a more in-depth treatment of iterative (aka linear recursive) and tree recursion processes, then don't miss out on the great treatment in SICP:

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