Suppose we want to write a filter function in Scheme:
;; Return a list containing all the ITEMS where PRED
;; returns #t.
(define (my-filter items pred)
(if (pair? items)
(if (pred (car items))
(cons (car items) (my-filter (cdr items) pred))
(my-filter (cdr items) pred))
'()))
This consumes stack space when pred returns #t, so we can get a
stack overflow:
;; Return a of MAX integers, from 0 to MAX-1.
(define (range max)
(define (range-iter i accum)
(if (= i max)
accum
(range-iter (+ i 1) (cons i accum))))
(range-iter 0 '()))
;; This gives a stack overflow (actual stack size varies between
;; implementations, tested on guile 2.0.11).
(define big-list
(my-filter (range 10000) (lambda (x) #t)))
We can rewrite our filter function to use an accumulator, so we don't get the stack overflow:
(define (my-filter items pred)
(define (my-filter-iter items accum)
(if (pair? items)
(if (pred (car items))
(my-filter-iter items (cons (car items) accum))
(my-filter (cdr items) pred))
accum))
(my-filter-iter items '()))
However, this still uses O(n) space! If our stack was unbounded, we wouldn't need to do this rewriting.
(Of course, there are cases where TCO turns an O(n) space function into an O(1) function, so the technique is certainly still useful.)