Java Reference
In-Depth Information
T
EST
Q
UESTIONS
P
ROGRAMMING
E
XERCISES
Sections 20.2-20.3
*20.1
(
Factorial
) Using the
BigInteger
class introduced in Section 10.14, you can
find the factorial for a large number (e.g.,
100!
). Implement the
factorial
method using recursion. Write a program that prompts the user to enter an inte-
ger and displays its factorial.
*20.2
(
Fibonacci numbers
) Rewrite the
fib
method in Listing 20.2 using iterations.
Hint
: To compute
fib(n)
without recursion, you need to obtain
fib(n - 2)
and
fib(n - 1)
first. Let
f0
and
f1
denote the two previous Fibonacci num-
bers. The current Fibonacci number would then be
f0 + f1
. The algorithm
can be described as follows:
f0 =
0
;
// For fib(0)
f1 =
1
;
// For fib(1)
for
(
int
i =
1
; i <= n; i++) {
currentFib = f0 + f1;
f0 = f1;
f1 = currentFib;
}
// After the loop, currentFib is fib(n)
Write a test program that prompts the user to enter an index and displays its
Fibonacci number.
*20.3
(
Compute greatest common divisor using recursion
) The
gcd(m, n)
can also
be defined recursively as follows:
■
If
m % n
is
0
,
gcd(m, n)
is
n
.
■
Otherwise,
gcd(m, n)
is
gcd(n, m % n)
.
Write a recursive method to find the GCD. Write a test program that prompts
the user to enter two integers and displays their GCD.
20.4
(
Sum series
) Write a recursive method to compute the following series:
1
2
+
1
3
+
1
i
m
(
i
)
=
1
+
. . .
+
Write a test program that displays
m(i)
for
i
,
2
, . . . ,
10
.
=
20.5
(
Sum series
) Write a recursive method to compute the following series:
1
3
+
2
5
+
3
7
+
4
9
+
5
11
+
6
13
+
i
m
(
i
)
=
. . .
+
2
i
+
1
Write a test program that displays
m(i)
for
i
,
2
, . . . ,
10
.
=
*20.6
(
Sum series
) Write a recursive method to compute the following series:
1
2
+
2
3
+
i
m
(
i
)
=
. . .
+
i
+
1
Write a test program that displays
m(i)
for
i
,
2
, . . . ,
10
.
=