Case Study: Computing Fibonacci Numbers
Tags: java, programming, learning, beginners
Published: 2024-07-02 19:11:18

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:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cjpl5kv8wg1nxrjwrpcf.png)

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dx0o3mb88lb6vk9uspyg.png)

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/56s6vu973rxfinfgibt7.png)

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lq6cx3w0tyvrpupybi0a.png)

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.