JavaScript 費氏數列

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

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

1. JavaScript 費氏數列 – 遞迴解

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

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

2. JavaScript 費氏數列 – 迴圈解

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. JavaScript 費氏數列 – 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

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

Leave a Comment

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

Scroll to Top