CPSC 211
Recursion

Objectives

• to understand the concept of recursion
• to know how to read a recursive method
• to know how to implement and debug a recursive method

Part 1

In this part of the lab we're going to warm up by tracing an existing recursive method and then modify it to do slightly different tasks. Begin by tracing the following recursive method (you can use a recursion tree or droids to do this) in order to determine the output to the screen when the call PrintUtil.print( 5702 ) is made:

public class PrintUtil {

     public static void print( int num ) {
          if( num > 0 ) {
               System.out.println( num % 10 );
          		print( num / 10 );
          }
     }
}

5
7
0
2

Now write a PrintUtilDriver class - (i.e., a fairly simple driver program with a main method) that you can use to test that your method works correctly.

Now add to the PrintUtil class a recursive public static method printBackwardsForwards that takes an integer as input and prints the digits in that integer both backwards and forwards, one digit per line. So, for example, the call printBackwardsForwards(5702) should generate the following output:

2
0
7
5
7
0
2

Note that the first digit in the number (5 in this case) is printed only once!

Modify your driver program to test the method printBackwardsForwards.

Part 2

In this part of the lab, you will write a recursive method of the Domino class to output all pair-numbers of a set of dominos where the maximumNumberOfDots on a domino is user specified. Recall that a domino is a rectangle whose face is divided into two equal parts that are blank or bear from one to six dots (assuming the maximumNumberOfDots is 6 in this case). A set of dominos usually contains 28 dominos; that is, all the possible pair-combinations of the numbers from 0 to 6 with no repetition. This means that the pairs (1, 6) and (6, 1), for example, are not distinguished and the set contains only one of them. The header of the domino method is as follows:

public static void printDominoSet( int dotsOnLeftSide, int dotsOnRightSide ) { ... }

For example, the call Domino.printDominoSet( 4, 4 ); should produce the following output:

4 : 4
4 : 3
4 : 2
4 : 1
4 : 0
3 : 3
3 : 2
3 : 1
3 : 0
2 : 2
2 : 1
2 : 0
1 : 1
1 : 0
0 : 0

• Hints:
• The initial call to your recursive method is printDominoSet( maximumNumberOfDots, maximumNumberOfDots ); that is, you start with the domino having the maximum number of dots on both sides.
• Use both parameters to distinguish the different cases.
• Decide what the values of these parameters should be when you want to stop printing (i.e. determine the "base case" of your recursive method).
• Decide whether you need to change one or both parameter values in the recursive call and how you get closer to your base case. Accordingly, decide how many recursive branches you will have in the corresponding recursion tree.
  
• Write a DominoDriver class - (i.e., a fairly simple driver program with a main method) that you can use to test your printDominoSet method. The driver should prompt the user for the maximum number of dots on the domino.

Part 3

In the last part of the lab, you will write a recursive method to sort a list using MergeSort. Given an list to sort, MergeSort will:

• Divide the list into two smaller sublists
• Recursively call itself to sort the sublists, and then
• Merge the partial solutions to obtain the sorted list.
• The base case for this algorithm is when the list is already sorted. (When do you know the list is sorted?).

Your assignment is to implement a mergeSort method which takes a List of integers and returns a new ArrayList with the integers, sorted in ascending order.

• The first part of this assignment is to implement the merge method which takes a result list and two sorted lists (slist1 and slist2) and adds the elements of slist1 and slist2, in order, to the result list. This should be written recursively. The header for this should be:
  public static void merge(List<Integer> result, List<Integer> slist1, List<Integer> slist2)
• The second part is to use the merge method to implement the mergeSort method. The header for this should be:
  public static List<Integer> mergeSort(List<Integer> lst)

You must test your code.

Extension: modify your methods to allow it to sort any object that extends the Comparable interface.

Here is an example which shows how the merge sort works:

input: 8,6,4,1,9,2,3,7,5
{8,6,4,1,9},              {2,3,7,5}
{8,6,4},    {1,9},        {2,3},    {7,5}
{8,6},{4},  {1},{9},      {2},{3},  {7},{5}
{8},{6}
Now we step backward merging the sorted lists:
{6,8},{4},  {1},{9},      {2},{3},  {7},{5}
{4,6,8},    {1,9},        {2,3},    {5,7}
{1,4,6,8,9},              {2,3,5,7}
{1,2,3,4,5,6,7,8,9}