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's答案是好的，但是为什么要在线性时间停止？事实证明，您实际上可以实现对数时间，只需注意可以将递归表示为矩阵乘法：