Recursive Definitions to Recursive Code

Questions

(a)     Write out the recursive definitions for each of the following. Remember that you need a base case and a recursive case.

I.         Fibonacci Sequence – takes a number and returns that position in the Fibonacci sequence.

II.       Factorial – takes one number and uses recursion to return the factorial of that number

III.     Addition – takes two numbers and uses recursion to add them.

IV.     Exponent – takes a number and the power it is to be raised to and uses recursion to evaluate the result.

V.       Multiplication – takes two numbers and uses recursion to multiply them

VI.     Palindrome (aka. A symmetric word. For example kayak, racecar or noon) – takes a char array and returns 1 if it is a palindrome and 0 if it isn’t.

(b)     Code functions that use recursion to do each of the above.

Example:

In the Morse-Thue Sequence, you start with either a 0 or a 1. If you have a 1, you replace it with 10 in the next generation. If you have a 0, you replace it with a 01 in the next generation. Here is the first couple of generations:

generation 0: 0
generation 1: 01
generation 2: 0110
generation 3: 01101001
generation 4: 0110100110010110

Recursive Definition:

This mirrors the code that we will eventually write.

Base Case: we are at the 0th generation, stop.

Recursive Case: Calculate this generation's replacement. call the code again to repeat it on the n-1 generation.

Code:

I have given the entire program here to help you code it.

import java.io.*;

public class Morse_Thue

{
public static void main (String args [])
{
   System.out.println (pattern ("0", 4));
}


public static String mtpattern (String starter, int gens)
{

   String finisher = "";

for (int i = 0 ; i < starter.length () ; i++)
{

   if (starter.charAt (i) == '0')
   finisher = finisher + "01";
else
   finisher = finisher + "10";

   }

if (gens - 1 != 0)
   return mtpattern (finisher, gens - 1);
else
   return finisher;

   }

}

You will, no doubt, have noticed that this could be coded by a double for loop. This is true. In this instance, it would have been a lot easier to code it that way. However, there are instances where recursion is a MUCH MUCH MUCH faster way to code something. It is a very powerful concept that we are going to practice on some smaller, simpler examples first. don't bother whining, I won't hear you.