CPSC 170 Lab 6: Recursion and Induction

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. A palindrome is a string that is the same forward and backward. In Chapter 3 you saw a program that uses a loop to determine whether a string is a palindrome. However, it is also easy to define a palindrome recursively as follows:
   • A string containing fewer than 2 letters is always a palindrome.
   • A string containing 2 or more letters is a palindrome if
     • its first and last letters are the same, and
     • the rest of the string (without the first and last letters) is also a palindrome.

   Write a program that prompts for and reads in a string, then prints a message saying whether it is a palindrome. Your main method should read the string and call a recursive (static) method palindrome that takes a string and returns true if the string is a palindrome, false otherwise.

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 palindrome program and BaseConvert.java. Tar your directory and email to me with cpsc170 lab6 in the Subject line.

Mathematical Induction

1. 1 + 5 + ... + 4n-3 = n(2n-1)

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

2. Any amount of postage greater than or equal to 12 cents can be built using only 4 and 5 cent stamps.