Tail call optimization in Racket
garbage-collection, racket, scheme, tail-call-optimization
Solution
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 `append`ing 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.
Problem
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)