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