How to solve Fibonacci recursively with JavaScript

Welcome to my article on how to solve Fibonacci recursively. I will start by providing the answer and then explain it in detail. Here is the solution:

var Fib = function(n) { 
if (n <= 1) return n;
return Fib(n-1) + Fib(n-2);
}

Now, let’s walk through the code above and see what is happening. At first glance, it appears that this solution could evaluate to 2. If you call Fib twice, each one will eventually evaluate to 1 and then you are adding them together to equal 2. However, this is not correct, and understanding how the answer works will get you started on the path to mastering recursion.

What is actually happening when you call Fib is that you are creating 2 more functions every time until you hit n = 1, at which point, you evaluate to 1 and then stop. So, if you start at n = 5, then you are calling (n = 4 and n = 3). Both of these will then call two more functions bringing us to (n = 3 and n = 2) AND (n = 2 and n = 1). This creates a tree like structure, which is very common when using recursion. See below for a diagram of what is happening:

Now that you see this diagrammatically, let’s look at how the result of the formula is calculated. Each time you get to n = 1 on a branch, the Fib sequence ends and evaluates to 1. This means that once all the various branches on the trees evaluate (5 of them above), you will have the answer to the very first: return Fib(n-1) + Fib(n-2) = 3 + 2 = 5. Which is not equal to 2!

And that should help you understanding how the recursive answer to Fibonacci works. Please feel free to comment this article if you have questions.

Show your support

Clapping shows how much you appreciated David Schwartz’s story.