In some cases, recursion enables you to create an intuitive, straightforward, simple solution to a problem. The **factorial** method in the preceding section could easily be rewritten without using recursion. In this section, we show an example for creating an intuitive solution to a problem using recursion. Consider the well-known Fibonacci-series problem:

The Fibonacci series begins with **0** and **1**, and each subsequent number is the sum of the preceding 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 optimization 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);

The code below gives a complete program that prompts the user to enter an index and computes the Fibonacci number for that index.

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

As shown in Figure above, 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 below.

The recursive implementation of the **fib** method is very simple and straightforward, but it isn’t efficient, since it requires more time and memory to run recursive methods. Though it is not practical, the recursive **fib** method is a good example of how to write recursive methods.

## Top comments (0)