Java Reference
In-Depth Information
Consider the case
y>0
. If
y
is even, then
x
y
equals
(x * x)
y/2
. For exam-
ple, instead of multiplying six
4
s together, one can multiply three (
4*4
)s. Thus,
if
y
is even, we can use a recursive call to compute
(x * x)
y/2
:
See lesson page
15.3 to get this
function from
the CD.
if
(y % 2 == 0) {
return
exp(x * x, y / 2); }
If
y
is odd, we can compute
x
y
as
x*x
y-1
, using a recursive call:
if
(y % 2 == 1) {
return
x * exp(x, y - 1); }
The function appears in Fig. 15.6. Like the previous iterative version devel-
oped in Sec. 7.3.2, it requires time proportional to
log y
.
15.2.3
Computing Fibonacci numbers
The Fibonacci sequence
0
,
1
,
1
,
2
,
3
,
5
,
8
,
13
,
…
is defined by
F
0
=0
,
F
1
=1
, and
F
n
=F
n-1
+F
n-2
for
n>1
. Each value in the sequence, except the first and sec-
ond, is the sum of the two preceding values. It is easy to write a recursive func-
tion that calculates one of these numbers:
/** = F
n
, for
n >= 0 */
public static int
Fib(
int
n) {
if
(n <= 1)
{
return
n; }
return
Fib(n - 1) + Fib(n - 2);
}
The difficulty with this function is that it is extremely slow. To see this, start
drawing the tree of parameters of all recursive calls:
n
n-1
n-2
n-2
n-3
n-3
n-4
/** = x
y
. Precondition:
y≥0 */
public static int
exp(
int
x,
int
y) {
if
(y == 0)
{
return
1 }
if
(y%2==0)
{
return
exp(x * x, y / 2); }
return
x * exp(x, y - 1);
}
Figure 15.6:
Function
exp
Search WWH ::
Custom Search