[Current] [News] [Glance] [Discussions] [Instructions] [Search] [Links] [Handouts] [Outlines] [Readings] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [Fall2000.01] [Spring2000]

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

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".

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

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`

.

[Current] [News] [Glance] [Discussions] [Instructions] [Search] [Links] [Handouts] [Outlines] [Readings] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [Fall2000.01] [Spring2000]

**Disclaimer** Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.

This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Readings/tail-recursion.html

Source text last modified Mon Oct 30 11:48:16 2000.

This page generated on Mon Oct 30 11:52:02 2000 by Siteweaver. Validate this page's HTML.

Contact our webmaster at rebelsky@grinnell.edu