Fundamentals of Computer Science I (CS151.02 2007S)
[Skip to Body]
Primary:
[Front Door]
[Syllabus]
[Glance]
[Search]

[Academic Honesty]
[Instructions]
Current:
[Outline]
[EBoard]
[Reading]
[Lab]
[Assignment]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Projects]
[Readings]
Reference:
[Scheme Report (R5RS)]
[Scheme Reference]
[DrScheme Manual]
Related Courses:
[CSC151 2006F (Rebelsky)]
[CSC151.01 2007S (Davis)]
[CSCS151 2005S (Stone)]
This reading is also available in PDF.
Summary:
As you've started exploring the technique of recursion, some of you have
asked (explicitly or implicitly), So, how do I write a recursive
procedure from scratch?
In this reading, we consider some common
techniques for thinking about the design and implementation of recursive
algorithms.
Contents:
As we've seen in the reading on recursion, recursion is a powerful technique for writing procedures that can repeat work and can deal with parameters whose size we do not know in advance (such as lists of unknown length).
We have also seen a few basic techniques for structuring recursive procedures. In the most general formulation, we write a recursive procedure as follows.
(define recursiveprocedure (lambda (parameters) (if testforbasecase basecase recursivecase)))
When we consider the parts in a bit more detail, we see that the basecase may involve the parameters (e.g, we may take the car of a oneelement list) or it may not (e.g., we may return 0). We also note that the recursive case involves recursing (obviously), simplifying the parameters before recursing, and, often, doing something after recursing.
(define recursiveproc (lambda (params) (if (basecasetest) (basecase params) (combine (partof params) (recursiveproc (simplify params))))))
In many cases, the recursive part really had two alternatives  one in which some test held and one in which it failed to hold. For example, we often check whether a list starts with a particular value. In that case, we might generalize to something a bit more like the following.
(define recursiveproc (lambda (params) (cond ((basecasetest) (basecase params)) ((specialcasetest) (combine (partof params) (recursiveproc (simplify params)))) (else (recursiveproc (simplify params))))))
We also saw a different pattern of recursion, one in which we use a
helper procedure that takes additional parameters, often parameters
to help us accumulate
an answer.
(define recursiveproc (lambda (params) (recursiveprochelper initialvalueofaccumulator params))) (define recursiveprochelper (lambda (computedsofar remainingparams) (if (basecasetest) (modify computedsofar) (recursiveprochelper (update computedsofar) (simplify remainingparams)))))
But how do you choose how to simplify, to update, to modify, and how else to deal with the specifics of a particular procedure? Let us consider some common strategies.
For both kinds of recursive procedures (those with recursive helpers and
those without), the first strategy you should often employ is to see if
you've solved (or seen a solution of) a similar procedure. If you have,
then see if you can modify that similar procedure for this case. For
example, if we are asked to compute the product of the values in a list,
we might begin with sum
.
(define sum (lambda (vals) (if (null? vals) 0 (+ (car vals) (sum (cdr vals))))))
What do we need to change in moving from sum to product?
sum
by product
.)
1, the multiplicative identity. Hence, we will need to change the base case from 0 to 1.
Putting that all together, we get the following:
(define product (lambda (vals) (if (null? vals) 1 (* (car vals) (product (cdr vals))))))
We can do something in writing closesttozero
. Since
closesttozero
involves finding the best
value
in a list, we rely on a procedure we've seen before that finds a
different kind of best value, largestinlist
.
(define largestoflist (lambda (numbers) (if (null? (cdr numbers)) (car numbers) (max (car numbers) (largestoflist (cdr numbers))))))
In this case, we observe that max
is used to select between
two values, and choose the better (larger) one. We'll need to replace
this with something that finds the value closer to zero.
(define closesttozero (lambda (numbers) (if (null? (cdr numbers)) (car numbers) (closertozero (car numbers) (closesttozero (cdr numbers))))))
Of course, closertozero
does not exist. So, we'll have
to write it. Fortunately, it is fairly straightforward.
(define closertozero (lambda (a b) (if (< (abs a) (abs b)) a b)))
That's it. We're done.
But what happens when you don't have a model on which you can base your
solution? Then, you need to start from scratch
, as it were.
I find it most useful to begin with the base case. Ask yourself What is the simplest case for which I can directly compute an answer? The answer to this question should give you a test for the base case. For lists, the simplest case is often an empty list or a singleelement list.
Next, ask yourself What is the answer in this simple case? If you do not find that the answer is relatively obvious, then your test for the base case may be wrong. Note that it is important to ensure that the type of the value of the base case matches the expected type. That is, if you are returning a list, the base case should be a list, if you are returning a number, the base case should be a number, and so on and so forth.
Next, ask yourself How do I simplify my parameters? For lists,
the typical case is to take the cdr
of the list. For natural
numbers, the typical case is to subtract some number. (A common, though
less typical, case is to divide by some number, often two.)
Finally, ask yourself Suppose I had a solution to this simplified version. What can I do with the result to compute my desired value?
The strategy we use for recursive helper procedures is similar, but differs in a few key ways. Recall that such procedures look something like the following:
(define recursiveprochelper (lambda (computedsofar remainingparams) (if (basecasetest) (modify computedsofar) (recursiveprochelper (update computedsofar) (simplify remainingparams)))))
You begin, again, by asking yourself How do I know that I have no values left to process? For lists, you often know that you're done when the list parameter (which we're fond of calling remaining) is empty. For numbers, you often know that you're done when one of the numeric parameters reaches 0.
You continue by asking yourself What is the relationship of the value I computed along the way to my desired result? The value computed along the way is often the desired result. At times, though, it may be slightly different (a reversed list, for example). Sometimes, the most straightforward thing to do is to return computedsofar as a test, and then see the relationship.
You continue by asking yourself How do I simplify the parameters? Again, for lists the answer is often to take the cdr, and for numbers, the answer is often to subtract or divide.
You conclude by asking yourself How should I update my intermediate result, given the particular information I've discarded by simplifying? The answer should give you the update procedure.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/History/Readings/writingrecursion.html
.
[Skip to Body]
Primary:
[Front Door]
[Syllabus]
[Glance]
[Search]

[Academic Honesty]
[Instructions]
Current:
[Outline]
[EBoard]
[Reading]
[Lab]
[Assignment]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Projects]
[Readings]
Reference:
[Scheme Report (R5RS)]
[Scheme Reference]
[DrScheme Manual]
Related Courses:
[CSC151 2006F (Rebelsky)]
[CSC151.01 2007S (Davis)]
[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 Thu Sep 13 20:55:21 2007.
The source to the document was last modified on Tue Feb 13 07:59:22 2007.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2007S/Readings/writingrecursion.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.