Solving The Fibonacci Sequence Using Recursion

The fibonacci sequence is something everyone encounters, when they begin learning algorithms. The sequence looks something like this:

The pattern is simple, the next number in the sequence is the sum of the previous two. So 1 + 1 is 2, 1 + 2 is 3, and so on.

We are going to create a function to solve for the number at the nth place of the fibonacci sequence.

Here is the completed version of the code:

What is essentially happening, is we’re solving for the fibonacci in the simplest case, and adding them (line 9). We can accomplish this using recursion.

Its important for every recursive function to have a base case, as can be seen in lines 4 and 6. When n equals 0 we return 0, because the 0th place of the fibonacci sequence is 0. When n equals 1, return 1 because the 1st place of the fibonacci sequence is 1.

The is a very powerful technique to solve problems that are difficult.

There is one issue with this function though…

Take a second and reread it, and see if you can figure it out.

The issue with this function is it will take longer, the larger n becomes. This is measured as Big O time complexity, and this function has a Big O of O(2^n).

If you don’t understand why this is bad, no problem, you can review time complexity HERE.

How we can fix this is fairly simple. Take a look at this picture representation of the fibonacci function as a tree structure:

As you can see in the highlighted sections, we’re solving for the same function fibonacci(2) multiple times. This is the case for fibonacci(3) as well. We can save the answers to those, so we don’t have to go over them multiple times. This process is know as Memoization. We will add an object to store the answers we’ve already solved, so we don’t redo them.

In line 4, we check if the answer exists and if it exists, we return it. In line 10, we store the answers we get in the memo object. Also notice, we are passing the memo object in every call of the fibonacci function.

This makes our function much faster, with a Big O of O(n).

If you can, try to implement this yourself, so you can understand it more clearly.

Otherwise, subscribe for content like this and more.