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