Tail call optimization in Racket

Question

I was doing SICP exercise 2.28 and stumbled upon a strange behaviour of the following code:

(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))

Ordinary fringe runs much faster than its iterative version fringe-tail:

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

vs.

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

It looks like fringe was optimized into loop and avoids any allocations, while fringe-tail runs much slower and spends time creating and destroying objects.

Can anyone explain this to me? (Just in case I'm using racket 5.2.1)

Answer 1

If you replace the last clause with:

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

then they run at the same speed for that input, and the tail-recursive version is faster for larger input.

The problem is that you're appending the much longer list for the cdr on to the front, which traverses and allocates much more than the naive version, which appends the fringe of the car on to the front.