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)

Have you tried with [tail calls](https://devblogs.microsoft.com/fsharpteam/tail-calls-in-f/)? https://stackoverflow.com/questions/3248091/f-tail-recursive-function-example — Gábor Bakos, Mar 05 '20 at 20:46

score 5 · Answer 1 · answered Mar 05 '20 at 23:01

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]

score 5 · Answer 2 · answered Mar 05 '20 at 23:45

kaefer's answer is good, but why stop at linear time? It turns out that you can actually achieve logarithmic time instead, by noting that the recurrence can be expressed as a matrix multiplication:

[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]

But then T_n can be achieved by applying the recurrence n times, which we can see as the first entry of M^n*[T_0; T_1; T_2; T_3] (which is just the upper right entry of M^n), and we can perform the matrix multiplication in O(log n) time by repeated squaring:

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)

Nice answer. Diagonalize to get O(1) time! – Charles Roddie Mar 06 '20 at 12:15 — Charles Roddie, Mar 06 '20 at 12:15

score 1 · Accepted Answer · answered Mar 08 '20 at 07:49

Here is a tail recursive version, which compiles to mostly loops (and its complexity should be 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 corresponds to tetra (n - 1), acc2 corresponds to tetra (n - 2), acc3 corresponds to tetra (n - 3), acc4 corresponds to tetra (n - 4)

Based on the Fibonacci example

More Efficient Recursive Tetranacci function in F#

3 Answers3