Teach Yourself Scheme: 6.3 Iteration

countdown defined above is really a recursive procedure. Scheme can define loops only through recursion. There are no special looping or iteration constructs.

Nevertheless, the loop as defined above is a genuine loop, in exactly the same way that other languages bill their loops. Ie, Scheme takes special care to ensure that recursion of the type used above will not generate the procedure call/return overhead.

Scheme does this by a process called tail-call elimination. If you look closely at the countdown procedure, you will note that when the recursive call occurs in countdown's body, it is the tail call, or the very last thing done -- each invocation of countdown either does not call itself, or when it does, it does so as its very last act. To a Scheme implementation, this makes the recursion indistinguishable from iteration. So go ahead, use recursion to write loops. It's safe.

Here's another example of a useful tail-recursive procedure:

(define list-position
  (lambda (o l)
    (let loop ((i 0) (l l))
      (if (null? l) #f
          (if (eqv? (car l) o) i
              (loop (+ i 1) (cdr l)))))))

list-position finds the index of the first occurrence of the object o in the list l. If the object is not found in the list, the procedure returns #f.

Here's yet another tail-recursive procedure, one that reverses its argument list ``in place'', ie, by mutating the contents of the existing list, and without allocating a new one:

(define reverse!
  (lambda (s)
    (let loop ((s s) (r '()))
      (if (null? s) r
	  (let ((d (cdr s)))
            (set-cdr! s r)
	    (loop d s))))))

(reverse! is a useful enough procedure that it is provided primitively in many Scheme dialects, eg, MzScheme and Guile.)

Prev Up Next