Three approaches to dynamic programming : leveraging recursion

fibonacci_dynamic_programming.js

// Get the value for index n in a Fibonacci sequence

// Recursion : O(2^n)
// n: positive integer
const getFibRecursion = n => {
  //initialize result to be returned eventually
  let result
  // check for the first two values (not computable)
  if (n === 1 || n === 2) {
    result = 1
  } else {
    // recursively get the value and store it in result
    result = getFibRecursion(n - 1) + getFibRecursion(n - 2)
  }
  return result
}

getFibRecursion(5)
// 5

// Memoization : O(n)
// n: positive integer, memo: array of length n+1 filled with null values 
const getFibMemo = (n, memo) => {
  // initialize result to be returned eventually
  let result
  // check if we have memoized the result for getFibMemo 
  if (memo[n] !== null) {
    // return the memoized value
    return memo[n]
  }
  // check for the first two values (not computable)
  if (n === 1 || n === 2) {
    result = 1
  } else {
    // recursively get the value and store it in result
    result = getFibMemo(n - 1, memo) + getFibMemo(n - 2, memo)
  }
  // memoize the computed value
  memo[n] = result
  
  return result
}

getFibMemo(5, Array(6).fill(null))
// 5

// Bottom up : O(n)
// n: positive integer
const getFibBottomUp = n => {
  // check for the first two values (not computable)
  if (n === 1 || n === 2) {
    return 1
  }
  // initialize array to be filled with values
  let bottomUp = Array(n+1).fill(null)
  // initialize uncomputable values
  bottomUp[0] = 0
  bottomUp[1] = 1
  bottomUp[2] = 1
  // loop over array and fill with relevant values
  bottomUp.forEach((value, index) => {
    if (index < 3) {
      bottomUp[index] = bottomUp[index]
    } else {
      bottomUp[index] = bottomUp[index-1] + bottomUp[index-2]
    }
  })

  return bottomUp[n]
}

getFibBottomUp(5)
// 5