================================================================== Hunk O starts here: ==================================================================
Many Scheme programs rely heavily on recursion, and Scheme makes it easy to use recursion in ways that aren't feasible in most other languages. In particular, you can write recursive procedures which call themselves instead of looping.
When a procedure calls itself in a way that is equivalent to iterating a loop, Scheme automatically "optimizes" it so that it doesn't need extra stack space. You can use recursion anywhere you could use a loop in a conventional language. Technically, loop-like recursion is called tail recursion, which we'll explain in detail in a later chapter.
The basic idea is that you never have to return to a procedure if all that procedure will do is return the same value to its caller. For example, consider the following procedure definition:
(define (foo) (bar) (baz))
When foo calls baz, it is a tail call, because on return
from baz, foo will do nothing except return the returned value
to its caller. That is, the return to foo from baz
will be immediately followed by a return to whatever procedure called
foo. There's really no need to do two returns, passing
through foo on the way back. Instead, Scheme avoids saving
foo's state before the call to baz, so that baz
can return directly to foo's caller, without actually
coming back to foo.
Tail-calling allows recursion to be used for looping, because a tail call that acts to iterates a loop doesn't save the caller's state on a stack.
Scheme systems can implement such tail calls as a kind of GOTO that passes arguments, without saving the state of the caller. This is not unsafe, like language-level GOTO's, because it's only done when the result would be the same as doing the extra returns.
Some compilers for languages such as Common Lisp and C perform a limited form of "tail call optimization," but Scheme's treatment of tail calls, is more general, and standardized, so you can use recursion more freely in your programs, without fear of stack overflow if you code your routines tail-recursively.
And of course, you can use recursion the way you would in most languages, as well as for loops, so recursion can do both jobs. While Scheme has conventional-looking looping constructs, they're defined in terms of recursion.