Java Reference

In-Depth Information

Exercises for Chapter 15

1. (a)

Define
descendent
recursively.

(b)

Define the format of binary integers (sequences of
0
s and
1
s) recur-

sively.

(c)

Define the format of Java identifiers recursively.

(d)

Define a list of integers separated by commas recursively.

2.
Write a recursive definition for the product
x*y
of two integers
x
and
y
,

where
y≥0
.

3.
Write a recursive definition for exponentiation
x
y
of two integers
x
and
y
,

where
y≥0
.

4.
Write a recursive function to sum the values in a range. With the specification

given for it, the values have to be summed from largest to smallest.

/** =
sum of integers in the range
0..n
, for
n ≥ -1 */

public static int
sum(
int
n)

5.
The function of the previous exercise has a recursive call that is not tail-recur-

sive. The way to change the function so that it will be tail-recursive is to add a

parameter. Write the following function so that the recursive call is tail recursive.

/** = x + (
sum of integers in the range
0..n)
, for
n ≥ -1 */

public static int
sum(
int
x,
int
n)

6.
Rewrite the function of the previous exercise to eliminate the tail-recursive

call using the technique of Sec. 15.3.4.

7.
Implement the inefficient function to calculate Fibonacci numbers (see Sec.

15.2.3) and calculate some Fibonacci numbers to see how long it takes. Try calls

like
Fib(10)
,
Fib(20)
,
Fib(30)
, ... until you get some sense of how inefficient

this function is.

8.
Function
fib
of the previous exercise is extremely inefficient, requiring time

proportional to
F
n
to calculate
fib(n)
. The way to get a more efficient function

is to add parameters to the function, as illustrated below. Write the function body.

Make sure that any recursive calls are tail recursive.

/** = F
n
, for
0<n
, given that
1≤k≤n,a=F
k
, and
b=F
k-1
*/

public static int
FibLinear(
int
n,
int
k,
int
a,
int
b)

9.
In Exercise 8, you wrote a function whose only call is tail recursive. Use the

method of Sec. 15.3.4 to eliminate the tail-recursion from that function.

10.
Write a recursive boolean function that tells whether a
String
contains a

blank.

11.

Write a recursive function
removeDups
that removes duplicate adjacent

Search WWH ::

Custom Search