Fibonacci using Recursion

on javascript, recursion, algorithms

Problem:

Given a position, find the fibonacci number at that position. We will use recursion to find the solution even though it is not as efficient as memoization.

Solution

solution 1

const fibonacci = position => {
	if(position < 3){
		return 1;

	}
	else {
		return fibonacci(position - 1) + fibonacci(position - 2);
	}
}

solution 2 - a terse solution using ternary operator

const fibonacci = position =>  position < 3 ? 1 : fibonacci(position - 1) + fibonacci(position - 2);

Explanation

Fibonacci Sequence - 1 1 2 3 5 8 13 21 …​

A fibonacci sequence starts with 1 and 1 and then continues on with the sum of previous two numbers.

For example if the position passed to the function is 6, the value 8 will be returned. If 8 is passed to the function, then 21 will be returned.

We have used recursion to find the result. We keep calling the fibonacci function using recursion until the position is less than 3. When the position < 3 it will return 1.

Lets say the position passed to the function is 6. Since 6 is not less than 3, the else clause will be executed which will be

return fibonacci(5) + fibonacci(4);

Now fibonacci(5) will be executed as

return fibonacci(4) + fibonacci(3);

and so on until position becomes less than 3.

The following flowchart will make it clear how recursion works.

fibonacci.jpeg