CS 307 - UT Extension- Fall 2001
Assignment 5, Recursion

Handed Out:    October 15, 2001
Due:    Before 11:59:59 p.m. Thursday October 25, 2001
Purpose: To practice writing recursive methods
Provided classes: None!

"Recursion captures the infinite in finite form"

Background: In this assignment you will be putting aside most of our object oriented concepts in order to practice writing recursive methods. Many of the methods will use recursion to solve problems that could just as easily if not more easily be solved using iteration, but you will use recursion for the practice. You will collect all of these methods in a single class, Recursive. All methods shall be non static. Remember, when writing a recursive method you first need to identify the Base case(s) and the recursive case(s).

1.    Write a method that recursively determines if a String is a palindrome, a word spelled the same backwards and forwards such as deified, racecar, testset, and aibohphobia (the fear of palindromes.) The Base case would be a string of length 0 or 1. The recursive case would be to return true if the first and last letters are the same and the String remaining after stripping off the first and last letters is a palindrome.

public boolean isPali(String word)

2.     Suppose that you have somehow been transported back to 1777 and the Revolutionary War. You have been assigned a dangerous reconnaissance mission: evaluate the amount of ammunition available to the British for use with their large cannon which has been shelling the Revolutionary forces. Fortunately for you, the British—being neat and orderly—have stacked the cannonballs into a single pyramid-shaped stack with one cannonball at the top, sitting on top of a square composed of four cannonballs, sitting on top of a square composed of nine cannonballs, and so forth. Unfortunately, however, the Redcoats are also vigilant, and you only have time to count the number of layers in the  pyramid before you are able to escape back to your own troops. To make matters worse, computers will not be invented for at least 150 years, but you should not let that detail get in your way. Your mission is to write a recursive method cannonball that takes as its argument the height of the pyramid and returns the number of cannonballs therein.

public int cannonball(int levels)

3.  On the standard Touch-Tone™ telephone dial, the digits are mapped onto the alphabet (minus the letters Q and Z) as shown in the diagram below:

In order to make their phone numbers more memorable, service providers like to find numbers that spell out some word (called a mnemonic) appropriate to their business that makes that phone number easier to remember. For example, the phone number for a recorded time-of-day message in some localities is 637-8687 (NERVOUS). Imagine that you have just been hired by a local telephone company to write a method listMnemonics that will generate all possible letter combinations that correspond to a given number, represented as a string of digits. For example, if you call

recursiveObject.listMnemonics("723") 

your method shall generate and print out (using recursion) the following 27 possible letter combinations that correspond to that prefix:

The order you print the combinations and number of combinations per line is unimportant.  You can use the following helper method:

public static String digitLetters(char ch)
{
    switch (ch) 
    {  case '0': return ("0");
       case '1': return ("1");
       case '2': return ("ABC");
       case '3': return ("DEF");
       case '4': return ("GHI");
       case '5': return ("JKL");
       case '6': return ("MNO");
       case '7': return ("PRS");
       case '8': return ("TUV");
       case '9': return ("WXY");
       default: {System.out.println("Illegal digit"); System.exit(1);return"";}
    }
}

public void listMnemonics(String number)

You will probably find it useful to create a method that does most of the real work:

public void recursiveMnemonics(String prefix, String rest)

4.    Write a method to recursively print the binary equivalent of an int N.  Example the binary equivalent of 13 may be found by repeatedly dividing 13 by 2.  If there is a remainder a 1 gets printed otherwise a zero gets printed. 

13 / 2 = 6 r 1
6 / 2 = 3 r 0
3 / 2 = 1 r 1
1 / 2 = 0 r 1

13 in base 2 is 1101.

This is very similar to an example in the book but less general.

// pre N >= 0
public void printBinary(int N)

5.    Write a recursive method that prints out the elements of a String in reverse order.

public void revString(String target)

recursiveObject.revString("Calvin and Hobbes");

would produce an output of:

sebboH dna nivlaC

6.    Write a recursive method to determine the sum of the digits of an integer. 51624 = 5  + 1 + 6 + 2 + 4 = 18. 

//pre N >= 0
public int sumOfDigits(int N)

7.    Write a program to determine the number of organisms in a matrix.  A matrix is defined as a 2D array of elements. Each cell can be occupied by a cell or empty. An organism consists of a cell and all the cells connected directly to that one via up, down, left, and right movements. Given the following matrix with occupied cells marked by a "*" how many organisms are there?

There are 5 organisms as shown below:

Write a method that accepts a 2D array of booleans (true if an element contains a cell and false otherwise) and returns the number of organisms on the board. Write the method (or a helper method) so that it determines this recursively. This is a flat world that does not wrap around. You may alter the world during your execution.

public int numThings(boolean[][] world)

8.    Write a recursive method to determine the minimum element in an array of integers

public int min(int[] list, int minSoFar)

Back to the cs 307 homepage.