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
/** = 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