Tail Recursion

Goals

This laboratory provides further analysis of recursion and tail recursion-- giving examples of how non-tail-recursive procedures can be rewritten to become tail recursive.

Finding the sum of numbers on a list

Consider the following two solutions to the problem of finding 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)))
       )
   )
)

Solution 2:

The second 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)))
       )
   )
)

1. Change the define statement to trace-define for both versions of sum above. (For the second version, also use trace-define to declare sum-kernel.) Run each version of sum on the list '(1 2 3 4), as in the above example. Comment on how the traces of these versions relate to the call diagrams in the readings for this lab.

Finding the maximum value on a list of numbers

Next consider some solutions for finding the maximum value within a list of numbers.

Solution 1:

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

2. Change define to trace-define and run the code for (maximum '(2 6 4)). How many times is maximum called? Explain briefly how this number is obtained.

3. Draw a diagram, such as the ones in the reading, to trace the procedure calls for the procedure call (maximum '(2 6 4)). Be sure your diagram agrees with the count determined from step 2.

Solution 2:

Using an additional parameter in 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)))
       )         
   )
)

4. As before, change define to trace-define and run the code for (maximum '(2 6 4)). How many times are maximum and maximum-kernel called? Explain briefly how this number is obtained.

5. Draw a diagram, such as the ones above, to trace the procedure calls for the procedure call (maximum '(2 6 4)).

   Explain why this approach is more efficient that the previous solution.

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)
           )
       )         
   )
)

6. Again, change define to trace-define and run the code for (maximum '(2 6 4)). How many times are maximum and maximum-kernel called? Explain briefly how this number is obtained.

7. Draw a diagram, such as the ones above, to trace the procedure calls for the procedure call (maximum '(2 6 4)).

8. Compare the efficiency of Solution 3 with that of Solutions 1 and 2. What conclusions can you make about the various solutions? Which solution do you prefer? Justify your preference briefly.

   Run the traces again, this time for the list '(2 6 4 5)). Explain how the patterns you observed for a 3-element list extend to this list of 4-element list.

Problem -- Average: Find the average of the numbers within a list.

Solution Outline:

Since an average requires both a sum of the items and a count of the number of items present, any solution must do both tasks. A tail recursive approach to this problem uses parameters to keep a running sum and a running count of the number of items processed.

9. Write a tail recursive solution to this problem, using a separate kernel procedure.

Problem -- Maximum, Minimum, and Average: Find the maximum, minimum, and average of a list of numbers.

Comment:

Since three results are desired, we must decide how these results should be returned. One natural approach would be to place all three results on a single list, with the maximum first, the minimum second, and the average third.

10. Write a tail recursive solution to this problem, using a single kernel procedure. The kernel procedure may have as many parameters as desired.

Work to be turned in:

• Comments for parts 1, 2, 4, 6, and 8.
• A diagram, with some explanation, for parts 3, 5, and 7.
• Programs for parts 9 and 10.

This document is available on the World Wide Web as

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

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