CMIS 241
Recursion
We'll do recursion this week. Chapter 4 is devoted to recursion. A
method or 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) method 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 methods
into iterative ones.
Actually, I don't think recursion is all that important to learn.
It's more of a computer-sciency theoretical idea.
Skip the Towers of Hanoi example.
The factorial function: N! = N*(N-1)! is "naturally" recursive (by
it's very definition: it's defined in (smaller) terms of itself). A Java
method 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)!
}
Page 242 shows that there are 10 calls of the method when the original
argument is 9: when it's 9, then when it's 8, then when 7, and so on
"down" to when 1, then 0. For the fac method, the argument 0 is the
"base case" which does not have a recursive call, "bottoming out" the
"recursing down". A recursive method must have one (or more) base
cases. For the fac method, each recursive call has a smaller value
than the "problem" the current call is working on. A recursive
method'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.
It helps to learn recursion by applying it to problems for which you
know an iterative solution. Searching a list for a particular value
can be done recursively. View the list as a recursive data structure
(i.e. defined in terms of smaller versions of itself): a list is an
element followed by a (sub)list. Page 485 ff. has the recursive search
method. 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 list is reached). Note that the smaller version
requirement is met: the recursive call is on the remaining list,
i.e. the sublist following the current element.
Determining the number of combinations of N items taken R at a time is
another naturally recursive definition. Writing a Java method 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.
Accessing the nodes of a singly linked list in reverse order (RevPrint
p. 264 ff.) can be done recursively: access the nodes in the remainder of
the list, then access the current node. Notice in the Java method that
the base case is when listRef is NULL, the method does nothing but
exit (i.e. the recursion stops).
The binary search is actually a recursive algorithm that was
implemented iteratively. It's on page 412. 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 method and associated code is overly complex (gee, what a
surprise). returns the boolean result of the search, but the method
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 method returns the value of the recursive function calls (a
common error is to leave out the "return" of the recursive calls.)
I recommend the exercises 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 (21.) 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 method, containing the arguments and local
variables of that call, thus allowing recursion.
An incorrect recursive method 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
method. It doesn't have a base case. Have fun with it. It will
eventually throw a StackOverflowError exception when the runtime stack
becomes full.
void inf_recurse (int x) {
System.out.println("hello: " + x);
inf_recurse(x-1);
}
Here's another bad method. It doesn't recurse on a smaller version.
void inf_recurse2 (int x) {
if (x > 0) {
System.out.println("hello: " + x);
inf_recurse2(x);
}
}
Comment out the output and add a counter that increments each call. For
each 1000 calls output a message so you can estimate how many calls
occur before the program is terminated. Use the BadRecursions.java
program on the class web site.
A recursive method 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 method, in which the single
recursive call is the last statement executed in the method, can be
easily converted into an iterative method. 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 method, or that have more than one
recursive call, can be converted into iterative methods 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
method is invariably more complicated than the recursive version.
The book provides good guidelines of section 4.7 for when to use
recursion in practical programs. Actually, it doesn't come up often.