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 methodprintBackwardsForwards.

Part 2

Recall the following  print method in the PrintUtil class from the previous question:

	public class PrintUtil {

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

             
}

Write the same method using iteration instead of recursion.  This type of methods are called tail-recursive methods because the recursive call is the last statement executed by the recursive step of that method.  Can you think of a systematic way of translating tail-recursive methods to iterative methods?

Part 3

In the last 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:

• 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.
• 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.
  

Practice Section Only (not for marks)

Practice Part 1

	public int fib( int n ) { 

		if( n == 1 || n == 2 ) 

			return 1; 

		else 

			return fib( n – 1 ) + fib( n – 2 ); 

	}

This function is not tail-recursive as the first recursive call is not the last statement that is executed before the function calls itself.  We still can define this method iteratively, but we need to think harder to do so. Your task in this part is to find an iterative definition for this function.

Practice Part 2

Initially there are 3 pegs, call them peg1, peg2, peg3,  and n disks of different size stacked in decreasing size (smaller at the top)  on one of the begs, say peg1. The goal of the game is to move all  the discs (the tower)  from peg1 to peg3 (using peg 2), moving one disk at a time, with the following restriction: a disk may never be placed on a disk that is smaller than itself.

The following site has a nice animation of the problem:

http://www.mazeworks.com/hanoi/index.htm

Try a few times the  animation with a different number of disks and speeds. Then define a function that if you give it the 3 pegs and the number of disks stored in the first peg, will print out the moves you need to make to move all the disks to peg 3.

When you're done, find a solution to this problem on the Internet and compare your code with it.

Practice Part 3

In this part of the lab you are to write a program that prompts the user for the number of rows in Pascal's triangle, and prints the triangle on the screen. One of the uses of Pascal's triangle is to determine the coefficients in the polynomial (a + b)ⁿ. The first few rows of Pascal's triangle are as follows:

                 1 - row 0
               1     1 - row 1
            1     2     1 - row 2
         1     3     3     1 - row 3
      1     4     6     4     1 - row 4
   1     5    10    10     5     1 - row 5

Now note that:

( a + b )³ = 1a³ + 3a²b + 3ab² + 1b³    - underlined coefficients match the numbers on row 3 of the triangle

( a + b )⁴ = 1a⁴ + 4a³b + 6a²b² + 4ab³ + 1b⁴    - underlined coefficients match the numbers on row 4 of the triangle

( a + b )⁵ = 1a⁵ + 5a⁴b + 10a³b² + 10a²b³ + 5ab⁴ + 1b⁵    - underlined coefficients match the numbers on row 5 of the triangle

The entries in Pascal's triangle can be generated by adding together the 2 adjacent numbers in the previous row and noting that the first and last numbers on each row are always 1. So, if we were to add a row to the triangle above, the first entry would be 1, the next entry is obtained by adding the 1 and 5 in the previous row to get 6, the one after that is obtained by adding the 5 and 10 to get 15, etc. The next row would therefore be:

1     6    15    20    15     6     1

The entries in the triangle can therefore be defined quite elegantly using the following recursive function:

		1,					if r = 0 or if r = n
C( n, r ) =
		C( n - 1, r - 1 ) + C( n - 1, r ),	if 0 < r < n

where C( n, r ) is the entry on the nth row in the rth position (where the first row is row 0 and the first position is position 0 ). So, for example, the 6 on row 4 can be generated by evaluating C( 4, 2 ) because the 6 sits on row 4 in position number 2. Similarly, the second 10 on row 5 can be generated by evaluating C( 5, 3 ) because the second 10 sits on row 5 in position number 3.

Part 3a

• Write a recursive public static method choose of a class named MathUtil to compute C( n, r ) as described above. Your method takes two integers, n and r, as input and returns C( n , r ).
  
• Write a MathUtilDriver class - (i.e., a fairly simple driver program with a main method) that you can use to test that your method works correctly.

Part 3b

• Add a public static method drawPascal to the MathUtil class that prints the first n rows of Pascal's triangle. Your method takes one integer, nRows, as input and prints that many rows of Pascal's triangle on the screen. Do not use recursion when writing this method - use a for or a while loop as necessary. When your method is written, the calldrawPascal(4) should generate the following output on the screen:
  
               1
           1    1
        1    2    1
     1    3    3    1
  
  Note that rows 0 through 3 have been drawn, for a total of 4 rows. Here are some hints:
  • With the exception of the leading 1 in each row, all numbers are printed in a field of width 6. The leading 1 is also printed in a field but the width of the field varies from row to row - you must figure out the pattern.
    • Probably the easiest way to output data in a field of a certain width is to make use of the System.out.printf(...) method. If you already know C, this method works very similarly to the printf method in C. The following call, for example, outputs the value of the variable data (assumed to be of type int) in a field of width 4:
              System.out.printf( "%4d", data );
      
• Remember that each number in the triangle can be generated by making an appropriate call to the function that computes C( n, r ). So, for example, the number in the first row (row 0) and first position (position 0) can be generated by computing C( 0, 0 ). Similarly, the number in the second row (row 1) and third position (position 2) can be generated by computing C( 1, 2 ).
  
• Modify your driver program to include a test for your drawPascal method.