Java ( data structure)

Basic Recursion

In this lab you will practice writing basic recursive algorithms. This lab comes in three parts. Each part should be submitted as a separate file of source code that is to be uploaded here on the Canvas website. Each part should also include detailed source code comments that explain the following components of your source code:

(1) comments at the beginning of your program that state your name, the lab assignment number, the text editor or IDE you used, the Java version you used, and the operating system you used

(2) comments that explain essential regions of programming logic used in your source code

(3) comments that explain the general purpose of all classes and methods used in your source code

(4) comments that explain the essential variables used in your source code

This assignment is worth 50-points, to be awarded after all labs are successfully completed. Submit your assignment as files named Towers.java, TripleCallCounter.java and recursiveSum.java making sure you have the ".java" file extension at the end of the file name. Submit Towers.java, TripleCallCounter.java and recursiveSum.java using the "Submit Assignment" button, and use the "File Upload" tab to select Towers.java, TripleCallCounter.java and recursiveSum.java from your computer to send it to the instructor.

NOTE: Do NOT submit a .zip or a compressed file with all of your Java source code inside it. Please submit only Java source code files. Points will be taken away from your lab 1 score if you submit .zip or a compressed file.

LAB 1a: Towers of Hanoi Directions [ Towers.java ] 10 points.

Please write the Java solveTowers() method given in class. The method should be included inside a class named Towers and should have a public static void main() method. The main() method should be used to pass the values of the parameters needed to solveTowers(), and should end after the solveTowers() method has completed. You may use hardcoded values for the variables in main() that are passed as parameters to solveTowers(), or you may take user input for the values in main() that are passed as parameter to solveTowers().

Once you have your source code working, try running the program for values of the Towers of Hanoi game that has more than 5 disks. You should try running the program for at least five different numbers of disks. Watch carefully to determine how the recursive calls are being executed for each of the five different numbers of disks you choose.

LAB 1b: Triple Call Counter [ TripleCallCounter.java ] 15 points.

The following recursive equation:

T(n) = T(n - 1) + T(1) + T(n - 1)

with the following base case conditions:

T(0) = 0

T(1) = 1

has a programming solution that works very similar to the structure of the solveTowers() algorithm from 1a. It too has three recursive calls, and a base case that performs a single command when it is used.

The actual solution to this recursive equation is the found in the following way:

T(2) = T(2 - 1) + T(1) + T(2 - 1) = 1 + 1 + 1

T(3) = T(3 - 1) + T(1) + T(3 - 1) = T(2) + T(1) + T(2) = 3 + 1 + 3

T(4) = T(4 - 1) + T(1) + T(4 - 1) = T(3) + T(1) + T(3) = 7 + 1 + 7

T(5) = T(5 - 1) + T(1) + T(5 - 1) = T(4) + T(1) + T(4) = 15 + 1 + 15

.

.

.

Write a method called solveTripleCounter() that takes a single integer parameter that is greater than or equal to 0 and returns the value of the formula for T(n) using a recursive calling and programming logic structure like that used in 1a. solveTrippleCounter() should return an int value that is equal to the value of T(n). solveTripleCounter() should be included inside a class you provide named TripleCallCounter and should have a public static void main() method. The main() method should be used to pass the value of the parameter needed to solveTripleCounter(), and should end after the solveTripleCounter() once method has completed. Use hardcoded values for a single integer value used in main() that is passed as the parameter to solveTripleCounter().

As a part of the comments for solveTripleCounter() provide a comment that explains what the algebraic equation is for n. That is, write the regular, non-recursive, equation that shows how T(n) is related to the value of n. Hint: the equation has as a number raised to the power of n in it, and also a subtraction of a constant number in it.

LAB 1c: Recursive Sum [ recursiveSum.java ] 25 points.

Write a method called recursiveSum() that takes two non-negative integer parameters and recursively calculates their sum. You only need to write the method to calculate the sum of two integer values that are both greater than or equal to 0. recursiveSum() should be included inside a class you name RSum and should have a public static void main() method. The main() method should be used to pass the value of the parameter needed to recursiveSum(), and should end after the recursiveSum() once method has completed. Use hardcoded values for a single integer value used in main() that is passed as the parameter to recursiveSum().

Hint: In a way similar to taking the recursive formula for factorial:

0! = 1

1! = 1

n! = n * (n - 1)

and solving some small values of it such as:

factorial(0) = 0

factorial(1) = 1

factorial(3) = 3 * factorial(2) = 3 * 2! = 6

factorial(4) = 4 * factorial(3) = 4 * 6 = 24

factorial(5) = 5 * factorial(4) = 5 * 24 = 120

factorial(n) = n * factorial(n-1)

then writing the following method name, data type, and input parameter as the Java code:

public static int factorial(int n) {

// factorial code goes here

.

.

.

}

Determine what the sum would be for 0 + 0, 0 + 1, 1 + 0, and 1 + 1, then return the sum of each one of those as the most basic answer of the recursion. The recursive logic should follow a pattern much like this for the small values 4 and 2:

4 + 2 =

(3 + 1) + 2 =

((2 + 1) + 1) + 2 =

(((1 + 1) + 1) + 1) + 2 =

((2) + 1) + 1) + 2 =

((3) + 1) + 2 =

(4) + 2 =

6

Notice only one of the two numbers is recursively reduced to 1 + 1 and then has + 1 added to the recursive return value.