Java Reference

In-Depth Information

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.

Search WWH ::

Custom Search