8
Recursion
Objectives
An introduction to the concept of recursion
Examples of recursively defined functions, such as factorials, the Fibonacci
sequence, the “3n + 1 function,” and the Ackermann function
Use of recursion in program code, including binary divide-and-conquer algo-
rithms
Recursion for computing permutations and combinations
Recursion for gaming and search tree computation
Dealing with memory use in recursion
Key Terms
3n +1problem
Ackermann function
binary search
Collatz problem
context
Fibonacci sequence
heuristic
objective function
recursive
Syracuse problem
Introduction
The concept of recursion is central to computer science. A standard way to solve a
complex problem is to break it down into smaller problems and then to solve the
complex problem by solving the smaller problems. In essence, recursion is a variation
on this common approach, a variation in which the smaller problems are in fact just
smaller versions of the original problems. Most modern programming languages,
including Java, support recursion and, although the specifics of implementation may
differ from one language to the next, the concepts used in recursion are independent
of the programming language.
185
186 CHAPTER 8RECURSION
8.1 Factorials and Fibonacci Numbers
A recursive algorithm, function, or program is one that calls, that is, invokes, itself.
Two of the classic examples of functions that can (or should) be defined recursively
are the Fibonacci sequence and the factorial function.
The Fibonacci sequence of integers is
1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...
The nth Fibonacci number F
n
is defined by
F
n
= F
n−1
+ F
n−2
subject to the base conditions
F
1
=1,F
0
=1.
We are more familiar with the factorial function N!. This can be written in a
nonrecursive way as
N!=N ·(N − 1) ·····(2) · 1
oritcanbewrittenas
N!=N ·(N − 1)!
subject to the base condition
0! = 1.
Recursion is often the best way to describe a computation. In the case of the
Fibonacci sequence, there is a closed form solution that can be worked out alge-
braically, but the recursive formula is conceptually much clearer.
In both cases, and in defining functions recursively, there are two parts to the
definition.
• First, we define what is in effect the steady-state function, such as
N!=N ·(N − 1)!.
In this part of the definition, we define the function for parameter N in terms of
the function when given smaller input parameters (N − 1 in the case of factorial
and both N − 1andN −2 in the case of the Fibonacci sequence).
• Second (and this is the part most often omitted in error or incorrectly specified),
we define the base condition that allows us to know when to stop the recursion.
For the factorial function, this is the base condition that 0! = 1. The factorial
function is a single-step recursion, so we need one base condition. Since the
Fibonacci sequence is defined as two-step recursion, we need to specify the
base case for both 0 and 1.
8.2 The Collatz Problem 187
Note that we could produce (almost) the same sequence by starting with any two
consecutive values as our base case for the Fibonacci sequence. For example, if we
define F(0) = 0 and F(1) = 1, we get the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,...,
but if we define the base cases F(0) = 3 and F(1) = 5, we get the sequence
3, 5, 8, 13, 21, 34,..., which is the same sequence except that it skips the initial
values. We can also produce Fibonacci-like sequences by applying the same recur-
sion but with different base cases. For example, with F(0) = 2 and F(1) = 1, we get
the sequence 2, 1, 3, 4, 7, 11, 18, 29, 47,.... This is called the Lucas sequence,after
the French mathematician Edouard Lucas. In general, such sequences are called lin-
ear second order recurrences, with “linear” meaning that the F(N) terms appear in
the recurrence as polynomial terms to the first degree and “second order” referring
to the fact that we need two consecutive values in the base case in order to define
the sequence uniquely.
8.2 The Collatz Problem
The Fibonacci sequence is a well-behaved sequence that is quite naturally defined
recursively, although it is also possible to work the algebra through to a closed
form for Fibonacci numbers. In both the factorial and the Fibonacci sequence,
computation of N!orofF(N) is a deterministic process. To compute N! recursively
requires exactly N function calls, each of which operates on successively smaller
parameter values. Computing F(N) recursively is slightly more complicated but
still deterministic. One can show that
F(N)=
1
√
5
⎡
⎣
1+
√
5
2
N
−
1 −
√
5
2
N
⎤
⎦
.
We won’t prove this, not because it is hard (it’s only high school algebra) but
because it is off the topic of this book.
A different function that is also defined recursively but whose computation is not
(yet) known to be a deterministic process is the function for the Collatz problem,
also called the 3n +1problem or the Syracuse problem. We define a function that
can be iterated as follows.
C(n)=3n +1 ifn is odd
= n/2ifn is even.
Unlike most recursive functions, in which we know the behavior of the function
involved, this particular function happens to be the study of some open questions
in research. For all values of n for which C(n) has ever been computed, the function
eventually iterates down to the value 1. However, it has never been proved that
188 CHAPTER 8RECURSION
iteration of this function always results eventually in 1, nor has there ever been
a really good result on how many iterations are necessary before 1 is reached.
Powers of 2 clearly iterate down to 1 immediately. On the other hand, C(27) takes
111 steps to reach 1, and the high-water marks for n<10
8
and for n<10
9
are
63,728,127 and 670,617,279, respectively. Although no real use has been found for
this mathematical curiosity, it remains an interesting example of a function that is
very easy to define, and defined recursively, but which as yet cannot be completely
analyzed and cannot be described except recursively.
8.3 Greatest Common Divisor
Yet another mathematical function that has a computationally simple formulation
using recursion is the greatest common divisor,orgcd. The greatest common divisor
of two integers n and m is the largest positive integer g such that both n/g and m/g
are integers. We write g =gcd(m, n). The simplest algorithm for calculating the gcd
is the Euclidean algorithm. The description of the Euclidean algorithm in Euclid’s
Elements is perhaps the earliest written description in history of an algorithm as
we know it, and although there are slightly more sophisticated ways to compute
the gcd, the standard method using the Euclidean algorithm has been virtually
unchanged for more than two millennia.
Euclid’s algorithm relies on two simple theorems that we will not prove.
Lemma 8.1
Given positive integers m and n, we can write m = q · n + r,withq and r positive
integers and r satisfying 0 ≤ r<n.
Lemma 8.2
Given positive integers m and n,withm = q · n + r as in Lemma 8.1, then
gcd(m, n)=gcd(r, n).
Computationally, we recognize q in the preceding lemmas as due to the rules of
integer division in Java, m/n, and we recognize r as m%n. This means that we can
define the gcd recursively (ignoring error conditions) as
gcd(m, n)=gcd(n, m%n)
and we are guaranteed that with the second call to the gcd function the second argu-
ment is smaller than the first argument, and with succeeding calls the arguments are
continually getting smaller. Because the arguments are getting smaller with each
recursive call, the recursion must eventually terminate. A Java method for the gcd
8.4 The Ackermann Function 189
follows. The first lines of this method ensure that it works for positive and negative
integers (the convention is that the gcd is always positive, even of two negative inte-
gers) and that we do not inadvertently call the method with a zero second argument.
If the first argument m is zero, the gcd is n. If both arguments are zero, then techni-
cally the gcd should be infinity, which we indicate symbolically (there is no integer
infinity in Java, so the value returned by calling the method with two zero argu-
ments would have to be defined by convention). We use as the base case the point
at which the remainder n is zero, at which point we return the other argument m.
public int gcd(int m, int n)
{
m = Math.abs(m);
n = Math.abs(n);
if(0 == n)
{
if(0 == m)
{
return INFINITY;
}
else
{
return m;
}
}
else if(0 == (m % n))
{
return n;
}
else
{
return gcd(n,m%n);
}
}
8.4 The Ackermann Function
Another function that is defined recursively, and which does have a history in com-
puter science, is the Ackermann function. There are in fact several variants of the
original Ackermann function, which was used as an example in the early days of
computability theory, but the one most commonly known in computer science is
defined as a recursion on two variables as shown in Figure 8.1.
190 CHAPTER 8RECURSION
A(m, n)=n +1 if m =0
= A(m − 1, 1) if m>0andn =0
= A(m − 1,A(m, n − 1)) if m>0andn>0
FIGURE 8.1 The formulas defining the Ackermann function.
The real study of the Ackermann function is limited to the theory of computing,
but the function is a common example in introductory texts in computer science. It
is a function that is very easy to specify and write a program for, but it grows very
rapidly even for small values of m and n. The code required is very simple, but only
the very smallest values can be computed because there is no nonrecursive definition
of the function and yet a recursive program will run out of memory for all but the
smallest inputs. Indeed, A(3, 3) requires more than 3000 method invocations before
returning the value 61, and A(4, 2) is an integer nearly 20,000 decimals in length.
8.5 Binary Divide-and-Conquer Algorithms
We can also define in a recursive way a divide-and-conquer algorithm for binary
search. In our earlier definition of binary search, we compared the key to be searched
for with the midpoint element in an array, determining whether the item would be
found in the first half or the second half of the array, and then we repeated the
process. Our iterative (and thus nonrecursive) program was essentially the following.
set lower and upper subscript bounds
while(lower < upper)
{
midpoint = (lower + upper)/2
compare the search key K against the midpoint
if(f(lower) < f(midpoint) < K < f(upper))
{
lower = midpoint
}
else if(f(lower) < K < f(midpoint) < f(upper))
{
upper = midpoint
}
}
This is a common way to write a method that works iteratively but which also can
be converted to a recursive version. In this iterative version, we shift pointers inside
8.6 Permutations and Combinations 191
a loop. Done as a recursive computation, we could use the following pseudocode,
wherewewrite
a[beginning_subscript ... ending_subscript]
to indicate the subarray of an array a[.] from subscripts beginning
subscript
inclusively through ending
subscript.
public int binary_search(array_to_be_searched)
{
if(array length is 1)
{
compare the search key K against the single element
set return_value if a match
}
else
{
midpoint = (lower + upper)/2
if(K < f(midpoint))
{
array_to_be_searched = array_to_be_searched[1 ... midpoint]
}
else if(f(midpoint) < K)
{
array_to_be_searched = array_to_be_searched[midpoint ... end]
}
call binary_search(array_to_be_searched)
}
return return_value
}
In the recursive version, rather than shifting pointers into the array (or ArrayList),
we package up the appropriate lower half or upper half of the array and then call
the same method with that half of the array as the parameter. Since the array
length is cut in half each time, we know that an array of length N can be searched
with at most lg N calls to the method.
8.6 Permutations and Combinations
The factorial, Fibonacci, and gcd functions are standard functions used in explain-
ing recursion, but they don’t come up much in practical computing problems.
192 CHAPTER 8RECURSION
Similarly, the Collatz problem is fascinating (because it is so simple and yet so
little progress has been made in answering the question of whether it always ter-
minates with a 1), but this problem is really a problem in pure mathematics. The
Ackermann function similarly, although it has been useful in theoretical computer
science, is not something that has found its way into practical issues central to
computation in the real world.
In contrast, a computation that does come up in the real world, and that can
and should be defined recursively if possible, is the generation of the permutations
or combinations of a list of items. A rank-ordering of preferences of N items, for
example, can occur in N! ways because any of the possible rank orderings could
occur. It frequently happens in specifying requirements for a computation that one
must generate permutations and combinations of options if only in order to test
that one’s software works for all possible sets of input values.
One puzzle-level problem that when attacked naively is a permutation problem
is the Jumble puzzle from the newspaper, in which readers are given anagrams of
five- and six-letter words and asked to come up with the English words made up
of those letters. Given the letters “celos,” for example, one would be expected to
come up with the word “close.”
A naive method for solving the Jumble puzzle is to generate all the permutations
of the list of letters, that is, all the five-letter (or six-letter) rearrangements of
the given letters used without replacement. These putative words could then be
looked up (using binary search of course) in a dictionary of English words. The
naive solution to the Jumble puzzle is to treat the letters as a mathematical set
of N letters. We start with a “word” word initialized to the null string and then
call a permutation-generation method, passing in the set of letters and the current
value of word.
The method runs a loop over all N possible starting letters. In each iteration of
this loop we pick one letter from the set, assign that letter as the next letter in the
word by concatenating the letter onto the current value of word, remove the chosen
letter from the set, and then recursively call the method, passing in as parameters
the new set (one smaller than before) and the new partially constructed word,one
letter longer than before. The base case occurs when there are no more letters in
the set, at which point we return word as constructed.
The recursive process for generating the permutations is shown in Figure 8.2,
where we generate all possible permutations from the list of three letters {e, h, t}.In
the first step, we choose a first letter, e,addthee to the partial permutation we have
created, remove e from the list of unused letters, and call the method recursively.
The method chooses a letter (the second letter), choosing the first entry in the list,
h, adding it to the partial permutation, deleting the h from the list of unused letters,
and calling the method recursively. The third letter is now chosen, and we have the
three-letter word made up of the three letters in their original sequence order 123.
8.6 Permutations and Combinations 193
Action Partial Unused Numerical
Permutation
choose first letter e ht
choose second letter eh t
choose third letter eht 123
put back third letter eh t
put back second letter e ht
choose second letter et h
choose third letter eth 132
put back third letter et h
put back second letter e ht
put back first letter eht
choose first letter h et
choose second letter he t
choose third letter het 213
put back third letter he t
put back second letter h et
choose second letter ht e
choose third letter hte 231
put back third letter ht e
put back second letter h et
put back first letter eht
choose first letter t eh
choose second letter te h
choose third letter teh 312
put back third letter te h
put back second letter t eh
choose second letter th e
choose third letter the 321
put back third letter th e
put back second letter t eh
put back first letter eht
FIGURE 8.2 Generating permutations recursively.
At this point, when the method is called we have no more choices to make, and
we must return from the recursion, putting letters back, until we reach a point
when we can choose again. This only happens after we put back the second letter,
h, and can now choose as our second letter the t that we did not choose the first
time through.
194 CHAPTER 8RECURSION
And so forth. Note that we must maintain the context of where we are in the
recursion. For example, when we get to the second time we choose a second letter,
we need to know to choose the t and not to choose the h again.
Generating permutations is an important process, but it is also a computationally
expensive process because there are N! permutations on N distinct letters. We can
choose the first letter of our word in N ways. We have N − 1 letters remaining, so
we can choose a second letter in sequence in N −1 ways. We remove the second
letter from our set, so we now have N −2 ways to choose a third letter, and so on.
For a set with N letters, then, we can come up with N! possible permutations. Since
this grows multiplicatively with N, we can very quickly exhaust the computational
power of even a supercomputer. A number as simple as 20! is already more than 100
times greater than the number of nanoseconds in a year. Current CPU speeds are
measured in small gigahertz values. Executing instructions at a 1GHz clock speed
is the same as executing instructions at one per nanosecond. If our computer ran
at 1GHz and could generate permutations at one permutation per instruction (this
is clearly impossible, but it puts us into a rough ballpark of computation cost), we
would need about 100 computers running for a year just to enumerate the possible
permutations on 20 letters. If one had a situation in which all 20! permutations
were possible, then clearly a brute force exhaustion would likely be infeasible, but
it frequently happens that exhaustion over smaller sizes is needed.
The code for a recursive generation of permutations is shown in Figure 8.3. We
have chosen in this method not to actually do anything with the permutations
except to generate them and print them out. In reality, there is no clear action that
would be taken with a list of permutations. If the goal is simply solving the Jumble
puzzle, then one will be given only five- and six-letter input sets, and there will be
only 120 or 720 lines of output, which is manageable but tedious. In a more serious
application, though, in which one might be generating permutations of 20 inputs,
there are too many results to be printed out or displayed for human reading. What
we do with the permutations at the point where this method prints them out will
depend, then, on the application. In this case, for demonstration purposes, we can
just print them out and verify that we get the right number and that the output
lines are, as they should be, all distinct.
8.7 Gaming and Searching Applications
Another significant use of recursion is in game and search applications.
Consider, for example, a program for chess. At any given point in the game, a
program playing White will know the status of the board and pieces and will have
some numerical goodness values for the overall status of both White and Black.
In theory, then, the program would consider every possible move that White could
8.7 Gaming and Searching Applications 195
/*********************************************************************
* Method to generate the permutations of the <code>letters</code>.
* A) If no more letters, we are done, and we print the permutation.
* B) Else run a loop on i on the letters in the current list.
* 1a) Copy the current list as passed in to a new current list
* to be passed recursively to this method.
* 1b) Get the i-th letter in the new list.
* 1c) Add the i-th letter to the end of the current perm.
* 1d) Remove the i-th letter from the new list.
* 2) Call this method recursively, passing in the current perm
* and the new list of unused letters.
* 3) When the program returns from the recursion, take
* off the last letter of the current perm in preparation for the
* next iteration in the loop on i.
**/
public void generatePermutations(ArrayList<String> thePerm,
ArrayList<String> currentLtrs)
{
String letter = "";
if(0 == currentLtrs.size())
System.out.printf("%s%n", thePerm);
else
{
for(inti=0;i<currentLtrs.size(); ++i)
{
ArrayList<String> newLtrs = new ArrayList<String>(currentLtrs);
letter = currentLtrs.get(i);
thePerm.add(letter);
newLtrs.remove(i);
generatePermutations(thePerm, newLtrs);
thePerm.remove(thePerm.size()-1);
}
}
}
FIGURE 8.3
Permutation generation for the Jumble puzzle.
make, and every possible response that Black could make, and would recompute the
goodness value of the board position for White. A basic principle of game programs,
looking only at one move and one response, is that the most sensible move for White
is the move that maximizes White’s goodness value after Black’s best response.
In practice, such game-playing programs are really search programs trying to
optimize what is known as an objective function (the goodness value), and they
rarely stop after one move and response. A practical chess-playing program would
search down several move-and-response levels before coming up with a current best
move. The natural way to write such a program is via recursion. The method is
196 CHAPTER 8RECURSION
passed the state of the board, the player (White or Black), and the value of the
objective function, and it will loop through possible moves, calling itself recursively.
A somewhat different kind of recursive search would be that of a program to look
for Sudoku solutions. In the case of chess or other board games, the complexity of
game play and the number of options require one to come up with a goodness
function that measures the quality of the board status. In the case of Sudoku, one
would be much more likely to make a choice for a square to fill, verify that such
a choice is valid, and call the method recursively. Most of the time the recursive
descent would end when there is no valid choice to be made, and the program would
back up and try a different choice. In many ways, this is really just a variation on
a permutation-generating program. If one views the Sudoku tableau as having 81
squares to fill with the integers 1 through 9, and thus a total of 9
81
possible solutions
to test, the rules of Sudoku simply stipulate that large chunks of the solution space
are illegal and need not be explored further.
8.8 Implementation Issues
Naive generation of all possible solutions, whether it be of a simple Jumble puzzle,
all possible grids in a Sudoku puzzle, or for some more serious purpose, is part of a
time-honored tradition of BFI computing (Brute Force and Ignorance). Asymptot-
ically we know that we cannot apply BFI to a permutation problem of any serious
size because the number of permutations on N items is N! and this grows exponen-
tially fast. Similarly, we cannot explore all possible moves in a chess game or any
other game of similar complexity because there are just too many possibilities. We
can expect as one of the implementation issues that the search will progress only
“some number” of levels down.
There are many times in computation when we don’t have any theory that will
help us in the computation and must therefore rely on a heuristic. A heuristic is a
notion that somehow “ought” to be true or seems like a reasonable way to trim away
unlikely candidates. Suppose we are given a set of letters and told that the letters
are an anagram of exactly one English word. If in our naive search we come upon
an intermediate possible word that starts out “syz,” we could apply a heuristic that
it is unlikely that an English word exists with this letter sequence and do an early
abort of our descent down the recursion. This would run the risk of missing a word
that might exist (namely, “syzygy”), but it would allow us to prune away segments
of an otherwise exponentially large search space and thus shorten the search.
A very important issue that comes up in using recursion is that memory space
is taken up with every recursive call to the method. Every time any method is
called, some memory is allocated for the context of that method when in a state of
execution. The context contains the variables allocated as well as scratch space the
8.8 Implementation Issues 197
compiler will have felt was necessary, space for the actual executable code in some
cases, and pointers to the program that called the method and to methods called
by the current method. Although memory space is not usually an issue with small
programs, it is possible through recursion to use up all the space by doing too many
recursive method calls. In the Collatz problem, for example, the “current” integer
N not only shrinks by division by 2 but also grows when the N ← 3N +1 part of
the method is called. Because the behavior of this function is still not known, we do
not know how many recursive calls will be needed before we get to the expected end
result of 1, and there are pathological bad cases that will need so many recursive
calls that available memory space is exceeded.
A more common memory problem with recursive methods is that we would need
to pass a data array in to the method each time. We do this in our permutation
method of Figure 8.3; not only do we pass a copy of the current permutation, we
also, with each method invocation, create a new instance of newLtrs. In the case
of permutations, the depth of our recursion is known (depth N for the N-letter
inputs) and the maximum size of the variables passed in is known and small (two
ArrayLists of length no more than N), so we know that we will never need space
for more than N
2
data items. Given that the time complexity of generating permu-
tations is N!, it is highly likely that we will run out of patience for computing the N!
permutations long before we run out of the N
2
space for this program as it executes.
Although we probably won’t have to worry about memory when doing a 15-deep
recursion on 15 items to generate permutations, the same is not necessarily true
for binary search in a very large array. The naive version of our recursive search
program requires us to package up half of the input array and pass that down to the
next level of recursion. Even if we had the memory (and memory is, after all, fairly
cheap these days), it’s a colossal imbalance of processing time to do this. In binary
search, our “computational” cost is one arithmetic step to compute the subscript
for the midpoint, one lookup in the array of the element at the midpoint, and one
comparison. It doesn’t seem to make sense to move thousands or perhaps millions
of elements into and out of arrays for each invocation of a method that has only
three simple computational steps.
One way to avoid memory copying in searching is with a hybrid of the naive
recursive search and the iterative search using pointers. If we declare the array to be
searched as an array in the class but not passed as a parameter to the method that
conducts the search, then we can pass lower and upper endpoints only, replacing
the while loop with a method that recursively calls itself until the searched-for
element is found or determined not to be present.
The simplistic solution for memory-efficient binary search does not really work
in the case of permutation generation. In binary search, the data values under
consideration are contiguous in an array. In the case of a permutation-like compu-
tation, the set of values to be dealt with at any level changes, and the values are
198 CHAPTER 8RECURSION
not contiguous in the original array; values already used in the partial permutation
show up as holes in the original list of elements.
One solution to this is shown in Figure 8.4.
/*********************************************************************
* Instance variables for this class.
**/
private ArrayList<Boolean> used;
private ArrayList<String> letters;
private ArrayList<String> thePerm;
...
/*********************************************************************
* Permutation generating method
**/
public void generatePermutations(int lettersLeft)
{
String letter = "";
if(0 == lettersLeft)
{
System.out.printf("the permutation is %s%n", thePerm);
}
else
{
for(inti=0;i<this.letters.size(); ++i)
{
if(false == used.get(i))
{
letter = letters.get(i);
thePerm.add(letter);
this.used.set(i,true);
--lettersLeft;
generatePermutations(lettersLeft);
thePerm.remove(thePerm.size()-1);
this.used.set(i,false);
++lettersLeft;
}
}
}
}
FIGURE 8.4
Permutation generation without copying the array.
We create as an instance variable of the class the set of letters, letters,from
which permutations are to be generated, and we declare as an instance variable of
the class a boolean array used to indicate which elements of the letters array
8.10 Exercises 199
have already been used. We lose in computational efficiency in that we must now
iterate over the entire array letters and then skip over those that have already
been used, where in the previous version our set of current letters kept getting
smaller. We gain, however, in not having to perform a deep copy of arrays and to
pass those arrays as parameters. We also must take care to set and reset used before
and after the calls to the recursive method and to add and remove the new letter
from the running partial permutation as we progress through the computation. In
this version, we also have a counter that drops to zero when all the letters have
been used. In the previous version, we knew we had reached the base case of the
recursion when the set of letters passed in was empty. In order to make the same
determination in the code in Figure 8.4, we would need to run a loop and determine
that all the letters had been used. This extra loop for every recursive call of the
method seems excessive, and it can be avoided by using a lettersLeft counter.
In general, then, we have a common theme recurring. A simple recursive approach
is possible, for which we pay in resource utilization in exchange for programming
simplicity. A better use of resources can be made at the expense of some greater
complexity in the programming, and the right choice of which approach to take will
depend in part on the details of the computation that is needed.
8.9 Summary
We have introduced recursion, with examples including the factorial function, the
Fibonacci sequence, the “3n + 1 function,” and the Ackermann function.
We have shown how to implement recursion in program code, taking special care
to distinguish computations in which memory space for recursive function calls
will be problematic and computations for which memory usage is unlikely to be a
problem.
Recursion is used extensively in game programs and in search trees, and binary
divide-and-conquer algorithms are often implemented recursively.
Finally, among the most common uses for recursion are in computing and in
enumerating permutations and combinations.
8.10 Exercises
1. Write a complete program for computing the factorial function using recursion.
Test it thoroughly, and include in your documentation of the method for the
function a comment about the range of values that can be computed without
error. Include a variable that will allow you to keep track of the number of
method calls to the recursive method.
200 CHAPTER 8RECURSION
2. Write a complete program for computing Fibonacci numbers using recursion.
Test it thoroughly, and include in your documentation of the method for the
function a comment about the range of values that can be computed without
error. Include a variable that will allow you to keep track of the number of
method calls to the recursive method.
3. Write a complete program for verifying the Collatz conjecture that the function
eventually reaches 1 for any input N. Test your program thoroughly to find
the pathological worst cases in a range of integer inputs, and include in your
documentation of the method for the function a comment about the range of
values that can be computed without error. Include a variable that will allow
you to keep track of the number of method calls to the recursive method.
Since recursive calls take memory, the number of such method calls could be
different on different machines and configurations before system errors occur.
A user reading and using your code should be given insight into how to test
the limits of the local execution environment.
4. Write a complete program for computing the Ackermann function using recur-
sion. Test this as discussed in the previous exercises.
5. Rewrite any of the preceding programs using long variables instead of int
variables, and compare the difference.
6. Rewrite any of the preceding programs using the Java BigInteger class instead
of int variables, and compare the difference. What you should see is that
arithmetic precision is no longer an issue, but running time is increased and it
is now easier to run out of memory.
7. You are probably familiar with Sudoku puzzles. Consider the microversion of
Sudoku given here, with integers running 1 through 4 and arranged in 2 × 2
blocks. The rule is that the digits 1 through 4 must appear exactly once in each
row, in each column, and in each 2 × 2 subblock of the tableau.
1 2 3 4
3 4 1 2
2 1 4 3
4 3 2 1
Write a recursive program that will find all the legal configurations of a puzzle
of this size. You will probably want to think first about how to handle the
determination of which entries might be legal in a given location. The naive,
computationally more expensive but easier to program approach would be to
recalculate the list of legal values for each location. A more polished approach
would be to keep used lists of the illegal values, but that would require more
8.10 Exercises 201
programming. Heeding the admonition “make it right before you make it bet-
ter” might be the smart thing to do for this assignment.
8. It is not hard to become convinced that if you have one legal configuration of the
micro-Sudoku in the previous exercise, then another legal configuration can be
found by applying a permutation on the digits. That is, the permutation 1 → 3,
2 → 4, 3 → 2, 4 → 1 converts the preceding legal tableau into the following legal
tableau.
3 4 2 1
2 1 3 4
4 3 1 2
1 2 4 3
Write a program that will apply the permutations on four symbols to the first
legal configuration in order to generate 23 more legal configurations.
9. Implement a binary search dictionary lookup program. There are a number
of lists of English words available from the Web without copyright. Download
one and use it as the source data to create a lookup program using recursive
binary search. Do not pass the arrays as parameters. Rather, as suggested in
Section 8.8, pass pointers to the left and right endpoints in the search in the
recursive call to the method.
10. Finish the creation of a Jumble-puzzle-solving program by combining permu-
tation generation (using recursion) with dictionary lookup. Be sure to test
your code on words that have the same letters but form more than one word
depending on the order, such as “form” and “from” or “close” and “socle.”
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.