More Efficient Recursive Tetranacci function in F#

Question

I am trying to write a tetranacci function using F# as efficiently as possible the first solution I came up with was really inefficient. can you help me come up with a better one? How would i be able to implement this in linear time?

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

You could economise by devising a function that computes the state for the next iteration on a 4-tuple. Then the sequence generator function Seq.unfold can be used to build a sequence that contains the first element of each state quadruple, an operation that is 'lazy` -- the elements of the sequence are only computed on demand as they are consumed.

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]

Note that the standard Tetranacci sequence (OEIS A000078) would usually be generated with the start state of (0, 0, 0, 1):

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