Phone screen challenge

Solutions.fs

// A sequence of integers is defined as F(N) = F(N-1) * F(N-2),
// with F(0) = 1 and F(1) = 2. 
// Write a function which, given N, prints N and F(N)
// f(2) = F(2-1) * F(2-2) = F(1) * F(0) = 2 * 1 = 2
// f(3) = f(3-1) * f(3-2) = f(2) * f(1) = 2 * 2 = 4
// f(4) = f(4-1) * f(4-2) = f(3) * f(2) = 4 * 2 = 8
// f(5) = f(5-1) * f(5-2) = f(4) * f(3) = 8 * 4 = 32
// f(6) = f(6-1) * f(6-2) = f(5) * f(4) = 32 * 8 = 256

// recursive
let rec f n =
    match n with
    | 0 -> 1
    | 1 -> 2
    | _ -> f(n-1) * f(n-2)

// iterative w/mutability
let iterF =
    function
    | 0 -> 1
    | 1 -> 2
    | n ->
        let mutable prevPrevResult = 1 // F(0)
        let mutable prevResult = 2 // F(1)
        let mutable result = prevResult * prevPrevResult // F(2)
        for _ in 2 .. n do // first 2 iterations have constant values, skip them
            result <- prevResult * prevPrevResult
            prevPrevResult <- prevResult
            prevResult <- result
        result

// fold (iterative w/immutability)
let foldF n =
    seq { 0 .. n }
    |> Seq.fold (fun (prev1,prev2) _ -> prev1 * prev2, prev1) (1,2)
    |> snd