Fibonacci Sequence

Dynamic programming can often be achieved either recursively or using the 'bottom up' approach. I'm going to go through three ways of solving for the nth value of the fibonacci sequence and compare the runtime of each option.

The options:

1. Using recursion without memoization
2. Using recursion with memoization
3. Using the 'bottom up' approach (iterative)

Quick aside: memoization is a fancy term for caching values to prevent redundant computation within a function.

The first (and worst) method for solving for a value of the fibonacci sequence is using recursion without memoization. The solution is printed below.

function fibRec(n) {
  let result;
  if (n === 1 || n === 2) {
    result = 1;
  } else {
    result = fibRec(n - 1) + fibRec(n - 2);
  }
  return result;
}

First I declare a variable, 'result' and conditionally set it to 1 (base case) or the sum of fibRec(n - 1) & fibRec(n - 2). The program works backwards to solve for each preceding fibRec(n), sums the appropriate values and returns the result.

This solution is least efficient because it requires an evaluation for each call to 'fibRec', even if the argument being passed to the function has already been evaluated. This results in redundancy because different values of 'fibRec(n)' are not being stored. To store values of 'fibRec(n)' we introduce the concept of memoization. The recursive solution without memoization has a big 'O' runtime of 'O(2 ** n)'.

The recursive solution with memoization is shown below.

function fibMemo(n, memo = {}) {
  if (memo[n]) return memo[n];
  let result;
  if (n === 1 || n === 2) {
    result = 1;
  } else {
    result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  }
  memo[n] = result;
  return result;
}

This time we introduce a new parameter, 'memo', with a default value of an empty object. If 'n' exists in memo we return the value of memo[n]. Otherwise, we declare a variable, result, and conditionally set it to 1 or the sum of fibRec(n - 1, memo) & fibRec(n - 2, memo). We then set memo[n] equal to result. The significant difference here is that memo is being passed to the function for each recursive call, and memo is being updated with each new 'n' value (so the function is never performed more than once for any given value of 'n'). This solution has a big 'O' runtime of 'O(n)'.

The last solution is the most intuitive for me and also performs much better than our recursive solution without memoization. The solution is below.

function fibIter(n) {
  if (n === 1 || n === 2) return 1;
  let arr = new Array(n + 1);
  arr[1] = 1;
  arr[2] = 1;
  for (let i = 3; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }
  return arr[n];
}

This solution is based on the principle that if you successively find the solution for each value of 'n' (starting from 1), and store each value to an array, you can work from the bottom up and simply return the last element of your array. I first return 1 if 'n' is equivalent to 1 or 2. I then declare a new array of length 'n + 1' (this length allows each value of 'n' to match its index value). This is where I will store each value of the fibonacci sequence through our input value, 'n'. I then set arr[1] & arr[2] equal to 1. Next I loop from 3 through n, solving for each successive fibonacci value (using previously stored values stored in 'arr'). The last step is to return the last element of arr, 'arr[n]'. This solution also has a big 'O' runtime of 'O(n)'.

For comparison's sake here are the actual runtimes for each solution, solving for the 50th value of the fibonacci sequence (12,586,269,025).

Recursive w/out Memoization: 128,975.460ms
Recursive w/ Memoization: 0.229ms
Bottom Up Approach: 8.452ms

This helps illustrate the massive difference in efficiency and helps me understand why memoization can be so helpful. I think the iterative (bottom up) approach is often easiest to conceptualize, but seeing the power of memoization combined with recursion makes me interested in applying that strategy to more problems in the future.

Sources:
What Is Dynamic Programming and How To Use It, by YK