【 JavaScript 】JavaScript 費氏數列的 3 種解法

面試的時候經常會問到怎麼用 JavaScript 解費氏數列，面試到後面整理了一下常見的 3 種解法：
首先說明一下費氏數列：[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] ，通常會請你用 JavaScript 求解陣列的最後一個值。

1. JavaScript 費氏數列 – 遞迴解

// Time complexity = O(2^n)
function fib(n) {
  if (n < 2) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

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

2. JavaScript 費氏數列 – 迴圈解

// Time Complexity = O(n)
function fib(n) {
  const arr = [0, 1];
  for (let i = 2; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }
  return arr[n];
}

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

3. JavaScript 費氏數列 – Memoization

// Time Complexity = O(n)
// 好理解的版本
function fib(n) {
  if (!fib.cache) {
    fib.cache = {
      0: 0,
      1: 1
    };
  }
  if (fib.cache[n] !== undefined) {
    return fib.cache[n];
  }
  fib.cache[n] = fib(n - 1) + fib(n - 2);
  return fib.cache[n];
}

// 其他函數通用版
function memoize(fn) {
  const cache = {};
  return function(...args) {
    if (cache[args]) {
      return cache[args];
    }
    const result = fn.apply(this, args);
    cache[args] = result;
    return result;
  }
}

function fib(n) {
  if (n < 2) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

fib = memoize(fib);

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

如果覺得我的文章有幫助的話，歡迎幫我的粉專按讚哦~謝謝你！