Contents Next: Timing Function Calls Up: Recursion and Iteration Previous: When To Use

Tail Recursion

Item (1) above is only a rough rule of thumb. If you get to the stage of compiling your Lisp code (a compiler takes code in a programming language and turns it into binary machine language to make it run faster) some compilers are smart enough to distinguish tail-recursive processes from those that are not. None of the above examples of recursive functions are tail recursive. To be tail-recursive, the answer ultimately returned by the top-level call to the function must be identical to the value returned by the very bottom level call. In the trace output from power, above, you can see that the ultimate answer, 81, is not the same as the deepest level returned value which was 1, so power is not a tail-recursive function.

This function has the property of being tail-recursive:

(defun mymax (nums)                      ;; finds the largest
  (cond ((= (length nums) 1) (car nums)) ;; termination
        ((>  (car nums) (cadr nums))      ;; first >  second so
         (mymax (cons (car nums) 
                      (cddr nums))))     ;; get rid of second
        (t (mymax (cdr nums)))))         ;; else dump first

If you trace this function applied to a list of numbers you will see something like the following:

> (MYMAX '(1 3 412 43 1 1 3412 53 43 43 54))
  1>  (MYMAX (1 3 412 43 1 1 3412 53 43 43 54))
    2>  (MYMAX (3 412 43 1 1 3412 53 43 43 54))
      3>  (MYMAX (412 43 1 1 3412 53 43 43 54))
        4>  (MYMAX (412 1 1 3412 53 43 43 54))
          5>  (MYMAX (412 1 3412 53 43 43 54))
            6>  (MYMAX (412 3412 53 43 43 54))
              7>  (MYMAX (3412 53 43 43 54))
                8>  (MYMAX (3412 43 43 54))
                  9>  (MYMAX (3412 43 54))
                    10>  (MYMAX (3412 54))
                    11>  (MYMAX (3412))
                    <11 (MYMAX 3412)
                    <10 (MYMAX 3412)
                  <9 (MYMAX 3412)
                <8 (MYMAX 3412)
              <7 (MYMAX 3412)
            <6 (MYMAX 3412)
          <5 (MYMAX 3412)
        <4 (MYMAX 3412)
      <3 (MYMAX 3412)
    <2 (MYMAX 3412)
  <1 (MYMAX 3412)
3412

Notice that the answer 3412 is carried all the way from the bottom to the top-level. Mymax is a tail-recursive function.

When compiling Lisp code, a ``smart'' compiler is capable of recognizing tail recursion, and cutting off processing as soon as the lowest level returns. This can greatly speed up the operation of recursive functions.