Fibonacci Algorithm Part 2

Let’s solve one of the famous recursion algorithm problems today with a Bottom-up algorithm. I’m pretty sure if you are studying for data structure and learning recursion you may encounter Fibonacci as an example to define recursion. So what is a Fibonacci?

Fibonacci Diagram Example.

Well, it’s actually just a sequence of numbers. To add more explanation of this sequence of numbers is that number is the addition of the two preceding ones, starting from 0 and 1. With this very basic knowledge, we are going to use a bottom-up algorithm method to solve the Fibonacci algorithm problem. As it sounds it’s actually pretty simple logic to approach, you start from 0 and add until you reach the desired output. For example, let‘s look at the code below.

array = [0,1] //We start with initial number 0,1.
let nextNumber = dp[i-1] + dp[i-2] //This will give you next number 
                                    by adding two preceding numbers.
array.push(nextNumber) // add to the array keep repeat this process.
return array.pop() 

pretty straight forward right? with this logic now let’s implement this in our real coding with the solution.

function fibonacci2(N){
   if(N < 2) {
     return N
 }
  let array = [0,1]
for(let i = 2; i < N; i++){
    let nextNumber = array[i-2] + array[i-1]
    array.push(nextNumber)
  }
    return array.pop() 
}
console.log(fibonacci2(8))  //13

There will go, will testing N given will get the correct Nth index of the Fibonacci number.