What is recursion?

Recursion is defined as when method is defined in terms of itself. The most famous example is the Fibonacci sequence, where each term is the sum of the previous two terms. Here are the first few terms of Fibonacci sequence: 0,1,1,2,3,5,8.... The first two terms are 0 and 1. That means the 3rd term is 1 as 0+1 = 1.

public int fibonacci(int index){

    if(index == 0){

        return 0;

    }

    if(index==1){

        return 1; 

    }

    return fibonacci(index-1) + fibonacci(index-2);

}

The two if-statements are intended to avoid infinite recursion. After all, if the method didn't evaluate to anything, the computer would do it forever. If an infinite recursion occurs, it results into a StackOverflow error.

What is fibonacci(5)?

The easiest way to solve this problem is to break it down into the equations. f here means fibonacci.

f(5) = f(4) + f(3)

f(4) = f(3) + f(2)

f(3) = f(2) + f(1)

f(2) = f(1) + f(0)

f(1) = 1

f(0) = 0

Now we can plug it in back into the original equations.

f(2) = 1 + 0 = 1

f(3) = 1 + 1 = 2

f(4) = 2 + 1 =3

f(5) = 3 +2 = 5

Answer is 5.

This method may be tedious, but it avoids errors. It also applies to string methods as well. For strings, be careful of the order of adding strings: "a"+"b" is not equal "b"+"a".