在 Ruby 裡的費式數列該怎麼寫?

這題在面試上非常容易被問到所謂的費式數列是什麼？

所謂的費式數列(費波那契數列)，指的是每一項是前兩項之和。

• 第 0 項 = 0
• 第 1 項 = 1
• 第 n 項 = 第 n - 1 項 + 第 n - 2 項

那接下來就來介紹費式數列的幾種寫法:

第一種 遞迴式

def f(x)
 return 1 if x <= 2
 return f(x-1) + f(x-2)
end

遞迴的概念就像是不停的呼叫自己，最終到遞迴到第0項的時候再一次次回推得到解答，但這樣寫的效能較差！

第二種 陣列式

def fi(n)
  arr = [0, 1, 1]
  if n > 2
    for i in 0..n - 1
      arr << arr[i] + arr[i + 1]
      i += 1
    end
  end
 arr[n]
end

一開始直接指定一個陣列並且確保要在第二項之後才會進行加總，那為什麼要 n-2 呢? 因為第 2 項是第 1項與第 0 項的總和，所以才需要 -2 ! 最後回傳陣列的第 n 項表示要取得最後一項的意思。

但這種寫法如果今天要 fi(10000) 那我們陣列豈不是超長一串？也會影響效能的快慢，所以就衍生出了第三種寫法

第三種 指定變數

既然都說了費式數列是前兩項之和，那是不是可以使用三個變數就完成這件事情呢？

def fi(x)
  n1 = 0
  n2 = 1
  return 1 if x <= 1
    for i in 0..x - 2
      n3 = n1 + n2
      n1 = n2
      n2 = n3
    end
  n3
end

其實跟陣列的寫法很像，但既然我們只需要最後一項的結果就可以這樣寫，n3 = n2 + n1 執行完後再將 n1 的值變成 n2 、 n2 的值變成n3 就可以了，這樣一來比起上述兩種寫法的效能也會比較好。

總結

以上的寫法都是我個人的寫法，如果有更好的寫法也請各位大大們提供！但最重要的是費式數列一定要會！！！