CMIS 240
Week 10
We need to have a crash course in recursion this week. Chapter 7 is
devoted to recursion. A function that calls itself is recursive.
There's nothing magical about recursion, although it sometimes seems
that there is. It's another way of repetition (the repetition that
you're familiar with is looping, i.e. iteration). Some problems lend
themselves to recursive solutions that are easier to do than a
corresponding iterative solution. Every iterative algorithm can be
recast as a recursive one, and vice versa. Recursion is generally
less efficient than looping because of all the (recursive) function
calls, each of which takes some system overhead that is absent in a
loop, but a good compiler will automatically turn certain kinds of
recursive functions into iterative ones.
The factorial function: N! = N*(N-1)! is "naturally" recursive (by
it's very definition: it's defined in (smaller) terms of itself). A C
function follows directly from the definition:
int fac (int N) {
if (N==0) //0!=1, by definition
return 1;
else
return N * fac(N-1); //N!=N*(N-1)!
}
Table 7.1 shows that there are 5 calls of the function when the
original argument is 4: when it's 4, then when it's 3, then when 2,
then when 1, then 0. For the fac function, the argument 0 is the
"base case" which does not have a recursive call, "bottoming out" the
"recursing down". A recursive function must have one (or more) base
cases. For the fac function, each recursive call has a smaller value
than the "problem" the current call is working on. A recursive
function's recursive call (or calls) must be on smaller versions of
the data, thus leading inexorably to the base case. When a base case
is reached the recursive calls "come back up", returning to where they
were called from. Verifying existence of base case(s) and recursion
on smaller version(s) is mechanical. It's the general case situation
of verifying that the whole thing works correctly that is difficult
and non-mechanical and that takes human ingenuity.
I've put a program that lists the N! permutations of N items in the
class web site in Chapter7/. It's a bit complicated though...
Chapter7/ of the class web site has a fibo.cpp program that computes
the Fibonacci numbers. This is a recursive function that has two
recursive calls. Download and experiment with it.
It helps to learn recursion by applying it to problems for which you
know an iterative solution. Searching an array for a particular value
can be done recursively. View the array as a recursive data structure
(i.e. defined in terms of smaller versions of itself): an array is an
element followed by a (sub)array. Page 400 has the recursive search
function. Note that it has two base cases: one when the search is
successful, and the other when the search is unsuccessful (i.e. when
the end of the array is reached). Note that the smaller version
requirement is met: the recursive call is on the remaining array,
i.e. the subarray following the current element.
Determining the number of combinations of N items taken R at a time is
another naturally recursive definition. Writing a C function for such
naturally recursive definitions is straightforward. You might have
seen another formula to calculate the number of combinations:
C(N,R)=N!/(R!(N-R)!). This formula wouldn't use the recursive
definition of combinations, although it could use the one for
factorial. Listing the combinations is more interesting. See the
combos.cpp program in class web site Chapter7/; it lists the
combinations of N things taken R at a time.
Accessing the nodes of a singly linked list in reverse order (RevPrint
p. 406) can be done recursively: access the nodes in the remainder of
the list, then access the current node. Notice in the C function that
the base case is when listPtr is NULL, the function does nothing but
exit (i.e. the recursion stops).
The binary search that we learned in chapter 3 is actually a recursive
algorithm that we implemented iteratively. Now (p. 408) we see the
truer nature of it. As a search, it's got two base cases: one for
success and one for failure when all items (that could possibly be the
sought-for item) have been looked at. The book's function returns the
Boolean result of the search, but the function could be modified to
return the index of the found item, or -1 (i.e. an impossible index)
to indicate unsuccessful search. Notice that the function returns the
value of the recursive function calls (a common error is to leave out
the "return" of the recursive calls.)
Inserting and deleting into a linked list can also be done
recursively. The code is simpler than the looping ways we've seen,
but more difficult to understand and subtler.
I recommend exercises 7-17 as a way to work with recursion. It
takes practice to get the hang of it. You should definitely code the
Fibonacci function, Newton's method for square rooting (14.) and
Ulam's function as practice.
The section on How Recursion Works can be lightly skimmed. It's not
critical to know how recursion is implemented by the compiler in order
to use recursion, although it might help. Have a vague notion of the
existence of the runtime stack that stacks the activation records, one
for each call of a function, containing the arguments and local
variables of that call, thus allowing recursion.
An incorrect recursive function can lead to infinite recursion, where
the recursing never ends. It's similar to infinite looping. Infinite
recursion will eventually use up all the memory available for the
runtime stack and then the program will be terminated. Here's a bad
function. It doesn't have a base case. Have fun with it. It will be
terminated by the OS (or maybe it will terminate a lousy OS).
void inf_recurse (int x) {
cout << "hello: " << x << endl;
inf_recurse(x-1);
}
Comment out the cout and add a counter that increments each call. For
each 100000 calls output a message so you can estimate how many calls
occur before the program is terminated. Use the badrecursion.cpp
program on the class web site.
Here's another bad function. It doesn't recurse on a smaller version.
void inf_recurse2 (int x) {
if (x > 0) {
cout << "hello: " << x << endl;
inf_recurse2(x);
}
}
A recursive function will be less efficient than the corresponding
iterative one. For a large-sized problem it might be necessary to use
the iterative version. A tail recursive function, in which the single
recursive call is the last statement executed in the function, can be
easily converted into an iterative function. So easily that the
compiler can do so automatically (and good compilers do). (Binary
search, factorial, and sequential search are tail recursive
functions.) Recursive functions whose recursive call is not the last
statement executed in the function, or that have more than one
recursive call, can be converted into iterative functions that use a
stack. (RevPrint, fibonacci, and quicksort are not tail recursive.)
In these cases the implicit use of the runtime stack is changed to the
explicit use of the programmer's own stack. The resulting iterative
function is invariably more complicated than the recursive version.
The book provides good guidelines on pages 426-428 for when to use
recursion in practical programs.
The Case Study about Quicksort will be included as part of chapter 10.
You don't need to study it now.
----------------------------------------------------------------
Homework
Due: 24 Nov
Write a program for a modified exercise 16 on page 442.
The user enters the number of rows and the number of columns. The
grid is rectangular, not necessarily square. The program reports how
many ways there are to go from the start at the lowerleft corner to
every other position (including the finish at the upperright corner)
moving either up or rightwards. Moving down or left or diagonally
isn't allowed. Use a 2D array of integers that records this
information; display it as a 2D grid when the information has been
calculated.
We want to find all paths in this "maze" of no walls.
The book has a partial solution that deliberately does not work, but
you'll still have to think about how to do the problem; randomly
changing the code probably won't yield the correct version. You must
use the recursive method. Hint: There are 48620 ways to get to 10,10.
There's about four billion ways to get to 20,17.
You might notice the similarity to combinations.
----------------------------------------------------------------
The proctored exam is week 12: 24 Nov - 26 Nov. You must schedule a
time at your UMUC site to take the exam. It's format is "short
answer", meaning coding mostly. There will be some tracing of code,
in particular recursive functions. You need to know the big-O
functions for the algorithms and data structures we've covered.
You'll need to be able to write linked list code, member functions
including copy ctor, and recursive functions. You'll need to know
binary search.