F# 中更高效的递归 Tetranacci 函数

Question

我正在尝试尽可能高效地使用 F# 编写一个 tetranacci 函数，但我提出的第一个解决方案确实效率低下。你能帮我想出一个更好的吗？我如何能够在线性时间内实现这一点？

let rec tetra n =
 match n with
 | 0 -> 0
 | 1 -> 1
 | 2 -> 1
 | 3 -> 2
 | _ -> tetra (n - 1) + tetra (n - 2) + tetra (n - 3) + tetra (n - 4)

Answer 1

您可以通过设计一个函数来计算 4 元组的下一次迭代的状态，从而节省成本。然后，序列生成器函数Seq.unfold可用于构建包含每个状态四元组的第一个元素的序列，这是一种“惰性”操作——序列的元素仅在消耗时按需计算。

let tetranacci (a3, a2, a1, a0) = a2, a1, a0, a3 + a2 + a1 + a0
(0, 1, 1, 2) 
|> Seq.unfold (fun (a3, _, _, _ as a30) -> Some(a3, tetranacci a30))
|> Seq.take 10
|> Seq.toList
// val it : int list = [0; 1; 1; 2; 4; 8; 15; 29; 56; 108]

请注意，标准 Tetranacci 序列 ( OEIS A000078 ) 通常会以以下开始状态生成(0, 0, 0, 1)：

// val it : int list = [0; 0; 0; 1; 1; 2; 4; 8; 15; 29]

Answer 2

kaefer 的回答很好，但为什么要在线性时间停止？事实证明，您实际上可以实现对数时间，注意递归可以表示为矩阵乘法：

[T_n+1]   [0; 1; 0; 0][T_n]
[T_n+2] = [0; 0; 1; 0][T_n+1]
[T_n+3]   [0; 0; 0; 1][T_n+2]
[T_n+4]   [1; 1; 1; 1][T_n+3]

但是然后T_n可以通过应用递归n次来实现，我们可以将其视为的第一个条目M^n*[T_0; T_1; T_2; T_3]（恰好是 的右上条目M^n），并且我们可以通过重复平方在 O(log n) 时间内执行矩阵乘法：

type Mat =
| Mat of bigint[][]
    static member (*)(Mat arr1, Mat arr2) =
        Array.init arr1.Length (fun i -> Array.init arr2.[0].Length (fun j -> Array.sum [| for k in 0 .. arr2.Length - 1 -> arr1.[i].[k]*arr2.[k].[j] |]))
        |> Mat

    static member Pow(m, n) =
        match n with
        | 0 -> 
            let (Mat arr) = m
            Array.init arr.Length (fun i -> Array.init arr.Length (fun j -> if i = j then 1I else 0I))
            |> Mat
        | 1 -> m
        | _ ->
            let m2 = m ** (n/2)
            if n % 2 = 0 then m2 * m2
            else m2 * m2 * m

let tetr =
    let m = Mat [| [|0I; 1I; 0I; 0I|]
                   [|0I; 0I; 1I; 0I|]
                   [|0I; 0I; 0I; 1I|]
                   [|1I; 1I; 1I; 1I|]|]
    fun n -> 
        let (Mat m') = m ** n
        m'.[0].[3]

for i in 0 .. 50 do
    printfn "%A" (tetr i)