Tail Recursion

Abstract

This reading provides further analysis of recursion, and it introduces the concept of tail recursion. The reading includes several examples of how non-tail-recursive procedures can be rewritten to become tail recursive.

This reading proceeds by considering several solutions to various problems.

Problem -- Sum: Find the sum of a list of numbers.

Solution 1:

The first solution seems to follow a now-familiar recursive format:

(define sum 
   (lambda (ls)
       (if (null? ls)
           0
           (+ (car ls) (sum (cdr ls)))
       )
   )
)

While this procedure works correctly, it is not terribly efficient either in terms of time or required memory within the machine. To understand why, we trace the execution of this procedure on the list (1 2 3 4).

Here, when we type (sum '(1 2 3 4)) the machine checks for a null list, recognizes that '(1 2 3 4) is not null, and goes the the else clause of the if. This means that sum will be called recursively with parameter (2 3 4). However, once (sum '(2 3 4)) is computed, we still will have to add 1 to the result to get the final answer. Thus, the machine will need to store 1 until the recursive step is completely done. Similar comments apply at each stage. Thus, when the machine finally evaluates (sum '()) and obtains 0, the sum has been called 5 times, and intermediate values are stored at each stage.

While this solution is correct, after the base case is computed (at the right of the above diagram), the machine must come back one call at a time, using previous results and making further computations.

Solution 2:

The next solution adds a running sum parameter.

(define sum 
   (lambda (ls)
       (sum-kernel ls 0)
   )
)
(define sum-kernel
   (lambda (ls running-sum)
       (if (null? ls)
           running-sum
           (sum-kernel (cdr ls) (+ running-sum (car ls)))
       )
   )
)

In this approach, recursion proceeds from (1 2 3 4) toward the null list (). However, once this base case is reached, the result (10) is returned directly by each preceding procedure call. In this case, the machine does not need to combine the result at one stage with values at a previous stage, so earlier values need not be stored during recursion. This direct return of a result following recursion is called tail recursion. The following diagram provides a graphical picture of this processing.

Since Scheme is sophisticated enough to identify when tail recursion is present, tail recursion can run particularly efficiently within Scheme.

Problem -- Maximum: Find the maximum value within a list of numbers

To find a maximum, there must be at least one item on the list. Otherwise, a maximum will be undefined. Thus, the base case arises when a list contains just one element.

Solution 1:

The first solution is particularly unsophisticated:

(define maximum 
   (lambda (ls)
       (cond ((null? (cdr ls)) (car ls))  
             ((< (car ls) (maximum (cdr ls))) (maximum (cdr ls)))
             (else (car ls))
       )         
   )
)

Solution 2:

To save the multiple calls to maximum for both the test and the result (e.g., in the < case), it is appropriate to store the current maximum as a new parameter to a kernel procedure.

(define maximum 
   (lambda (ls)
      (maximum-kernel (car ls) (cdr ls))
   )
)

(define maximum-kernel
   (lambda (max-so-far lst)
       (cond ((null? lst) max-so-far)
             ((< (car lst) max-so-far) (maximum-kernel max-so-far (cdr lst)))
             (else (maximum-kernel (car lst) (cdr lst)))
       )         
   )
)

Solution 3:

The following is a variation of the Solution 2.

(define maximum 
   (lambda (ls)
      (maximum-kernel (car ls) (cdr ls))
   )
)

(trace-define maximum-kernel
   (lambda (max-so-far lst)
       (if (null? lst) 
           max-so-far
           (maximum-kernel (if (< (car lst) max-so-far) 
                               max-so-far
                               (car lst))
                           (cdr lst)
           )
       )         
   )
)

In this approach, the base case of the recursion is handled in one if statement. Also, since the recursive case always calls maximum-kernel with (cdr lst), the only question is which value should be used for the new maximum value in this call. Placing the if statement in the call as the first parameter clarifies the value to be used.

This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/153.sp05/readings/reading-tail-recursion.shtml

created March 7, 1997 last revised February 1, 2005
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.