Nth Fibonacci number using Java Recursion

There are certain problems that just make sense to solve using Java Recursion. Demonstrating Fibonacci Series is one of them. Let’s take a look at something called Fibonacci series. Here are the first few numbers of this series:
0, 1, 1, 2, 3, 5, 8, 13, 21…

     Now stop reading and try to figure out what’s going on or let’s walk thru the sequence together and see how it works:

To obtain the sequence, we start with 0 and 1 after which every number is the sum of the previous two numbers. 

For example, the first two numbers will be 0 and 1

0, 1

For the next number, we add the previous two numbers 0 and 1 which gives one. 

0, 1, 1

The next number would be 1 + 1 = 2 

0, 1, 1, 2 

Now, the next number would be 1 + 2 = 3 

0, 1, 1, 2, 3

Continuing in this way gives the Fibonacci series. A specific term in the series is represented as Fn where n is the position of that number from the beginning. For example,

F0 = 0, F1 = 1, F2 = 1, F3=2, F4 = 3, F5 = 5 and so on... 

The Fibonacci series can be expressed as a recurrencerelation as shown below: 

F0 = 0

F1 = 1
F_n = F_n-1 + F_n-2; where n >= 2

     What’s neat about this sequence is that when you try to sit down and think up an algorithm to solve this problem, you can’t help but think of recursion. Since the solution to the next number relies on the past two iterations, recursion becomes very handy. Now that’s not to say that the only way to solve this problem is with Java Recursion, but it can make the coding much simpler (We also can use Java Iterator to solve this sequence). Let’s start coding and talk about it. The basic model of recursion is to follow two rules properly:

Define stopping point.
Walk towards the stopping point.

     As long as we follow these two rules, we are ok, otherwise we might get caught in an infinite loop. In this case we have to terminate our code manually. Since we are looking for the Nth number of our Fibonacci Sequence, do you guess what’s our “stopping point” would be? Nice guess! It’s the number we are wishing to solve. If the question is: “What is the 20^th number in the Fibonacci Sequence?”, then our precious “stopping point” is 20.

     Well then, we have our stopping point, now think about the second part of our recursion model. How do we make our code to walk towards the stopping point? We know that the Fibonacci sequence represents 

F_n = F_n-1 + F_n-2; where n >= 2. Here the _n represents the unique index of any particular number in the Fibonacci sequence. In this case, its 20.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Private static int index = 0;
public static void main(String[] args){
    int n1 = 0;
    int n2 = 1;
    System.out.println(“index: “ + index + “ = “ + n1);
    fibonacci(n1, n2);
}
public static void fibonacci(int n1, int n2){
    System.out.println(“index: “ + index + “ = “ + n2);
    if (index == 20) { //Stopping point.
        return;
    }
    index++; //Make sure to increment our index to walk towards the end.
    fibonacci(n2, n1 + n2);
}

     Here we go! We have our working algorithm for the Fibonacci Sequence. Now change your stopping point and explore different index  of the sequence.