last revised January 26, 2005 by Henry M. Walker
| CSC 153: Computer Science Fundamentals | Grinnell College | Spring, 2005 |
| Laboratory Exercise Reading | ||
This introduces the concept of recursive procedures −− procedures that include one or more calls to themselves. Recursion provides an extremely powerful tool in problem solving.
As we've already seen, it is commonplace for the body of a procedure to include calls to another procedure, or even to several others. Direct recursion is the special case of this phenomenon in which the body of a procedure includes one or more calls to the very same procedure -- calls that deal with simpler and more readily computable values of the parameters.
For instance, imagine that you want to define a procedure
longest-on-list that takes as its argument any non-empty list
of character strings and returns whichever element of that list is the
longest:
(longest-on-list '("This" "is" "the" "forest" "primeval")) ===> "primeval"
(longest-on-list '("Wherefore" "art" "thou" "Romeo")) ===> "Wherefore"
(longest-on-list '("To" "be" "or" "not" "to" "be")) ===> "not"
(longest-on-list '("foo")) ===> "foo"
If there is a tie for the longest string, let's say that whichever one appears first on the list wins:
(longest-on-list '("keep" "it" "short" "and" "sweet")) ===> "short"
(longest-on-list '("you" "can" "see" "the" "top")) ===> "you"
In trying to write this procedure, the main difficulty is that we have to
deal with lists of unknown length. It's easy to determine which of two
given strings is longer; Scheme provides a built-in procedure
string-length that computes the number of characters in a
string, and we can apply this procedure to each string and compare the
results:
(define longer-string
(lambda (str1 str2)
(if (< (string-length str1) (string-length str2))
str2
str1)))
But even with the help of this function it's not clear how to search a list that might, in principle, contain hundreds or even millions of strings.
However, there's one case in which the parameter is so simple in structure
that it's trivial to come up with the answer: When ls is a
list that contains only one string, by default it is the longest string on
the list, and we can simply extract it with car and return it.
And in any other case -- whenever the list is known to
have two or more elements -- we can at least be confident that the longest
string is either the first one on the list, or the
longest string from the rest of the list. So if we could solve the
slightly simpler problem of identifying the longest string from the rest of
the list, and compare that one with the first element of the list (using
longer-string), we'd be done.
In this situation, recursion is the solution to our problem:
(define longest-on-list
(lambda (ls)
(if (null? (cdr ls))
(car ls)
(longer-string (car ls)
(longest-on-list (cdr ls))))))
In English: To find the longest string on the list ls, test
whether its cdr is the empty list. If so, then ls has only
one element, so recover that element by applying car.
Otherwise, find the longest string in the rest of the list -- by invoking
the longest-on-list procedure itself! -- and compare that to
the first string of ls; return whichever one is longer.
Consider how this works for a particular list, say ("red" "white" "and"
"blue"): The call
(longest-on-list '("red" "white" "and" "blue"))
tests whether the cdr of the list it is given is empty. It isn't, so the
alternative of the if-expression is selected and evaluated.
It's a call to the longer-string procedure, and the first step
in invoking that procedure is to compute the value of each of the
arguments. (car ls) is easily found to be "red",
but to work out the value of the second argument we have to call
the longest-on-list procedure again, but with the cdr of the
original list, just as if the call were
(longest-on-list '("white" "and" "blue"))
Whatever value is returned by this call will become the second argument of
longer-string and will be compared with "red".
So what does it return? On this second invocation, the
longest-on-list procedure tests whether the cdr of
("white" "and" "blue") is empty. It isn't, so once again the
alternative of the if-expression is selected and evaluated,
beginning with the arguments of the call to longer-string. At
this level, (car ls) is "white", but finding the
value of the second argument requires us to evaluate another call to
longest-on-list -- basically,
(longest-on-list '("and" "blue"))
On this third invocation, longest-on-list tests whether the
cdr of ("and" "blue") is empty. It isn't, so the alternative
is selected yet again, and we start once more to evaluate the arguments to
longer-string. The first argument, (car ls), is
"and"; for the second argument we need the value of a fourth
invocation,
(longest-on-list '("blue"))
But this time, when longest-on-list tests whether the cdr of
("blue") is empty, the result of the test is #t,
so that the consequent of the if-expression is selected:
(car '("blue"))
This returns the string "blue", which is handed back to the
preceding level. At that point, both arguments to
longer-string are in place: The first is "and",
the second is "blue".
(longer-string "and" "blue") ===> "blue"
The longer-string procedure determines that
"blue" is longer and returns it as the value of the third
invocation of longest-on-list. This enables the earlier call
to longer-string to go forward, since now both of its
arguments have been available:
(longer-string "white" "blue") ===> "white"
This completes the second invocation of longest-on-list,
giving it the value "white". So now the very first call to
longer-string can be completed, since both of its arguments
have been evaluated:
(longer-string "red" "white") ===> "white"
So the value of the original call (longest-on-list '("red" "white"
"and" "blue")) is "white", as required.
The computer still has to do the work of taking the list apart, step by
step and element by element, to examine all of the elements. This will
require as many calls to the longest-on-list procedure as
there are elements in the list it is given. But the programmer does not
have to write out all those calls or to predict how many of them there will
be. By providing a test that tells the procedure when to stop cdr-ing and
recursing -- the test (null? (cdr ls)) -- the programmer can
write a short, simple procedure to do however much work is necessary.
The procedure longest-on-list proceeded by making a series of procedure calls. In this case, each successive call in the recursion required a simpler computation because the list was shorter each time.
In cases involving numbers, recursion instead may make successive changes in some numeric parameter until a limiting case is reached.
For example, it is straightforward even without recursion to define the
procedures square and cube to figure the second
and third powers of a number by successive multiplications:
(define square
(lambda (n)
(* n n)))
(define cube
(lambda (n)
(* n n n)))
But suppose we want to compute the kth power of n more generally, with a two-argument procedure in which both n and k are parameters? It doesn't quite make sense to do this by repeated multiplication unless k is a positive integer, but if we promise never to call our procedure unless this precondition is met we can use recursion to determine how many multiplications to perform:
(define power
(lambda (n k)
(if (= k 1)
n
(* n (power n (- k 1))))))
In English: To compute the kth power of n, check whether k is 1; if so, the answer is simply n. Otherwise, multiply n by the (k - 1)st power of n.
Since we promise to start with a positive integer value for k, and
each successive recursive call to power reduces the exponent
by 1, eventually a call will be reached in which the second parameter has
been reduced to 1. This call will return the value of the first parameter
without attempting any further recursion.
As another example involving integers, consider the following procedure
list-of-zeroes procedure that takes one argument, which is
assumed to be a non-negative integer indicating the length of the desired
list, and returns a list of that length in which every element is 0:
(define list-of-zeroes
(lambda (n)
(if (zero? n)
'()
(cons 0 (list-of-zeroes (- n 1))))))
In English: To construct a list of n zeroes, first check whether
n is itself zero; if so, return the empty list. Otherwise,
construct a list of n - 1 zeroes and then use cons to
attach another zero to the front. The limit here is the zero value of
n; when this limit has been reached, no more recursive calls are
needed.
When solving problems, one very common pattern involves constructing a list by applying some given procedure to every element of a given list and collecting the results. For example, the following procedure constructs a list of the squares of the numbers on a given list:
(define square-each-element
(lambda (ls)
(if (null? ls)
'()
(cons (square (car ls))
(square-each-element (cdr ls))))))
In English: To square every element of a list, test whether that list is
empty. If so, return the empty list (there's nothing to square!);
otherwise square the first element, and use cons to attach it
to the front of a list of the squares of the rest of the elements.
In some cases, it may be helpful to define two procedures to solve a problem -- one to set up the initial call to the other, supplying additional arguments to assist the recursion. This is illustrated in the following problem and solution:
Problem : Write a procedure called tally-by-parity that
takes any list ls of integers and returns a two-element list
in which the first element is the number of odd integers in ls
and the second is the number of even integers in ls.
(tally-by-parity '(2 3 5 7 11 13)) ===> (5 1) (tally-by-parity '(0 1 2 3 4 5 6)) ===> (3 4) (tally-by-parity '(-8 124 0 124)) ===> (0 4) (tally-by-parity '()) ===> (0 0)Proposed Solution:
(define tally-by-parity
(lambda (ls)
(tally-helper ls '(0 0))))
(define tally-helper
(lambda (ls ct-pair)
(cond ((null? ls) ct-pair)
((odd? (car ls))
(tally-helper (cdr ls)
(list (+ 1 (car ct-pair)) (cadr ct-pair))))
(else (tally-helper (cdr ls)
(list (car ct-pair) (+ 1 (cadr ct-pair))))))))
This document is available on the World Wide Web as
http://www.walker.cs.grinnell.edu/courses/153.sp05/readings/reading-recursion.shtml
|
created February 4, 1997 by John David Stone last revised January 26, 2005 by Henry M. Walker |
|
| For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. |