Next: Local Call, Previous: Source Optimization, Up: Advanced Compiler Use and Efficiency Hints [Contents][Index]
A call is tail-recursive if nothing has to be done after the the call
returns, i.e. when the call returns, the returned value is immediately
returned from the calling function. In this example, the recursive
call to myfun
is tail-recursive:
(defun myfun (x) (if (oddp (random x)) (isqrt x) (myfun (1- x))))
Tail recursion is interesting because it is form of recursion that can be implemented much more efficiently than general recursion. In general, a recursive call requires the compiler to allocate storage on the stack at run-time for every call that has not yet returned. This memory consumption makes recursion unacceptably inefficient for representing repetitive algorithms having large or unbounded size. Tail recursion is the special case of recursion that is semantically equivalent to the iteration constructs normally used to represent repetition in programs. Because tail recursion is equivalent to iteration, tail-recursive programs can be compiled as efficiently as iterative programs.
So why would you want to write a program recursively when you can write it using a loop? Well, the main answer is that recursion is a more general mechanism, so it can express some solutions simply that are awkward to write as a loop. Some programmers also feel that recursion is a stylistically preferable way to write loops because it avoids assigning variables. For example, instead of writing:
(defun fun1 (x) something-that-uses-x) (defun fun2 (y) something-that-uses-y) (do ((x something (fun2 (fun1 x)))) (nil))
You can write:
(defun fun1 (x) (fun2 something-that-uses-x)) (defun fun2 (y) (fun1 something-that-uses-y)) (fun1 something)
The tail-recursive definition is actually more efficient, in addition to being
(arguably) clearer. As the number of functions and the complexity of their
call graph increases, the simplicity of using recursion becomes compelling.
Consider the advantages of writing a large finite-state machine with separate
tail-recursive functions instead of using a single huge prog
.
It helps to understand how to use tail recursion if you think of a
tail-recursive call as a psetq
that assigns the argument values to the
called function’s variables, followed by a go
to the start of the called
function. This makes clear an inherent efficiency advantage of tail-recursive
call: in addition to not having to allocate a stack frame, there is no need to
prepare for the call to return (e.g., by computing a return PC.)
Is there any disadvantage to tail recursion? Other than an increase in efficiency, the only way you can tell that a call has been compiled tail-recursively is if you use the debugger. Since a tail-recursive call has no stack frame, there is no way the debugger can print out the stack frame representing the call. The effect is that backtrace will not show some calls that would have been displayed in a non-tail-recursive implementation. In practice, this is not as bad as it sounds—in fact it isn’t really clearly worse, just different. See debug-tail-recursion for information about the debugger implications of tail recursion, and how to turn it off for the sake of more conservative backtrace information.
In order to ensure that tail-recursion is preserved in arbitrarily
complex calling patterns across separately compiled functions, the
compiler must compile any call in a tail-recursive position as a
tail-recursive call. This is done regardless of whether the program
actually exhibits any sort of recursive calling pattern. In this
example, the call to fun2
will always be compiled as a
tail-recursive call:
(defun fun1 (x) (fun2 x))
So tail recursion doesn’t necessarily have anything to do with recursion as it is normally thought of. See local-tail-recursion for more discussion of using tail recursion to implement loops.
Next: Local Call, Previous: Source Optimization, Up: Advanced Compiler Use and Efficiency Hints [Contents][Index]