F# 程式設計/解決方案/遞迴

F#：遞迴和遞迴函式解決方案

更快的斐波那契函式

以下函式計算斐波那契數列中的第n個數字

let rec fib = function
    | n when n=0I -> 0I
    | n when n=1I -> 1I
    | n -> fib(n - 1I) + fib(n - 2I)

上面的函式既不是尾遞迴，也不特別有效，計算複雜度為O(2ⁿ)。此函式的尾遞迴形式具有O(n)的計算複雜度。重新編寫上面的函式，使其成為尾遞迴。

你可以使用以下方法驗證函式的正確性

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(10) = 55
fib(100) = 354224848179261915075

解決方案

檢查斐波那契數列中的前 10 個數字

 n: fib(n)
---------
 0: 0
 1: 1
 2: 1
 3: 2
 4: 3
 5: 5
 6: 8
 7: 13
 8: 21
 9: 34
10: 55

數列中的每個數字都是它上面兩個數字的和。如果我們在累積引數中儲存前兩個斐波那契數字的值，那麼我們可以非常輕鬆地計算下一個斐波那契數字。

let fib n =
    let rec loop acc1 acc2 = function
        | n when n = 0I -> acc1
        | n when n = 1I -> acc2
        | n -> loop acc2 (acc1 + acc2) (n - 1I)
    loop 0I 1I n

累加器變數acc1和acc2分別對應fib(n - 1)和fib(n - 2)。

我們可以在 fsi 中測試此函式

> let fib n =
    let rec loop acc1 acc2 = function
        | n when n = 0I -> acc1
        | n -> loop acc2 (acc1 + acc2) (n - 1I)
    loop 0I 1I n;;

val fib : Numerics.BigInteger -> Numerics.BigInteger

> [0I .. 10I] |> Seq.iter (fun x -> printfn "fib(%O) = %O" x (fib x));;
fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55
val it : unit = ()

> fib 100I;;
val it : Numerics.BigInteger = 354224848179261915075I

> fib 1000I;;
val it : Numerics.BigInteger 
= 434665576869374564356885276750406258025646605173717
80402481729089536555417949051890403879840079255169295
92259308032263477520968962323987332247116164299644090
6533187938298969649928516003704476137795166849228875I