递归与累加器样式的表现

Question

我们有两个函数来计算给定数字的阶乘.第一个,!使用累加器样式.第二种,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证明在所有情况下都需要进行实际测试.

Answer 1

答案取决于Racket系统的细节.这是我的看法.

自然递归版本和累加器版本之间存在两个主要差异.首先,累加器版本以允许尾调用优化的方式编写.这有助于使累加器版本更快,因为需要创建更少的堆栈帧.但这与HtDP中讨论的内容相反,并且您已经在工作计算机上看到过.

另一个区别是乘法的顺序.自然递归版本按升序将数字从1倍增加到20,即

((((1 * 2) * 3) * … * 19) * 20)

累加器版本按降序乘以相同的数字,即

((((20 * 19) * 18) * … * 2) * 1)

在数学上,这些是相同的,并且两个阶乘函数将给出相同的结果.尽管如此,这种差异可能很重要.特别是,在任何中间乘法中,后一计算的中间结果将大于前一计算.

20的阶乘是一个很大的数字.它不适合32位整数.这意味着球拍将需要使用任意长度的整数("bignum")来表示答案,以及一些中间结果.任意精度算术,包括涉及bignums的乘法,都比固定精度算术慢.

由于累加器版本中的中间结果总是大于自然递归版本,因此累加器版本将需要比递归版本更早的bignum.简而言之,虽然两个版本都需要相同数量的乘法,但累加器版本需要更多的任意精度乘法.这使累加器版本变慢.显然,算术的额外成本超过了减少堆栈帧数的节省.

那么为什么同样的趋势不会出现在你的家用电脑上呢？你说它是英特尔iMac,所以它可能是一个64位系统.20岁!是一个很大的数字,它与64位整数相比较小,所以你的家用计算机没有做任何精度算术,顺序无关紧要.HtDP已经足够老,它可以使用32位系统,就像你的工作计算机上的Windows XP一样.

探索差异更有用的是计算数字列表的乘积的函数

(define (product numlist)
  (* (car numlist) (product (cdr numlist)))

或累加器版本.然后,您可以按升序或降序输入数字,而不管您是使用自然递归还是基于累加器的方法.