Dynamic programming fibonacci example

dynamic-fibonacci.js

// Naive recursion.
function fib1(n) {
  if (n <= 1) {
    return n
  }

  return fib1(n - 1) + fib1(n - 2)
}
{
  console.log('fib1')
  const start = Date.now()
  console.log(fib1(100))
  const end = Date.now()
  console.log(end - start)
  console.log('===')
}

// Dynamic "top-down" w/momoization.
const fibs = [0, 1]
function fib2(n) {
  if (fibs[n] === undefined) {
    fibs[n] = fib2(n - 1) + fib2(n - 2)
  }

  return fibs[n]
}
{
  console.log('fib2')
  const start = Date.now()
  console.log(fib2(100))
  const end = Date.now()
  console.log(end - start)
  console.log('===')
}

// Dynamic "bottom-up".
function fib3(n) {
  if (n === 0) {
    return n
  }

  let previous = 0
  let current = 1

  for (let i = 0; i < n - 1; i++) {
    let newValue = previous + current
    previous = current
    current = newValue
  }

  return current
}
{
  console.log('fib3')
  const start = Date.now()
  console.log(fib3(100))
  const end = Date.now()
  console.log(end - start)
  console.log('===')
}

/*
fib1
?
?
===
fib2
354224848179262000000
1
===
fib3
354224848179262000000
0
===
*/