F# – Fibonacci Sequence

A classic implementation of the Fibonacci sequence is shown below.

// Classic implementation (O(n) time complexity and O(n) space complexity)
let rec fib1 n =
    match n with
    | n when n <= 2 -> 1
    | _ -> fib1 (n-1) + fib1 (n - 2)

An optimized version of the Fibonacci sequence is shown below. The dictionary is used to store previously computed values and used in subsequent iterations making it much more performant than the previous implementation.

let rec fib2 (n, dict: Dictionary<int, int>) =
    match n with
    | n when dict.ContainsKey(n) -> dict[n]        
    | n when n <= 2 -> 1
    | _ -> 
        dict.Add(n, fib2 (n-1, dict) + fib2 (n - 2, dict))
        dict[n]