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

我试图使用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)

最佳答案

这是一个tail recursive版本，可编译为大部分循环（其复杂度应为O（n））：

let tetr n =
  let rec t acc4 acc3 acc2 acc1 = function
    | n when n = 0 -> acc4
    | n when n = 1 -> acc3
    | n when n = 2 -> acc2
    | n when n = 3 -> acc1
    | n -> t acc3 acc2 acc1 (acc1 + acc2 + acc3 + acc4) (n - 1)
  t 0 1 1 2 n

acc1对应于tetra (n - 1)，
acc2对应于tetra (n - 2)，
acc3对应于tetra (n - 3)，
acc4对应于tetra (n - 4)

基于the Fibonacci example