Java Reference
In-Depth Information
20
else if
(index ==
1
)
// Base case
base case
21
return
1
;
22
else
// Reduction and recursive calls
fib(index -
1
) + fib(index -
2
)
23
return
;
recursion
24 }
25 }
Enter an index for a Fibonacci number:
The Fibonacci number at index 1 is 1
1
Enter an index for a Fibonacci number:
The Fibonacci number at index 6 is 8
6
7
Enter an index for a Fibonacci number:
The Fibonacci number at index 7 is 13
The program does not show the considerable amount of work done behind the scenes by the
computer. Figure 20.4, however, shows the successive recursive calls for evaluating
fib(4)
.
The original method,
fib(4)
, makes two recursive calls,
fib(3)
and
fib(2)
, and then
returns
fib(3) + fib(2)
. But in what order are these methods called? In Java, operands are
evaluated from left to right, so
fib(2)
is called after
fib(3)
is completely evaluated. The
labels in Figure 20.4 show the order in which the methods are called.
fib(4)
0: call
fib(4)
17: return
fib(4)
return
fib(3)
+
fib(2)
10: return
fib(3)
11: call
fib(2)
16: return
fib(2)
1: call
fib(3)
return
fib(2)
+
fib(1)
return
fib(1)
+
fib(0)
7: return
fib(2)
14: return
fib(0)
8: call
fib(1)
13: return
fib(1)
2: call
fib(2)
12: call
fib(1)
15: return
fib(0)
9: return
fib(1)
return
fib(1)
+
fib(0)
return 1
return 0
return 1
4: return
fib(1)
5: call
fib(0)
3: call
fib(1)
6: return
fib(0)
return 1
return 0
F
IGURE
20.4
Invoking
fib(4)
spawns recursive calls to
fib
.
As shown in Figure 20.4, there are many duplicated recursive calls. For instance,
fib(2)
is called twice,
fib(1)
three times, and
fib(0)
twice. In general, computing
fib(index)
requires roughly twice as many recursive calls as does computing
fib(index - 1)
. As you
try larger index values, the number of calls substantially increases, as shown in Table 20.1.
T
ABLE
20.1
Number of Recursive Calls in
fib(index)
index
2
3
4
10
20
30
40
50
# of calls
3
5
9
177
21891
2,692,537 331,160,281
2,075,316,483
