CSC 161 Lab 6-1 and Project: Recursion

This lab/project will give you an opportunity to work with recursion. Take a look at the screenshot below:

This frame displayed is the user interface of a program that allows a user to input arguments for seven different methods and then call the method on those arguments be pressing the Compute button.

The seven methods include three methods that compute the simple arithmetic operators: the sum, product, and power of two numbers (Caution: we assume that the second number, n, is always nonegative!) When you press the Compute button, the result of the method call is displayed in the pink result text field. The result text field is non-editable, so it is for input only.

Among the seven, there are four methods that take a single string argument, and return a value. These are methods to determine if a string is a palindrome, to reverse a string, to transform a string to uppercase, and to count the number of uppercase letters in a string.

All seven method are fully written, and the program is fully functional. You can download the zipped-up Netbeans Lab6_1Recursion.zip folder that contains the program. Unzip the folder onto your computer, and use Netbeans to open the project. You do this by starting Netbeans, going to the File menu, and selecting Open Project... You can then run the program, and it will work, just like you see in the screen shot above.

But of course, there is a catch. All the methods are implemented using loops, or iteration. Your assignment is to go through the code, find each of the seven methods, and replace them with recursive methods with the same name that take exactly the same parameters. The methods to be replaced are the following:

 
   private int sum(int m, int n)
    {
       // start with n and add 1 n times
       int result = m;
       int k = 1;
       while (k <= n)
       {
           result = result + 1;
           k++;
       }
       return result;
    }

   private int product(int m, int n)
    {
        // start with 0 and add m   n  times
        int result = 0;
        int k = 1;
        while (k <= n)
        {
            result = result + m;
            k++;
        }
        return result;
    }

    private int power(int m, int n)
    {
        //  Start with 1 and Multiply by m   n times
        int result = 1;
        int k = 1;
        while (k <= n)
        {
            result = result * m;
            k++;
        }
        return result;
    }

   private boolean isPalindrome(String str, int low, int high)
    {
       int lo = low;
       int hi = high;
       while (lo < hi)
       {
           if (str.charAt(lo) != str.charAt(hi))
               return false;
           lo++;
           hi --;
       }
       return true;
    }

    private void reverse(StringBuilder sb, int low, int high)
    {
        int lo = low;
        int hi = high;
        while (lo < hi)
        {
            char loChar = sb.charAt(lo);
            char hiChar = sb.charAt(hi);
            sb.replace(hi, hi+1, String.valueOf(loChar));
            sb.replace(lo, lo+1, String.valueOf(hiChar));
            lo++;
            hi --;
        }
    }

    private void upperCase(StringBuilder sb, int start)
    {
        int k = start;
        while (k < sb.length())
        {
            char ch = Character.toUpperCase(sb.charAt(k));
            sb.replace(k, k + 1, String.valueOf(ch));
            k++;
        }
    }

    private int countUpperCase(String str, int start)
    {
       int count = 0;
       int k = start;
       while (k < str.length())
       {
           char ch = str.charAt(k);
           if (Character.isUpperCase(ch))
               count ++;
           k++;
       }
       return count;
    } 

Yes I know there are simpler ways to write these methods, but we are trying to use these as tools to learn the technique of recursion here. The point is that all these methods are written using loops. You should replace them with equivalents that do the same "algorithm", but do it recursively.

Due date: Saturday at the end of Week 6.

Project

A prime number is a positive integer that is divisible by exactly two different integers, 1, and itself. For example, 2 is a prime number, 3 is prime, and so are 11, 19, 23, and a whole lot of other numbers. On the other hand, 1 is not a prime number, because it is not divisible by two different integers. The number 12 is not prime, because it is divisible by more than two integers: 1, 2, 3, 4, 6, and 12.

1. Write and test a method boolean isPrime(int n) that returns true when n is prime, and returns false otherwise.

2. Write a non recursive method

 
void getPrimeFactors(int n, StringBuilder primeDivisors)
or
void getPrimeFactors(int n, List <Integer> primeDivisors)

(Your choice which of these two you write). This method will take a positive integer n as parameter and add to the StringBuilder or list object passed to it, the all prime factors (with repetitions) of n separated by commas. For example, if n = 12 then the primes

 2, 2, 3
are added to the string builder (or list). If n = 17 then the single number
17
is added to the string builder (or list). If n=84 then the numbers
2, 2, 3, 7
are added.

3. Write a recursive version

void RecGetPrimeFactors(int n, StringBuilder primeDivisors)
or
void RecGetPrimeFactors(int n, List <Integer> primeDivisors)

of whichever method you wrote above.

4. Test all three of your methods to make sure they work correctly. You can use a console application that asks the user to enter a single integer. Then, the program will feed the integer to all three methods and and print the results. Here is an example of the output when the input is n = 17

17 is a prime number.
List of prime factors of 17 is [17]
List of prime factors of 17 is [17]
Here is example of the output for the input n = 84.
84 is not a prime number.
List of prime factors of 84 is [2, 2, 3, 7]
List of prime factors of 17 is [2, 2, 3, 7]

Note that the second and third lines of the ouput will always match because the recursive and non recursive versions of the same method should produce the same output.

Due Date: Wednesday of Week 7.

Optional, For the adventurous: You can use a graphic user interface with a text field for the user to enter a value. You can use a JTextArea to display the output.