Recursion - Multimedia Introduction to Programming Using Java - page 423

characters from a String . For example, removeDups("baaaccd") = "bacd" .
12. Write a recursive function that tells how many blanks a String has.
13. Write the following function; the recursive case should involve substring
s[1..] :
/** = the reverse of s. For example, srev("abc") is "cba" */
public static String rev(String s)

14. The previous exercise results in a function that has a recursive call that is not
tail-recursive. The way to make it more efficient is to add an extra parameter.
Write the following function, making sure that recursive calls are tail recursive:

/** = (the reverse of s ) +t */
public static String tailrev(String s, String t)

15. In the previous exercise, you wrote a function to reverse a String whose
only call is tail-recursive. Use the method of Sec. 15.3.4 to eliminate the tail-
recursive call from that function.

16. Write the following linear search procedure, using recursion (no loops):

/** Return the int i that satisfies
(0) x is not in b[0..i-1] and
(1) x = b[i] or i = b.length */
public static int linearSearch( int [] b, int x, int h)
17. This exercise asks you to implement the binary search algorithm of Sec.
8.5.3 recursively. Write the body of the following function:

/** = an integer i that satisfies b[h..i] ≤ x < b[i+1..k] */
public static int binarySearch( int [] b, int x, int h, int k)
18. A palindrome is a String that reads the same backward and forward. Write
the following function. The way to think about it is to understand that s is a
palindrome if its first and last characters are the same and the substring between
them is a palindrome. By definition, a string of length 0 or 1 is a palindrome.
/** = "s is a palindrome " */
public static boolean isPalindrome(String s)
18. Write a recursive function (no loops) to computer gcd(x, y) , where x>0
and y>0 . The gcd(x, y) is the greatest common divisor of x and y : the largest
integer that divides both of them. Your recursive function can use (only) these
properties of gcd:

Turn to lesson
page 15.3 for
an astonishing
palindrome.