題目：
(5 級) Memoized Fibonacci
斐波那契數列 (Fibonacci sequence) 通常用來解釋遞歸樹 (Recursive tree)。

def fibonacci(n)
  return n if (0..1).include? n
  fibonacci(n - 1) + fibonacci(n - 2)
end

這種算法可以很好地發揮教育作用，但效率極低，不僅僅是因為遞歸，而是因為調用了兩次 fibonacci method，遞歸的右分支 (fibonacci(n-2)) 重新計算了左分支已計算好的所有斐波那契數 (fibonacci(n-1))。

該算法效率極低，以至於無法計算超過 50 斐波那契數列。你可以在等待答案時去喝咖啡或小睡一下。但是，如果您在 "Codewar" 中嘗試此操作，則很可能在算出答案之前出現 "code timeout" 問題。

在這個 Kata，我們要實現記憶解決方案。這將很酷，因為它可以讓我們繼續使用遞歸樹算法，同時仍將其充分優化得以非常迅速地獲得答案。

記憶版本的訣竅是，我們將保留一個暫存的數據結構 (很可能是一個關聯陣列)，在計算數據時將在其中存儲斐波那契數。計算斐波那契數時，我們首先在暫存中查找它，如果不存在，我們將其計算結果並放入暫存中，反之則返回暫存中的數。

將該 method 重構為遞歸的 Fibonacci method，並使用已記憶的數據結構避免了遞歸樹的缺陷。

Ruby 解法：

# 先做出暫存用的 Hash 結構
# 這邊使用實體變數是因為區域變數無法在 fibonacci method 的 scope 中被調用
@cache ||= {0 => 0, 1 => 1}

def fibonacci(n)
  # 先確認第 n/n-1/n-2 個斐波那契數是否已經被計算過，存在 cache 中
  if not @cache.has_key?(n)
    # 沒有的話就先計算，並把結果放進 cache 中
    @cache[n-1] = fibonacci(n-1) if not @cache.has_key?(n-1)
    @cache[n-2] = fibonacci(n-2) if not @cache.has_key?(n-2)
    # 再將前兩個斐波那契數加總放進 cache 中
    @cache[n] = @cache[n-1] + @cache[n-2]
  end

  # 最後回傳暫存中的斐波那契數
  @cache[n]
end

JavaScript 解法：

// 先做出暫存用的 Object 結構
let cache = {0: 0, 1: 1};

var fibonacci = function(n) {
  // 先確認第 n 個斐波那契數是否已經被計算過，存在 cache 中
  // 因為 JS 的數字 0 被視為 false，所以要另外拿出來判斷
  if (!(cache[n] === 0 || cache[n])) {
    // 沒有的話就先計算，並把結果放進 cache 中
    if (!cache[n-2]) { cache[n-2] = fibonacci(n-2); }
    if (!cache[n-1]) { cache[n-1] = fibonacci(n-1); }
    // 再將前兩個斐波那契數加總放進 cache 中
    cache[n] = cache[n-1] + cache[n-2];
  }
  
  // 最後回傳暫存中的斐波那契數
  return cache[n];
}