我们有两个函数可以计算给定数字的阶乘。第一个,!
,使用累加器样式。第二个,fact
,使用自然递归。
(define (! n0)
(local (;; accumulator is the product of all natural numbers in [n0, n)
(define (!-a n accumulator)
(cond
[(zero? n) accumulator]
[else (!-a (sub1 n) (* n accumulator))])))
(!-a n0 1)))
和
(define (fact n)
(cond
[(= 0 n) 1]
[else (* n (fact (- n 1)))]))
在第 31 节的底部,HtDP指出自然递归版本通常与累加器版本一样快,但没有说明原因。我对此进行了一些阅读,似乎答案是“尾调用优化/消除”,但维基百科的文章似乎与 HtDP 所说的不一致,至少在性能方面。为什么会这样?
在工作中,递归风格更快。在家里,蓄能器风格更快。是否没有一般的启发式方法来指导选择通常首选哪种风格?我知道累加器样式更节省内存,但如果我们将讨论仅限于性能,至少对我来说不清楚,哪个是更好的选择。
我对此进行了更深入的考虑,并且不得不支持维基百科关于一般情况下累加器式递归的优越性的文章。它不仅减少了堆栈/堆空间的使用,而且内存访问总是落后于寄存器访问,并且只有在多核出现后才能更加明显。尽管如此,HtDP 证明在所有情况下都需要进行实际测试。