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

18.5 Example Using Recursion: Fibonacci Series
The Fibonacci series ,

0, 1, 1, 2, 3, 5, 8, 13, 21, …

begins with 0 and 1 and has the property that each subsequent Fibonacci number is the
sum of the previous two. This series occurs in nature and describes a form of spiral. The
ratio of successive Fibonacci numbers converges on a constant value of 1.618…, a number
that has been called the golden ratio or the golden mean. Humans tend to find the golden
mean aesthetically pleasing. Architects often design windows, rooms and buildings whose
length and width are in the ratio of the golden mean. Postcards are often designed with a
golden-mean length-to-width ratio.
The Fibonacci series may be defined recursively as follows:

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci( n ) = fibonacci( n - 1) + fibonacci( n - 2)

There are two base cases for the Fibonacci calculation: fibonacci(0) is defined to be 0, and
fibonacci(1) to be 1. The program in Fig. 18.5 calculates the i th Fibonacci number re-
cursively, using method fibonacci (lines 10-18). Method main (lines 21-26) tests fibo-
nacci , displaying the Fibonacci values of 0-40. The variable counter created in the for
header (line 23) indicates which Fibonacci number to calculate for each iteration of the
loop. Fibonacci numbers tend to become large quickly (though not as quickly as factori-
als). Therefore, we use type BigInteger as the parameter type and the return type of meth-
od fibonacci .

1 // Fig. 18.5: FibonacciCalculator.java

2 // Recursive fibonacci method.

3 import java.math.BigInteger;

4
5 public class FibonacciCalculator

6 {

7 private static BigInteger TWO = BigInteger.valueOf( 2 );

8
9 // recursive declaration of method fibonacci

public static BigInteger fibonacci(BigInteger number)
{
if (number.equals( BigInteger.ZERO ) ||
number.equals( BigInteger.ONE )) // base cases
return number;
else // recursion step
return fibonacci(number.subtract( BigInteger.ONE )).add(
fibonacci(number.subtract( TWO )));
}

10

11

12

13

14

15

16

17

18

19
20 // displays the fibonacci values from 0-40

21 public static void main(String[] args)

22 {

Fig. 18.5 | Recursive fibonacci method. (Part 1 of 2.)