21.7. Important Facts

[Page 638 ( continued )]

19.3. Example: Fibonacci Numbers

The factorial method in the preceding section could easily be rewritten without using recursion. In some cases, however, using recursion enables you to give a natural, straightforward, simple solution to a program that would otherwise be difficult to solve. Consider the well-known Fibonacci series problem, as follows :

The series:		1	1	2	3	5	8	13	21	34	55	89
indices:		1	2	3	4	5	6	7	8	9	10	11

The Fibonacci series begins with 0 and 1, and each subsequent number is the sum of the preceding two numbers in the series. The series can be recursively defined as follows:

 fib(0) = 0; fib(1) = 1; fib(index) = fib(index - 2) + fib(index - 1); index >= 2 

The Fibonacci series was named for Leonardo Fibonacci, a medieval mathematician , who originated it to model the growth of the rabbit population. It can be applied in numeric optimization and in various other areas.

---

[Page 639]

How do you find fib(index) for a given index ? It is easy to find fib(2) because you know fib(0) and fib(1) . Assuming that you know fib(index - 2) and fib(index - 1) , fib(index) can be obtained immediately. Thus, the problem of computing fib(index) is reduced to computing fib(index - 2) and fib(index - 1) . When computing fib(index - 2) and fib(index - 1) , you apply the idea recursively until index is reduced to or 1 .

The base case is index = 0 or index = 1 . If you call the method with index = 0 or index = 1 , it immediately returns the result. If you call the method with index >= 2 , it divides the problem into two subproblems for computing fib(index - 1) and fib(index - 2) using recursive calls. The recursive algorithm for computing fib(index) can be simply described as follows:

   if   (index ==     )   return 0   ;   else if   (index ==   1   )   return 1   ;   else     return   fib(index -   1   ) + fib(index -   2   ); 

Listing 19.2 gives a complete program that prompts the user to enter an index and computes the Fibonacci number for the index.

Listing 19.2. ComputeFibonacci.java

 1   import   javax.swing.JOptionPane;  2  3   public class   ComputeFibonacci {  4  /** Main method */  5   public static void   main(String args[]) {  6  // Read the index  7     String intString = JOptionPane.showInputDialog(  8   "Enter an index for the Fibonacci number:"   );  9 10  // Convert string into integer  11   int   index = Integer.parseInt(intString); 12 13  // Find and display the Fibonacci number  14     JOptionPane.showMessageDialog(   null   , 15   "Fibonacci number at index "   + index +   " is "   +  fib(index)  ); 16   } 17 18  /** The method for finding the Fibonacci number */  19   public static long    fib(   long   index)  { 20   if   (index ==   )  // Base case  21   return     ; 22   else if   (index ==  1  )  // Base case  23   return    1  ; 24   else    // Reduction and recursive calls  25   return    fib(index -   1   ) + fib(index -   2   )  ; 26   } 27 } 

The program does not show the considerable amount of work done behind the scenes by the computer. Figure 19.3, however, shows 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. The labels in Figure 19.3 show the order in which methods are called.

---

[Page 640]

Figure 19.3. Invoking fib(4) spawns recursive calls to fib .

As shown in Figure 19.3, there are many duplicated recursive calls. For instance, fib(2) is called twice, fib(1) is called three times, and fib(0) is called twice. In general, computing fib(index) requires twice as many recursive calls as are needed for computing fib(index - 1) . As you try larger index values, the number of calls substantially increases .

Besides the large number of recursive calls, the computer requires more time and space to run recursive methods.

Pedagogical Note

The recursive implementation of the fib method is very simple and straightforward, but not efficient. See Exercise 19.2 for an efficient solution using loops . The recursive fib method is a good example to demonstrate how to write recursive methods, though it is not practical.