CPSC 170 Lab 7: Recurrence Relations and More Recursion

Pencil-and-Paper Problems

1. T(1) = 2
   T(n) = 2n + 2*T(n-1)  n >= 2
   

2. S(1) = 1
   S(n) = 1 + 2*S(n/2)  n >= 2
   Hint: Recall that 20 +21 + ... +2n = 2n+1-1.
   

More Recursion

3. The greatest common divisor (gcd) of two positive integers is the largest integer that divides both integers evenly. For example:

   gcd(9,3) = 3
   gcd(3,7) = 1
   gcd(16,24) = 8
   

   Call the two integers m and n; let m be the smaller and n the larger. If m divides n evenly, then clearly gcd(m,n) = m. Otherwise, Euclid's algorithm says that gcd(m,n) is the gcd of m and the remainder when n is divided by m.

   Write a program that prompts for and reads in two positive integers and prints their gcd. Your main method should read in the integers and call a recursive method gcd that takes two integers and uses Euclid's algorithm to find and return the gcd, which will then be printed by the main method. Note that the gcd method will have to be static.

4. A palindrome is a string that is the same forward and backward. 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 method palindrome that takes a string and returns true if the string is a palindrome, false otherwise.

   To write the palindrome method you'll have to think of the palindrome specification recursively. Here's a start:

   • In what case(s) is a string always a palindrome?
   • In all other cases, a string is a palindrome if
     • it has what immediately checkable property, and
     • what substring is also a palindrome?

   You will need to do some string manipulations in this program. 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.

HAND IN:

• Hand in your solutions to 1 and 2 and hardcopy of your GCD and Palindrome files.
• Tar the files in your lab7 directory and email the .tgz file to me (bloss@cs.roanoke.edu).