Prev Up Next
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