Module [304] - Recursive Methods

Study Material
Apprenticeship
Problets [optional]
JavaBat
Homework

This module will focus on a design technique that you will explore further again in later courses. We are going to discuss recursive methods, i.e. methods that, when faced with solving a problem of size N, call themselves on smaller subsets of that problem, then collect the partial results and return them.

Textbook Reading Assignments
The following sections of the textbook are assigned for this module.
- Chapter #18 – Recursion

It is important to note that this module appears way later in our textbook. As a result, the author occasionally references some concepts that we will cover in our last module regarding objects and classes. Similarly, some of the exercises assume that you have already played with JavaFX to build some graphic user interfaces. We will avoid these exercises for now since that material will be covered in COP2513 Object Oriented Programming for IT.

Module Learning Outcomes

In this module, you will develop further your programming skills as follows;

Tracing: Ability to read and trace Java programs leveraging recursive methods.
Implementing: Ability to write Java programs leveraging recursive methods.
Testing: Ability to develop tests for Java programs leveraging recursive methods.
Debugging: Ability to troubleshoot Java programs leveraging recursive methods.
Designing: Ability to design Java programs leveraging recursive methods.

A01 - Iterative Fibonnachi
Video Link: YouTube
This exercise is #18.2 in the 11th & 10th editions of our text.
Rewrite the fib method in Listing 18.2 using iterations. Here is the algorithm to help you do so;
```
f0 = 0; // For fib(0)
f1 = 1; // For fib(1)
 
for (int i = 1; i <= n; i++) {
  currentFib = f0 + f1;
  f0 = f1;
  f1 = currentFib;
}
// After the loop, currentFib is fib(n) 
```
Write a test program that prompts the user to enter an index and displays its Fibonacci number.

A02 - Summing Series
Video Link: YouTube
This exercise is #18.4 in the 11th & 10th editions of our text.
Write a recursive method to compute the following series:
```
m(i)=1+ (1/2) + (2/3) + ... + (i/(i+1))
```
Write a test program that displays m(i) for i = 1, 2, ..., 10.

A03 - Inverse the Digits of an Integer
Video Link: YouTube
This exercise is #18.8 in the 11th & 10th editions of our text.
Write a recursive method that displays an int value reversely on the console using the following header;
```
	  public static void reverseDisplay(int value)
```
For example, reverseDisplay(12345) will display 54321. Write a test program that prompts the user to enter an integer and displays its reversal.

A04 - Counting upper-cases in a String
Video Link: YouTube
This exercise is #18.14 in the 11th & 10th editions of our text.
Write a recursive method to return the number of uppercase letters in a string. Write a test program that prompts the user to enter a string and displays the number of uppercase letters in the string.

A05 - Counting upper-cases in an array
Video Link: YouTube
This exercise is #18.16 in the 11th & 10th editions of our text.
Write a recursive method to return the number of uppercase letters in an array of characters. You need to define the following two methods;
```
public static int count(char[] chars)
public static int count(char[] chars, int high)
```
The second one is a recursive helper method. Write a test program that prompts the user to enter a list of characters in one line and displays the number of uppercase letters in the list.

IMPORTANT NOTE:

This week, we have both Problets and Codingbat / Javabat assigned as part of your practice. However, you will automatically get credit for the Problets practice.
As a result, you will not have to upload any screenshots for Problets for this module, yet will receive full points for the question prompting you to do so.
Please note that the Javabat / Codingbat exercises are still due! Do not skip these.
The links below are only provided so that, if you need help from a Problet tutor, you will find it readily available. If you need more time to work through the Javabat / Codingbat exercise, you will have the flexibility to do so.

Each of the following links will lead you to a separate tutor applet. The tutors take usually 30 minutes to work through.

Problet #1 - Functions - Recursive Functions
URL Link: See Instructor Announcements
This Problet tutor will allow you to understand how Java recursive methods work

The following exercises are from the Recursion-1 group from the JavaBat website. These are introductory exercises on recursion that will help you understand the fundamentals of this design strategy.

JB1 - Bunny Ears
URL Link: bunnyEars
We have a number of bunnies and each bunny has two big floppy ears. We want to compute the total number of ears across all the bunnies recursively (without loops or multiplication).

JB2 - Bunny Ears, the Sequel
URL Link: bunnyEars2
We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3, ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3 ears, because they each have a raised foot. Recursively return the number of "ears" in the bunny line 1, 2, ... n (without loops or multiplication).

JB3 - Nested Parentheses
URL Link: nestParen
Given a string, return true if it is a nesting of zero or more pairs of parenthesis, like "(())" or "((()))". Suggestion: check the first and last chars, and then recur on what's inside them.

JB4 - Recursive sub strings
URL Link: strCopies
Given a string and a non-empty substring sub, compute recursively if at least n copies of sub appear in the string somewhere, possibly with overlapping. N will be non-negative.

IMPORTANT NOTE:

Some of the homework exercises below are marked as [optionals]; You do not have to complete these in order to get full participation credit for the HW assignment corresponding to this module.
More specifically, when the TAs select the exercise to upload, they will NOT select any of the optional ones. However, all non-optional exercises are fair game so you should complete them.

B01 - Factorials that are too Big to fail [OPTIONAL]
This exercise is #18.1 in the 11th edition of our text.
Rewrite a recursive program to compute the factorial of an integer value, but, this time, use the BigInteger class to do so. Use your program to compute the factorial of a large number, e.g. 100, entered by the user.

B02 - Greater Common Divisor
This exercise is #18.3 in the 11th & 10th editions of our text.
The gcd(m, n) can also be defined recursively as follows:
- If m % n is 0 , gcd(m, n) is n
- Otherwise, gcd(m, n) is gcd(n, m % n)
Write a recursive method to find the GCD. Write a test program that prompts the user to enter two integers and displays their GCD.

B03 - Recursive Reversing
This exercise is #18.9 in the 11th & 10th editions of our text.
Write a recursive method that displays a string reversely on the console. For example, using reverseDisplay("abcd") will display dcba in the console. Write a test program that prompts the user to enter a string and displays it, reversed.

B04 - Highest from Array
This exercise is #18.13 in the 11th & 10th editions of our text.
Write a recursive method that returns the largest integer in an array. Write a test program that prompts the user to enter a list of eight integers and displays the largest element.

B05 - Occurences of a given character in an array
This exercise is #18.17 in the 11th & 10th editions of our text.
Write a recursive method that finds the number of occurrences of a specified character in an array. To do so, use the following two methods;
```
public static int count(char[] chars, char ch)
public static int count(char[] chars, char ch, int high)
```
The second one is a recursive helper method. You will also write a test program that prompts the user to enter a list of characters in one line, then another character. It will display the number of occurrences of the character in the list.

B06 - Strings Permutations
This exercise is #18.25 in the 11th & 10th editions of our text.
Write a recursive method to print all the permutations of a string. For example, for the string abc, the permuations are;
```
abc
acb
bac
bca
cab
cba
```
You should define the following two methods.
```
public static void displayPermutation(String s)
public static void displayPermutation(String s1, String s2)
```
The first method simply invokes displayPermutation(" ", s). The second method is a helper method that uses a loop to move a character from s2 to s1 and recursively invokes it with a new s1 and s2. The base case is that s2 is empty, it results in printing s1 to the console. Write a test program that prompts the user to enter a string and displays all its permutations.