Stepping Through Recursive Fibonacci Function

The Fibonacci Sequence is such that each number is the sum of the previous two numbers.

Fibonacci Sequence: 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 . . .

This is a great use case for recursion.

We will build our Fibonacci algorithm using recursion. We will define a function that takes in a number called position as a parameter.This position will indicate which number from the Fibonacci sequence we want returned to us.

For example:
fibonacci(4) // returns 3
fibonacci(9) // returns 34

This algorithm does not require a lot of code, so we will not over complicate it.

Let's define the function fibonacci that takes in a number position .

function fibonacci(position){

}

Next, let's go-ahead to define our base case. So, we can ask ourselves, what is the situation that we immediately know one number is found at the given position in our Fibonacci sequence? There are two situations:

1. Since the first two numbers in the Fibonacci sequence are always 1 and 1, if the position equals 1 it should return 1 or if it equals 2 it should return 1 still

function fibonacci(position){
   if(position < 3) return 1;
}

Now we write our recursive code:

function fibonacci(position){
   if(position < 3) return 1;
   else return fibonacci(position - 1) + fibonacci(position - 2)
}

We know that the number in the position is a result of the sum of the two previous numbers before it position -1 and position - 2. We return the result of adding our Fibonacci function using these two cases as passed in parameters of each. The function will call itself until the base case is attained then it will stop.

To see a visualization of the breakdown of how each function is called, here's a link to a video that explains it.

https://www.youtube.com/watch?v=zg-ddPbzcKM&t=319s

Now, this algorithm is not conducive because when we want to return the position of a very large number say 1500, the chain of recursion will result in what we call a stack overflow! Different browsers have limits to how large a call stack is supposed to be and if you reach that limit, the function will throw in an error stating that you've to exceed the maximum call stack limit.

This algorithm has an exponential O(2^n) time complexity because the chain of recursion grows exponentially by each call making it a bad way to solve this.

We will look at a much faster algorithm in the next one.

Happy Hacking!