Computer Science Fundamentals (CS153 2004S)
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
Misc:
[Experiments in Java]
[Java API]
[Scheme Reference]
[Scheme Report]
[CS153 2003S]
[CS151 2003F]
[CS152 2000F]
[SamR]
Summary: In this reading, we consider how to make your recursive procedures run more quickly by taking advantage of a program design strategy called tail recursion.
Contents:
Consider the following recursive functions.
;;; 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: ;;; val, a value ;;; values, a list of values ;;; Purpose: ;;; Determines if val is in values. ;;; Produces: ;;; mem?, a boolean value ;;; Preconditions: ;;; The parameters have the appropriate types. ;;; Postconditions: ;;; mem? is #t if there exists an element of values that ;;; is equal to val. ;;; mem? is #f otherwise. (define member? (lambda (val values) (and (not (null? values)) (or (equal? val (car values)) (member? val (cdr values)))))) ;;; Procedure: ;;; factorial ;;; Parameters: ;;; n, a nonnegative integer ;;; Purpose: ;;; Computes n! = 1*2*3*...*n ;;; Produces: ;;; result, a positive integer ;;; Preconditions: ;;; n is a nonnegative integer [unchecked] ;;; Postconditions: ;;; result = 1*2*3*...*n (define factorial (lambda (n) (if (<= n 0) 1 (* n (factorial ( n 1)))))) ;;; Procedure: ;;; addtoall ;;; Parameters: ;;; value, a number ;;; values, a list of numbers ;;; Purpose: ;;; Creates a new list by adding value to each member of values. ;;; Produces: ;;; newlist, a list of numbers ;;; Preconditiosn: ;;; value is a number [Unverified] ;;; values is a list of numbers [Unverified] ;;; Postconditions: ;;; (listref newvalues i) equals (+ value (listref values i)) ;;; for all reasonable values of i. (define addtoall (lambda (value values) (if (null? values) null (cons (+ value (car values)) (addtoall value (cdr values))))))
In writing recursive procedures and looking and these 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 addtoall
procedures
do something with the result (multiply the result by something and cons
something to the result, respectively).
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
.
For example, here are the steps in some calls to member?
and a call to factorial
.
(member? 4 (list 1 2 3 4 5)) => (member? 4 (list 2 3 4 5)) => (member? 4 (list 3 4 5)) => (member? 4 (list 4 5)) => #t (member 6 (list 1 2 3 4 5)) => (member? 6 (list 2 3 4 5)) => (member? 6 (list 3 4 5)) => (member? 6 (list 4 5)) => (member? 6 (list 5)) => (member? 6 ()) => #f (factorial 5) => (* 5 (factorial 4)) => (* 5 (* 4 (factorial 3))) => (* 5 (* 4 (* 3 (factorial 2)))) => (* 5 (* 4 (* 3 (* 2 (factorial 1))))) => (* 5 (* 4 (* 3 (* 2 (* 1 (factorial 0)))))) => (* 5 (* 4 (* 3 (* 2 (* 1 1))))) => (* 5 (* 4 (* 3 (* 2 1)))) => (* 5 (* 4 (* 3 2))) => (* 5 (* 4 6)) => (* 5 24) => 120
Note that the recursive calls to member
shrink towards a result
while the recursive calls to factorial
build up a lot of
unresolved multiplication that must be done when we reach the base case.
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 used a husk and kernel 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 huskandkernel techniques to make some nontailrecursive procedures tail recursive.
(define factorial (lambda (n) ; Define a kernel that "accumulates" the previous multiplications ; as a second parameter. Now we're computing n*(n1)*...*(m+1)*m! (letrec ((kernel (lambda (m acc) ; If we've run out of values, return what we've ; accumulated. (if (<= m 0) acc ; Otherwise, multiply the current accumulated ; product by m and continue with the ; remaining values. (kernel ( m 1) (* acc m)))))) (kernel n 1))))
If we want to use named let, we can be even more concise.
(define factorial (lambda (n) (let kernel ((m n) (acc 1)) (if (<= m 0) acc (kernel ( m 1) (* acc m))))))
There is an important reason for adopting tail recursion, and it has to do with efficiency. An implementation of Scheme is required to perform tailcall 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,
tailcall 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. You can see the problem as we look at the steps involved in summing a short list.
(sum (list 97 85 34 73 10)) => (+ 97 (sum (list 85 34 73 10))) => (+ 97 (+ 85 (sum (list 34 73 10)))) => (+ 97 (+ 85 (+ 34 (sum (list 73 10))))) => (+ 97 (+ 85 (+ 34 (+ 73 (sum (list 10)))))) => (+ 97 (+ 85 (+ 34 (+ 73 (+ 10 (sum null)))))) => (+ 97 (+ 85 (+ 34 (+ 73 (+ 10 0))))) => (+ 97 (+ 85 (+ 34 (+ 73 10)))) => (+ 97 (+ 85 (+ 34 83))) => (+ 97 (+ 85 117)) => (+ 97 202) => 299
As you might expect, it is possible to write a tailrecursive version of
sum
, just as we wrote a tailrecursive factorial:
(define sum (letrec ((sumkernel (lambda (ls runningtotal) (if (null? ls) runningtotal (sumkernel (cdr ls) (+ (car ls) runningtotal)))))) (lambda (ls) (sumkernel 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 the 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:
sumkernel
is tailrecursive.
Here is a summary of the execution of a call to this version of
sum
:
(sum (list 97 85 34 73 10)) => (sumkernel (list 97 85 34 73 10) 0) => (sumkernel (list 85 34 73 10) 97) => (sumkernel (list 34 73 10) 182) => (sumkernel (list 73 10) 216) => (sumkernel (list 10) 289) => (sumkernel null 299) => 299
Note that the additions are performed on the way into the successive calls
to sumkernel
, so that when the base case is reached no
further calculation is needed  the value of the second argument in that
last call to sumkernel
is returned without further
modification as the value of the original call to sum
.
You might also note that we did the additions in a different order. While the order is not important for addition, it may be for other operations.
Finally, let's look at how we might rewrite this new sum
using a named let.
(define sum (lambda (lst) (let kernel ((ls lst) (runningtotal 0)) (if (null? ls) runningtotal (kernel (cdr ls) (+ (car ls) runningtotal))))))
Tail recursion becomes a little bit more subtle when you think about
how you would use tail recursion to build lists. Consider the
addtoall
procedure from the start of this reading.
The straightforward way to make this procedure tailrecursive is to
add a list of things that have been added to
as a
parameter to the kernel. When we're done, we just return that list.
(define addtoall (lambda (value values) ; kernel is a procedure of two parameters: ; valuesremaining, the values left to process ; valuesprocessed, a list of all values that have ; already been added to. ; Initially, all values remain to be processed and ; no values have been added to. (let kernel ((valuesremaining values) (valuesprocessed null)) ; If there are no values remaining to process, we can ; use the values already processed. (if (null? valuesremaining) valuesprocessed ; Otherwise, process the first remaining value ; and then process any other remaining values. (kernel (cdr valuesremaining) (append valuesprocessed (list (+ value (car valuesremaining)))))))))
As you may have noted from the code, it's a little bit complicated to extend that list. In particular, we have to add the next value to the end of the list of processed values. Right now, we only know two ways to add to the end of a list: (1) append another list (in this case a list containing just one value) or (2) reverse, cons, and reverse again. Both strategies are somewhat inefficient because we have to step all the way through the list to add to the end. Since we keep adding to the end, we step through the result list again and again and again and again.
Is there a better way to write addtoall
? Yes. We can
consider other ways we know to add values to a list. Rather than
appending, we can just cons each value on to the processed list.
(kernel (cdr valuesremaining) (cons (+ value (car valuesremaining)) valuesprocessed))))))
Now we have to figure out what to return in the base case. Since we're stepping through one list from lefttoright and adding them to the result list from righttoleft (that is, extending the list at the left each time), the result is the reverse of the result we want. Hence, in the base case, we need to reverse it again.
(define addtoall (lambda (value values) ; kernel is a procedure of two parameters: ; valuesremaining, the values left to process ; valuesprocessed, a list of all values that have ; already been added to; given in reverse order. ; Initially, all values remain to be processed and ; no values have been added to. (let kernel ((valuesremaining values) (valuesprocessed null)) ; If we've run out of values to process, (if (null? valuesremaining) ; Return the values already processed after putting them ; back in the correct order. (reverse valuesprocessed) ; Otherwise, process the first remaining value ; and then process any other remaining values. (kernel (cdr valuesremaining) (cons (+ value (car valuesremaining)) valuesprocessed))))))
Fall 2000 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~stone/courses/scheme/indefiniterecursion.xhtml
and which can now be found at
http://www.cs.grinnell.edu/~stone/courses/scheme/spring2000/indefiniterecursion.xhtml
(dated March 17, 2000).
sum
as an example (as well as
an index
procedure that I chose not to copy).
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Readings/tailrecursion.html
.
Sunday, 8 April 2001 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2001S/Readings/tailrecursion.html
.
Thursday, 7 November 2002 [Samuel A. Rebelsky]
sum
.
Monday, 11 November 2002 [Samuel A. Rebelsky]
addtoall
.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2002F/Readings/tailrecursion.html
.
Thursday, 20 February 2003 [Samuel A. Rebelsky]
member
.
Thursday, 6 March 2003 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2003S/Readings/tailrecursion.html
.
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
Misc:
[Experiments in Java]
[Java API]
[Scheme Reference]
[Scheme Report]
[CS153 2003S]
[CS151 2003F]
[CS152 2000F]
[SamR]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Fri May 7 09:44:43 2004.
The source to the document was last modified on Wed Jan 21 09:41:33 2004.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2004S/Readings/tailrecursion.html
.
; ; Check with Bobby
Samuel A. Rebelsky, rebelsky@grinnell.edu