Recursion - Java: How to Program Early Objects - page 785

fibonacci( 3 )

return fibonacci( 2 ) + fibonacci( 1 )

return fibonacci( 1 ) + fibonacci( 0 ) return 1

return 1 return 0

Fig. 18.6 | Set of recursive calls for fibonacci (3).

made? The Java language specifies that the order of evaluation of the operands is from left to
right. Thus, the call fibonacci(2) is made first and the call fibonacci(1) second.
A word of caution is in order about recursive programs like the one we use here to
generate Fibonacci numbers. Each invocation of the fibonacci method that does not
match one of the base cases (0 or 1) results in two more recursive calls to the fibonacci
method. Hence, this set of recursive calls rapidly gets out of hand. Calculating the Fibo-
nacci value of 20 with the program in Fig. 18.5 requires 21,891 calls to the fibonacci
method; calculating the Fibonacci value of 30 requires 2,692,537 calls! As you try to cal-
culate larger Fibonacci values, you'll notice that each consecutive Fibonacci number you
use the application to calculate results in a substantial increase in calculation time and in
the number of calls to the fibonacci method. For example, the Fibonacci value of 31
requires 4,356,617 calls, and the Fibonacci value of 32 requires 7,049,155 calls! As you
can see, the number of calls to fibonacci increases quickly—1,664,080 additional calls
between Fibonacci values of 30 and 31 and 2,692,538 additional calls between Fibonacci
values of 31 and 32! The difference in the number of calls made between Fibonacci values
of 31 and 32 is more than 1.5 times the difference in the number of calls for Fibonacci
values between 30 and 31. Problems of this nature can humble even the world's most pow-
erful computers. [ Note: In the field of complexity theory, computer scientists study how
hard algorithms work to complete their tasks. Complexity issues are discussed in detail in
the upper-level computer science curriculum course generally called “Algorithms.” We
introduce various complexity issues in Chapter 19, Searching, Sorting and Big O.] In this
chapter's exercises, you'll be asked to enhance the Fibonacci program of Fig. 18.5 so that
it calculates the approximate amount of time required to perform the calculation. For this
purpose, you'll call static System method currentTimeMillis , which takes no argu-
ments and returns the computer's current time in milliseconds.

Performance Tip 18.1
Avoid Fibonacci-style recursive programs, because they result in an exponential “explo-
sion” of method calls.