RECURSION - Introduction to Java Programming: Comprehensive Version - page 710

The series: 0 1 1 2 3 5 8 13 21 34 55 89 …

indexes: 0 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 pre-
ceding two. The series can be recursively defined as:

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 opti-
mization and in various other areas.
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) ,
you can obtain fib(index) immediately. Thus, the problem of computing fib(index) is
reduced to computing fib(index - 2) and fib(index - 1) . When doing so, you apply
the idea recursively until index is reduced to 0 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 == 0 )
return 0 ;
else if (index == 1 )
return 1 ;
else
return fib(index - 1 ) + fib(index - 2 );

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

L ISTING 18.2

ComputeFibonacci.java
1 import java.util.Scanner;
2
3 public class ComputeFibonacci {
4 /** Main method */
5 public static void main(String[] args) {
6 // Create a Scanner
7 Scanner input = new Scanner(System.in);
8 System.out.print( "Enter an index for a Fibonacci number: " );
9

int index = input.nextInt();

10
11 // Find and display the Fibonacci number
12 System.out.println( "The Fibonacci number at index "
13 + index + " is " + fib(index));
14 }
15
16

/** The method for finding the Fibonacci number */

17 public static long fib( long index) {

18 if (index == 0 ) // Base case base case

19 return 0 ;