Tail Recursion

How to make your recursive procedures run more quickly by taking advantage of a notion called tail recursion.

Recursive Strategies

In writing recursive procedures, you may have noticed that there are two general strategies for dealing with the result of the recursive call: (1) you can just return the result; or (2) you can do something with the result. For example, the member? procedure just returns the result of the recursive call and the factorial and add-to-all procedures do something with the result (multiply by something and cons to it, respectively).

;;; STANDARD POSTCONDITIONS:
;;; Unless specified otherwise, procedures
;;;   (1) do not modify their parameters
;;;   (2) do not read any input
;;;   (3) do not write any output

;;; Procedure:
;;;   member?
;;; Parameters:
;;;   A value
;;;   A list of values
;;; Purpose:
;;;   Determines if the value is in the list
;;; Produces:
;;;   #t if it is, #f otherwise
;;; Preconditions:
;;;   The parameters have the appropriate types.
;;; Postconditions:
;;;    Just the standard ones
(define member?
  (lambda (val values)
    (cond (
           ; Nothing is in the empty list
           ((null? values) #f)
           ; If it's the first element, it's in the list
           ((equal? val (car values)) #t)
           ; Otherwise, look through the rest of the list
           (else (member? (val (cdr values))))))))

;;; Procedure:
;;;   factorial
;;; Parameters:
;;;   n, a non-negative integer
;;; Purpose:
;;;   Computes n! = 1*2*3*...*n
;;; Produces:
;;;   n!, a positive integer
;;; Preconditions:
;;;   n is a non-negative integer [unchecked]
;;; Postconditions:
;;;   Just the standard ones
(define factorial
  (lambda (n)
    (if (<= n 0) 1
        (* n (factorial (- n 1))))))

;;; Procedure:
;;;   add-to-all
;;; Parameters:
;;;   value, a number
;;;   values, A list of numbers
;;; Purpose:
;;;   Creates a new list by adding value to each member of values.
;;; Produces:
;;;   A new list of numbers with the desired characterisitc.
;;; Preconditiosn:
;;;   value is a number [unchecked]
;;;   values is a list of numbers [unchecked]
;;; Postconditions:
;;;   Just the standard ones
(define add-to-all
  (lambda (value values)
    (if (null? values) null
        (cons (+ value (car values)) 
              (add-to-all value (cdr values))))))

If you think about how you might simulate these by hand, you'll notice that it's harder to deal with the second type of procedures because you have to spend extra effort remembering "the stuff left to do after the recursive call is done".

Husk-and-Kernel, Revisited

In previous labs, we've seen several examples illustrating the idea of separating the recursive kernel of a procedure from a husk that performs the initial call. Sometimes we've done this in order to avoid redundant precondition tests, or to prevent the user from bypassing the precondition tests. In other cases, we saw that the recursion can be written more naturally if the recursive procedure has an additional argument, not supplied by the original caller.

We can use husk-and-kernel techniques to make some non-tail-recursive procedures tail recursive.

(define factorial 
  ; Define a kernel that "accumulates" the previous multiplications
  ; as a second parameter.  Now we're computing n*(n-1)*...*(m+1)*m!
  (letrec ((kernel (lambda (m acc)
                     ;;
                     (if (<= m 0) (* 1 acc)
                         (kernel (- m 1) (* acc m))))))
    (lambda (n)
      (kernel n 1))))

Efficiency and Tail Recursion

There is yet another reason for adopting tail recursion, and it has to do with efficiency. An implementation of Scheme is required to perform tail-call elimination -- to implement procedure calls in such a way that, if the last step in procedure A is a call to procedure B (so that A will simply return to its caller whatever value is returned by B), the memory resources supporting the call to A can be freed and recycled as soon as the call to B has been started. To make this possible, the implementer arranges for B to return its value directly to A's caller, bypassing A entirely. In particular, this technique is required to work when A and B are the same procedure, invoking itself recursively (in which case the recursion is called tail recursion), and even if there are a number of recursive calls, each of which will return to its predecessor the value returned by its successor. In the implementation, each of the intermediate calls vanishes as soon as its successor is launched.

However, this clever technique, which speeds up procedure calling and sometimes enables Scheme to use memory very efficiently, is guaranteed to work only if the procedure call is the last step. For instance, tail-call elimination cannot be used in the sum procedure as we defined it in an earlier lab:

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

The recursive call in this case is not a tail call, since, after it returns its value, the first number on the list still has to be added to that value.

As you might expect, it is possible to write a tail-recursive version of sum, just as we wrote a tail-recursive factorial:

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

The idea is to provide, in each recursive call, a second argument, giving the sum of all the list elements that have been encountered so far: the running total of the previously encountered elements. We call these second argument the accumulator.

When the end of the list is reached, the value of the accumulator (the running total) is returned; until then, each recursive call strips one element from the beginning of the list, adds it to the running total, and finally calls itself recursively with the shortened list and the augmented running total. The ``finally'' part is important: sum-kernel is tail-recursive.

Here is a summary of the execution of a call to this version of sum:

    (sum (list 97 85 34 73 10))
--> (sum-kernel (list 97 85 34 73 10) 0)
--> (sum-kernel (list 85 34 73 10) 97)
--> (sum-kernel (list 34 73 10) 182)
--> (sum-kernel (list 73 10) 216)
--> (sum-kernel (list 10) 289)
--> (sum-kernel null 299)
--> 299

Note that the additions are performed on the way into the successive calls to sum-kernel, so that when the base case is reached no further calculation is needed -- the value of the second argument in that last call to sum-kernel is returned without further modification as the value of the original call to sum.