我想知道您如何在方案中实现尾递归幂函数?
我已经为方案定义了我的递归:
(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)
(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
是在退出过程之前发生的最后一件事顺便说一句,有一种更快的方法来实现整数求幂。与其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
(用于“结果”)。)
Ó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