Fundamentals of Computer Science I: Media Computing (CS151.02 2007F)
[Skip to Body]
Primary:
[Front Door]
[Glance]

[Academic Honesty]
[Instructions]
Current:
[Outline]
[EBoard]
[Reading]
[Lab]
[Assignment]
Groupings:
[Assignments]
[EBoards]
[Examples]
[Exams]
[Handouts]
[Labs]
[Outlines]
[Projects]
[Readings]
[Reference]
Reference:
[Scheme Report (R5RS)]
[Scheme Reference]
[DrScheme Manual]
Related Courses:
[CSC151.01 2007F (Davis)]
[CSC151 2007S (Rebelsky)]
[CSCS151 2005S (Stone)]
This reading is also available in PDF.
Summary: You've now seen a bit of the basics of recursion as a program design strategy. We now consider an alternate technique for writing recursive procedures, one in which we carry along a partial result at each step. This technique is called tail recursion.
Contents:
There are a few basic principles to writing recursive functions. As you may recall from the first reading on recursion, a recursive procedure is one that calls itself. To successfully write a recursive procedure, you need
A disadvantage of traditional recursion is that it is difficult to tell what is happening along the way. In the particular case of list recursion, we work all the way down to the end of the list, and then work our way back to the front of the list to compute a final result. Why not just compute the result as we go?
Before we go much further, let's take a quick detour into an
important concept: When Scheme has a nested expression to evaluate,
how does it evaluate that expression? The technique it uses is
pretty straightforward: In order to apply a procedure to parameters,
those parameters must be in simple form (that is, values, rather than
expressions to compute values). Hence, given (proc exp1 exp2
exp3)
, Scheme first evaluates exp1
, exp2
,
and exp3
and then applies proc
to the three
resulting values.
In what order does it evaluate exp1
, exp2
, and
exp3
? It turns out that it depends on the implementation
of Scheme. In our sample code, we'll always assume that Scheme evaluates
a procedure from left to right.
Of course, for some operations (which we call syntax
), Scheme
uses a different evaluation strategy. For example, when evaluating
an if
, Scheme does not evaluate all three parameters.
Instead, it evaluates them in a specified order (first the test, then
only one of the consequent and alternate). Similarly, when evaluating
an and
or an or
, Scheme evaluates the parameters
one at a time, stopping as soon as it knows an answer (in the case of
and
, when it hits a #f
; in the case of
or
, when it hits a #t
).
But there's more. To understand how Scheme evaluates expressions, we must also understand how it applies the procedures you define and how it processes definitions in general.
The naming scheme that Scheme uses is relatively straightforward. Scheme keeps a table of correspondences between names and values. For each name, it stores a reference to the value, which means that two names can refer to the same value. (This is imporant to know, because if you change a value with a sideeffecting function, then all references to that value seem to change.) If you write another definition using the same name, it changes the reference, but not the underlying value. When Scheme sees a name while evaluting an expression, it looks up the name in the table, and uses the value the name refers to.
The way procedures work takes advantage of this naming Scheme. When you
call a procedure on some arguments, Scheme first updates the name
table, mapping each name in the lambda to the corresponding argument.
For example, if you apply (lambda (a b c) ...)
to 3, 1, and
6, the table will now have a
refer to 3, b
refer to 1, and c
refer to 6. After updating the table,
Scheme evaluates the body of the procedure. When it finishes evaluating
the body, it cleans up the name table, undoing any changes it made.
Why is the way Scheme evaluates and understands expressions important
for recursion? First, it may help you understand how recursion works.
Because if
(or cond
), delays the evaluation of
the consequent and alternate, we can safely have a procedure call itself
without worrying about it calling itself again and again and again,
ad infinitum. Second, it clarifies how we can have the same names (the
parameters) mean different things at different times.
We'll consider the question of computing results as we go with the
summation example from the previous reading.
As you may have noted, an odd thing about the sum
procedure
is that it works from right to left. Traditionally, we sum from left
to right. Can we rewrite sum
to work from left to right?
Certainly, but we may need a helper procedure (another procedure
whose primary purpose is to assist our current procedure) to do so.
If you think about it, when you're summing a list of numbers from left to right, you need to keep track of two different things:
Hence, we'll build our helper procedure with two parameters,
sumsofar
and remaining
. We'll start
the body with a template for recursive procedures (a test to
determine whether to use the base case or recursive case, the base
case, and the recursive case). We'll then fill in each part.
(define newsumhelper (lambda (sumsofar remaining) (if (test) basecase recursivecase)))
The recursive case is fairly easy. Recall that since remaining
is a list, we can split it into two parts, the first element (that is, the
car
), and the remaining elements (that is, the cdr
).
Each part contributes to one of the parameters of the recursive
call. We update sumsofar
by adding the first element of
remaining
to sumsofar
. We update
remaining
by removing the first element.
To continue
, we simply call newsumhelper
again with those updated parameters.
(define newsumhelper (lambda (sumsofar remaining) (if (test) basecase (newsumhelper (+ sumsofar (car remaining)) (cdr remaining)))))
The recursive case then gives us a clue as to what to use for the test. We need to stop when there are no elements left in the list.
(define newsumhelper (lambda (sumsofar remaining) (if (null? remaining) basecase (newsumhelper (+ sumsofar (car remaining)) (cdr remaining)))))
We're almost done. What should the base case be? In the previous version, it was 0. However, in this case, we've been keeping a running sum. When we run out of things to add, the value of the complete sum is the value of the running sum.
(define newsumhelper (lambda (sumsofar remaining) (if (null? remaining) sumsofar (newsumhelper (+ sumsofar (car remaining)) (cdr remaining)))))
Now we're ready to write the primary procedure whose responsibility it is
to call newsumhelper
. Like sum
,
newsum
will take a list as a parameter. That list will
become remaining
. What value should sumsofar
begin with? Since we have not yet added anything when we start, it
begins at 0.
(define newsum (lambda (numbers) (newsumhelper 0 numbers)))
Putting it all together, we get the following.
;;; Procedure: ;;; newsum ;;; Parameters: ;;; numbers, a list of numbers. ;;; Purpose: ;;; Find the sum of the elements of a given list of numbers ;;; Produces: ;;; total, a number. ;;; Preconditions: ;;; All the elements of numbers must be numbers. ;;; Postcondition: ;;; total is the result of adding together all of the elements of numbers. ;;; If all the values in numbers are exact, total is exact. ;;; If any values in numbers are inexact, total is inexact. (define newsum (lambda (numbers) (newsumhelper 0 numbers))) ;;; Procedure: ;;; newsumhelper ;;; Parameters: ;;; sumsofar, a number. ;;; remaining, a list of numbers. ;;; Purpose: ;;; Add sumsofar to the sum of the elements of a given list of numbers ;;; Produces: ;;; total, a number. ;;; Preconditions: ;;; All the elements of remaining must be numbers. ;;; sumsofar must be a number. ;;; Postcondition: ;;; total is the result of adding together sumsofar and all of the ;;; elements of remaining. ;;; If both sumsofar and all the values in remaining are exact, ;;; total is exact. ;;; If either sumsofar or any values in remaining are inexact, ;;; total is inexact. (define newsumhelper (lambda (sumsofar remaining) (if (null? remaining) sumsofar (newsumhelper (+ sumsofar (car remaining)) (cdr remaining)))))
Does this change make a difference in the way in which the sum is evaluated? Let's watch.
(newsum (cons 38 (cons 12 (cons 83 null)))) => (newsumhelper 0 (cons 38 (cons 12 (cons 83 null)))) => (newsumhelper (+ 0 38) (cons 12 (cons 83 null))) => (newsumhelper 38 (cons 12 (cons 83 null))) => (newsumhelper (+ 38 12) (cons 83 null)) => (newsumhelper 50 (cons 83 null)) => (newsumhelper (+ 50 83) null) => (newsumhelper 133 null) => 133
Note that the intermediate results for newsum
were different,
primarily because newsum
operates from left to right.
Okay, how does one write one of these procedures? First, you build a
helper procedure that takes as parameters the list you're recursing over,
which we've called remaining
, a new parameter,
____sofar
, and any other useful parameters. The helper
recurses over the list, updating that list to its cdr at each step
and updates ____sofar
to be the next partial result.
Then you build the main procedure, which calls the helper with an
appropriate initial ____sofar
and remaining
.
For example,
(define proc (lambda (lst) (prochelper initialvalue lst))) (define prochelper (lambda (sofar remaining) (if (null? lst) sofar (prochelper (combine sofar (car remaining)) (cdr remaining)))))
However, as we'll see in the next section, you sometimes need to use
different initial values for sofar
and lst
.
We've now seen two strategies for doing recursion: We can combine the result of a recursive call into a final result, or we can pass along intermediate results as we recurse, and stop with the final result. Which should you use? For many applications, it doesn't matter. However, there are times that one technique is much more appropriate than the other. Consider the problem taking a list of numbers, n_{1}, n_{2}, n_{3}, ... n_{k1}, n_{k}, and computes n_{1}  n_{2}  n_{3}  ...  n_{k1}  n_{k}.
Suppose we use the first technique. We might write:
(define difference (lambda (lst) (if (null? lst) 0 ( (car lst) (difference (cdr lst))))))
Unfortunately, this doesn't quite work as you might expect. Consider
the computation of (difference (list 1 2 3))
. As you may
recall, subtraction is left associative, so this should be (12)3, or 4.
Let's see what happens.
(difference (cons 1 (cons 2 (cons 3 null)))) => ( 1 (difference (cons 2 (cons 3 null)))) => ( 1 ( 2 (difference (cons 3 null)))) => ( 1 ( 2 ( 3 (difference null)))) => ( 1 ( 2 ( 3 0))) => ( 1 ( 2 3)) => ( 1 1) => 2
Hmmm ... that's not quite right. So, let's try the other technique.
(define newdifference (lambda (lst) (newdifferencehelper 0 lst))) (define newdifferencehelper (lambda (differencesofar remaining) (if (null? remaining) differencesofar (newdifferencehelper ( differencesofar (car remaining)) (cdr remaining)))))
Okay, what happens here?
(newdifference (list 1 2 3)) => (newdifferencehelper 0 (cons 1 (cons 2 (cons 3 null)))) => (newdifferencehelper ( 0 1) (cons 2 (cons 3 null))) => (newdifferencehelper 1 (cons 2 (cons 3 null))) => (newdifferencehelper ( 1 2) (cons 3 null)) => (newdifferencehelper 3 (cons 3 null)) => (newdifferencehelper ( 3 3) null) => (newdifferencehelper 6 null) => 6
Nope. Still incorrect. So, what happened? We started with 0, then we
subtracted 1, then we subtracted 2, then we subtracted 3. It looks like
we did those last two subtractions in order. But wait! Why are we
subtracting 1? That's the value we're supposed to subtract everything
else from. That means we need to choose a better initial differencesofar
and remaining
. Why not make the car the
differencesofar
and the cdr remaining
?
(define newerdifference (lambda (lst) (newdifferencehelper (car lst) (cdr lst))))
Does this work?
(newerdifference (list 1 2 3)) => (newdifferencehelper 1 (cons 2 (cons 3 null))) => (newdifferencehelper ( 1 2) (cons 3 null)) => (newdifferencehelper 1 (cons 3 null)) => (newdifferencehelper ( 1 3) null) => (newdifferencehelper 4 null) => 4
It works! Well, it works for this example. We'll see if it works for other examples.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/History/Readings/recursion.html
.
[Skip to Body]
Primary:
[Front Door]
[Glance]

[Academic Honesty]
[Instructions]
Current:
[Outline]
[EBoard]
[Reading]
[Lab]
[Assignment]
Groupings:
[Assignments]
[EBoards]
[Examples]
[Exams]
[Handouts]
[Labs]
[Outlines]
[Projects]
[Readings]
[Reference]
Reference:
[Scheme Report (R5RS)]
[Scheme Reference]
[DrScheme Manual]
Related Courses:
[CSC151.01 2007F (Davis)]
[CSC151 2007S (Rebelsky)]
[CSCS151 2005S (Stone)]
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 Mon Dec 3 09:54:29 2007.
The source to the document was last modified on Mon Oct 1 10:33:05 2007.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2007F/Readings/tailrecursionreading.html
.
You may wish to validate this document's HTML ; ;
Samuel A. Rebelsky, rebelsky@grinnell.eduhttp://creativecommons.org/licenses/bync/2.5/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.