4

我想知道您如何在方案中实现尾递归幂函数?

我已经为方案定义了我的递归:

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

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

4

3 回答 3

5

答案是类似的,你只需要将累积的结果作为参数传递:

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

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

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

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

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

于 2012-05-17T23:51:06.337 回答
1

Ó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

于 2012-05-17T12:18:30.640 回答