Chapter
2 – Part 2
We have studied some simple examples of recursion. In this course we will not get into more complex examples. But we need to cover one more example. This is on page 73 of your text, Mr. Spock’s Dilemma (Choosing k out of n things).
On the
surface this seems like an easy problem. Suppose you had 4 shirts, a red one
(R), a blue one (B), a white one (W) and a green one (G). You have to choose
two out of the four. How many ways can you do it? Well, you can choose any of
the following pairs:
RB
RW
RG
BW
BG
WG
There are 6 ways. The order of how we pick them does not
count. But what if someone asked you how many ways there were of choosing 15
things out of 140 things? Hmm, you may have some difficulty. This is where Mr.
Spock of Startrek comes in. He knows that there are N planets yet to visit on
his trip through space, yet he also knows that he only has time to visit K of
them. How many ways can he choose K planets out of N planets. He starts to
think about this problem and starts looking at a certain planet called Planet
X. He can choose to go to Planet X or not. If he does go to Planet X, he has
eliminated one of the possible choices and he now only has to determine how to
choose K-1 planets out of N-1 planets. (Notice we have reduced the problem a
little, just like we wish to do when we are looking for a recursive function.
However, Mr. Spock may choose not to visit Planet X. If he does not, then he
has to choose K planets out of the N-1 remaining. (Again, we have reduced the
problem slightly.)
Now if
you think about this, you will note that if we add the number of ways of
choosing planets if he visits Planet X to the number of ways to visit the
planets if he does not visit Planet X, we will have counted every possible way
of choosing K planets out of N planets.
Now
let’s think about some of the really simple cases (the base cases). How many
ways are there of choosing N things out of N things? Only ONE! The only way of
choosing N things out of N things is to choose all of them. Also, how many ways
are there of choosing 0 things out of N things? Again, only ONE way (i.e. you
do nothing; you make no choices whatever).
Also you may say, how many ways can you pick 5 things if you have only
four to choose from. In this case the answer is ZERO. It is impossible to do.
Now we
are ready to write our recursive method because we have some base cases and we
also know ouw to reduce the problem slightly. Here it is:
public int combinations(int k, int n) {
//---------------------------------------------
//Computes the number of groups of k out of
n things.
//Precondition: n and k are nonnegative integers.
//Postcondition: returns combinations(n, k).
//---------------------------------------------
if ( k == 0 || k == n)
return 1;
else
if ( k > n )
return 0;
else
return combinations(n–1, k–1) +
combinations(n-1, k);
}
Isn’t this exciting!!!!!!
In CSC-117 you learned about arrays. Some are one-dimensional and others have more than one dimension. In this discussion we will deal with only one-dimensional arrays.
Consider an array of 16 integers, like this:
|
3 |
7 |
9 |
18 |
17 |
20 |
5 |
0 |
30 |
22 |
12 |
11 |
27 |
2 |
8 |
1 |
Now suppose I were to ask you to write a method that
would find the largest number on the array. You would probably write a for-loop
and keep checking one number against the next until you had found the largest
one.
Is there another way? Yes. Recursion! Let’s see how.
Look at the first half of the array. The largest number
there is 20. Look at the second half. The largest number there is 30. So the
answer to our problem is the maximum of the largest number in the 1st
half and the largest number in the 2nd half.
Now look at only the first half, the numbers from 3 to 0.
Divide it in half. So now we have two arrays each containing four numbers ( 3,
7, 9, 18) and (17, 20, 5, 0). The largest number in the first half is 18 and
the largest in the second half is 20. Therefore the largest in the first 8
numbers is the 20. Do you see what we are doing? We are continually dividing
the array in half and looking for the largest numbers in each of the halves,
and then picking the largest of those two. This is called a Binary Search
method. It is called “binary” because of the continual divisions into two
parts.
A
pseudo-code algorithm for this method is given on page 76 of your text:
if
(anArray has only one item)
maxArray(anArray)
is the item in anArray
else
if
(anArray has more than one item)
maxArray(anArray)
is the maximum of
maxArray(left
half of anArray) and
maxArray(right
half of anArray)
Of
course, we were using a nice 16 element array where we could divide it into
pieces that were 8 numbers long, then 4 numbers long, then 2, then 1. In
reality arrays can be of any size, so we have to worry about odd numbers and
where to actually “break” the array in half.
Let’s try to write this method in Java.
The
Binary Search technique has been around for a long time. Most of the time it is
used not to find the largest element in an array, but rather to find any given
element in an array. For example, you may have an array that has 1000 elements
given to you (i.e. passed as a parameter) and you have to determine if some
given number, say 77 is actually in the array or not. Notice that we are not
looking for the largest element now. We are asking a different question. Is the
number 77 in the array that was given to us?
In order to use the binary
search method on this type of problem however, we need to impose an extra rule
on the array. If the array is all jumbled up, there will be no advantage in
using a recursive binary method over a
straightforward loop. So, in order to speed things up, we will tell the
user that if he/she wishes us to perform a binary search on an array, then
he/she must give us an array that is already ordered (i.e. sorted so that the
smallest number is in the first position, the largest in the last, etc.)
Here is the actual code in Java:
public
int binarySearch(int anArray[], int first, int last, int value) {
//
Searches the array items anArray[first] through anArray[last] for “value”
// by
using a binary search technique.
//
Precondition: 0<=first,
last<=SIZE-1, where SIZE is the maximum size of
// the array, and anArray[first]<=anArray[first+1] <= …
// <=
anArray[last].
//
Postcondition: If “value” is in the
array, the method returns the index
// of the array item that equals
“value”; otherwise the
// method will return a –1 (an
invalid index).
int
index;
if (first
> last)
index
= -1; //the value was not found.
else
//Invariant:
If value is in the array then
// anArray[first}<=value<=anArray[last]
int
mid = (first+last)/2;
if(value
== anArray[mid])
index
= mid; //value found
else
if(value
< anArray[mid])
index
= binarySearch(anArray, first, mid-1, value);
else
index
= binarySearch(anArray, mid+1, last, value);
}
Let’s think up an example array and see how this works by following the method through all of the checks and recursive calls.
We will also do some of the exercises at the end of Chapter 2 in
class.
Your next assignment is from pages 98 thru 102, problems 9, 10, 14,
15 and 22. I do not want you to write actual programs that can be executed, but
for the last few problems, you will have to write methods. Please type this
assignment so it is easy to read.