5a. Recursion

Recursion, what is that?

From Wiipedia: Recursion (see recursion), in mathematics and computer science, is a method of defining functions in which the function being defined is applied within its own definition.

Here is the problem, or actually 3 problems!

Create a program using recursion that does the following:

• 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). Write a method listMnemonics that will generate all possible letter combinations that correspond to a given number, represented as a string of digits. This is a recursive backtracking problem, but you are trying to find all the "solutions", not just one. In fact you are trying to find all possible Strings, not just Strings that are actual "words".

For example, if you call

ArrayList<String> result = recursiveObject.listMnemonics("623")

your method shall generate and return an ArrayList containing the following 27 possible letter combinations that correspond to that prefix:

MAD MBD MCD NAD NBD NCD OAD OBD OCD

MAE MBE MCE NAE NBE NCE OAE OBE OCE

MAF MBF MCF NAF NBF NCF OAF OBF OCF

• The program reads a single integer from the user. If that integer is less than 1, it prints an error message and stops. Don't ask for a better value. Stop. Otherwise, it prints a pattern of integers as demonstrated in the table below. There is a space before each integer, a newline after each integer greater than 5, and the underlines and boldface are hints to help you see that pattern and are not printed by your program. Your program should work for any positive integer, but because it prints 2n-1 numbers (plus spaces) for input n, do not test it with anything bigger than 15.

Things to note

• If you are not sure on any part of the problem, just ask me and I will give you additional information

• You MUST use recursion to solve the problems.

• You just get a 4+ if you get it working!

• See Marking Rubric

• Ensure you work through (in order):

This produces a numeric pattern symmetric about n where each half before and after n is also symmetric around n-1. The newline after printing any integer larger than 5 provides a nice line length and also makes the pattern of the bigger numbers along the right edge reading down. If you get the normal pattern, that will just happen. Don't think about it. Output for an input of 7 is:

 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6

 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7

 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6

 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

• The program reads a single integer from the user. If that integer is less than 1, it prints an error message and stops. The hourglass base case with input 1 displays two lines with one star on each line. Otherwise, it prints a pattern of asterisks or stars (*) as shown below for an input of 4. Note that there are four stars (and spaces) on the first and last lines.

* * * *

* * *

* *

*

*

* *

* * *

* * * *

Or, you could just do this!

Create a program Boggle program, like this.

Finding all the different possible words is a recursive algorithm. You can then use a web service to see if the string is really a word.

Two part assignment

This is a 2 week assignment:

• Week 1 hand in DESIGN ONLY
  • Top-down, Flow-chart (but not pseudo-code) and test cases (to describe some test cases you will be looking for)
• Week 2 hand in EVERYTHING ELSE
  • plus the stuff from part a

Each week ENSURE you include the Marking Rubric

Things to note

• If you are not sure on any part of the problem, just ask me and I will give you additional information
• You MUST use recursion to solve the problems.
• You must do ONE (1) of the above programs (get a 3+)
  • Get a 4- if you do 2 out of 3
  • Get a 4+ if you do all 3 of them
• See Marking Rubric
• Ensure you work through (in order):
  • Class diagram(s)
  • Flow-chart(s) (for each major method in your class diagram)
  • Final, debugged, commented code
  • Screen shots proving test cases are correct
• Ensure you follow the "Hand in Process"