在Racket中进行尾调用优化

Question

我正在做SICP 练习2.28并偶然发现以下代码的奇怪行为:

(define (fringe tree)
  (cond
    ((null? tree) '())
    ((not (pair? tree)) (list tree))
    (else (append (fringe (car tree)) (fringe (cdr tree))))))

(define (fringe-tail tree)
  (define (fringe-iter tree result)
    (cond
      ((null? tree) result)
      ((not (pair? tree)) (list tree))
      (else (fringe-iter (cdr tree) (append result (fringe-tail (car tree)))))))
  (fringe-iter tree '()))

(define x (make-list (expt 10 4) 4))
(time (fringe x))
(time (fringe-tail x))

普通fringe运行速度比其迭代版本快得多fringe-tail:

cpu time: 4 real time: 2 gc time: 0

与

cpu time: 1063 real time: 1071 gc time: 191

看起来它fringe被优化为循环并避免任何分配,而fringe-tail运行速度慢得多,花费时间创建和销毁对象.

任何人都可以向我解释这个吗？(以防我使用球拍5.2.1)

Answer 1

如果用以下内容替换最后一个子句:

(else (fringe-iter (cdr tree) (append (fringe-tail (car tree)) result)))

然后它们以相同的速度运行该输入,并且尾递归版本对于更大的输入更快.

问题在于你正在append使用更长的列表cdr来进行前端,这些列表的遍历和分配比天真的版本要多得多,后者将caron 的边缘附加到前面.