函數語言版本的費氏數列程式

費氏數列 (Fibonacci's numbers) 是 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 這樣的數列，其中每個數為前二個數的和，除了最前面的底數 0, 1 外。

小小的費氏數列程式很好寫，看起來也很好執行，以 C 語言為例：

n_2 = 0; n_1 = 1;
if (n == 0)
    fn = n_2;
else if (n == 1)
    fn = n_1;
else
    for (i=2; i<n; i++) {
        fn = n_2 + n_1;
        n_2 = n_1;
        n_1 = fn;
    }

最後 fn 為答案。但 C 程式版本其實不好執行，若指定的費氏項數稍大，而程式中的變數是整數或長整數，就會溢位。

函數語言 Haskell 寫出來的比較可愛：

fibNum :: (Integral a) => a -> a
fibNum 0 = 0
fibNum 1 = 1
fibNum (n+1) = fibNum (n-1) + fibNum n

雖然沒有溢位問題了，但是打個 fibNum 100 跑得真久，因為遞迴的計算量很大。

但函數語言的好處是，許多程式可用累積變數 (aggregating parameters) 改寫成線性版本，改善計算效率。在此，例如：

fib :: (Integral a) => a -> a
fib n = fib1 n 0 1

fib1 :: (Integral a) => a -> a -> a -> a
fib1 0 x _ = x
fib1 1 _ y = y
fib1 (n+1) x y = fib1 n y (x+y)

打個 fib 100 很快就跑出答案為： 354224848179261915075 。漂亮！

在此可見程式語言的特性，除了語法可愛和簡潔之外，在可優化的容易程度是特別有價值的。

想要探索更深入的價值，請積極參與微程式資訓技術研討會¹並參閱投影片。

---

¹微程式資訊技術研討會是微程式資訊股份有限公司的內部會議。