CPSC 170 Lab 7: Introduction to Recursion

1. Computing a positive integer power of a number is easily seen as a recursive process:

   x0 = 1
   xy = x*xy-1  for all y > 1
   

   File Power.java contains a main program that reads in integers base and exp and calls method power to compute base^exp. Fill in the code for power to make it a recursive method to do the power computation.

   Print Power.java.

2. The Fibonacci sequence is a well-known mathematical sequence in which each term is the sum of the two previous terms. More specifically, if fib(n) is the nth term of the sequence, then the sequence can be defined as follows:

       fib(0) = 0
       fib(1) = 1
       fib(n) = fib(n-1) + fib(n-2)  n>1
   

   For example, the first eight elements of the sequence are 0,1,1,2,3,5,8,13.

   Because the Fibonacci sequence is defined recursively, it is natural to write a recursive method to determine the nth number in the sequence. File Fib.java contains the skeleton for a program that reads an integer n from and computes and prints the n^th Fibonacci number. Save this file to your directory. Following the specification above, fill in the code for method fib so that it recursively computes and returns the nth number in the sequence.

   Print Fib.java.

3. Printing a string backwards can be done iteratively or recursively. To do it recursively, think of the following specification:

   If s contains any characters (i.e., is not the empty string)

   • print the last character in s
   • print s' backwards, where s' is s without its last character

   File Backwards.java contains a program that prompts the user for a string, then calls method printBackwards to print the string backwards. Save this file to your directory and fill in the code for printBackwards using the recursive strategy outlined above. Recall that for a String s in Java,

   • s.length() returns the number of charaters in s
   • s.charAt(i) returns the i^th character of s, 0-based
   • s.substring(i,j) returns the substring that starts with the i^th character of s and ends with the j-1^st character of s (not the j^th!), both 0-based.
   So if s="happy", s.length=5, s.charAt(1)=a, and s.substring(2,4) = "pp".

   Print Backwards.java.

4. The GCD is the largest integer that divides both values without producing a remainder. The following block of code implements Euclid's algorithm for finding the greatest common divisor (GCD) of two positive integers.

   	public static int gcd (int num1, int num2)
   	{
   		int c;
   		while (num2!=0) 
   		{
   			c=num2;
   			num2=num1%num2;
   			num1=c;
   		}
   		return num1;
   	}
   
   

   Study this code and perform a couple of hand traces to figure out how it works. Create a class called DivisorCalc that implements a recursive version of the gcd method and a driver program to test your implementation. Remember the steps in recursive method design.

   What is the base case?

   What is the recursive step?

5. One algorithm for converting a base 10 number to base b involves repeated division by the base b. Initially one divides the number by b. The remainder from this division is the units digit (the rightmost digit) in the base b representation of the number (it is the part of the number that contains no powers of b). The quotient is then divided by b on the next iteration. The remainder from this division gives the next base b digit from the right. The quotient from this division is used in the next iteration. The algorithm stops when the quotient is 0. Note that at each iteration the remainder from the division is the next base b digit from the right -- that is, this algorithm finds the digits for the base b number in reverse order.

   Here is an example for converting 30₁₀ to base 4:

                         quotient       remainder
                         --------       ---------
            30/4 =           7              2
   	 7/4  =           1              3
   	 1/4  =           0              1
   
   

   The answer is read bottom to top in the remainder column, so 30₁₀ = 132₄.

   Think about how this is recursive in nature: If you want to convert x (30 in our example) to base b (4 in our example), the rightmost digit is the remainder x % b. To get the rest of the digits, you perform the same process on what is left; that is, you convert the quotient x / b to base b. If x / b is 0, there is no rest; x is a single base b digit and that digit is x % b (which also is just x).

   The file BaseConversion.java contains the shell of a method convert to do the base conversion and a main method to test the conversion. Note that the convert method returns a string representing the base b number. This means that in the base case, when the remainder is what is to be returned, it must be converted to a String object by concatenating it with a null string. Similarly, in the recursive case the result of the recursive call will be concatenated with the remainder.

   Fill in the code for convert and the call in the main method. Here is some data to test your program on:

   • 89₁₀ = 1011001₂
   • 347₁₀ = 2342₅
   • 3289₁₀ = 6331₈

   Print BaseConversion.java.

HAND IN:

• Turn in hardcopy of Power.java, Fib.java, Backwards.java, your gcd program and driver, and BaseConvert.java. Tar your directory and email to me with cpsc170 lab7 in the Subject line.