JavaScript 費氏數列的三種解法

費氏數列：[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] ，通常會求最後一個值。

1. 遞迴解

const fib = (num) => {
  if (num < 2) return num
  return fib(num-1) + fib(num-2)
}

fib(10)
// 55
fib(6)
// 8

2. 迴圈解

const fib = (num) => {
  if (num < 2) return num
  const arr = [0, 1]
  for (let i=2; i<=num; i++) {
    arr[i] = arr[i-1] + arr[i-2]
  }
  return arr[num]
}

fib(10)
// 55
fib(6)
// 8

3. Memoization

const fib = (num) => {
  if (!fib.cache) {
    fib.cache = {}
  }
  if (fib.cache[num] !== undefined) {
    return fib.cache[num]
  }
  fib.cache[0] = 0
  fib.cache[1] = 1
  fib.cache[num] = fib(num-1) + fib(num-2)
  return fib.cache[num]
}

fib(10)
// 55
fib(6)
// 8