Fibonacci — Three Approaches

Overview

Three implementations of Fibonacci compared: naive exponential recursion, hash-table memoization via closures, and a tail-recursive O(1)-space version. Includes benchmarking to show why algorithm choice matters more than micro-optimization.

Three Approaches

1. Naive Recursion — O(2ⁿ)

The textbook implementation. Beautiful but exponentially slow:

let rec fib_naive = function
  | 0 -> 0
  | 1 -> 1
  | n -> fib_naive (n - 1) + fib_naive (n - 2)

2. Memoized — O(n) time, O(n) space

A closure captures a private hash table. The cache persists between calls but is invisible to the outside world:

let fib_memo =
  let cache = Hashtbl.create 64 in
  let rec fib n =
    match Hashtbl.find_opt cache n with
    | Some v -> v
    | None ->
      let v = match n with
        | 0 -> 0 | 1 -> 1
        | _ -> fib (n - 1) + fib (n - 2)
      in
      Hashtbl.replace cache n v; v
  in fib

3. Tail-Recursive Iterative — O(n) time, O(1) space

The most efficient approach. Uses two accumulators instead of a cache:

let fib_iter n =
  if n <= 0 then 0
  else
    let rec aux a b i =
      if i = n then b
      else aux b (a + b) (i + 1)
    in aux 0 1 1

Performance Comparison

First 15 Fibonacci numbers:
  [0; 1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; 233; 377]

fib_naive(35) = 9227465  (0.1842s)
fib_memo(35)  = 9227465  (0.000001s)
fib_iter(35)  = 9227465  (0.000001s)

Speedup (memo vs naive): 184200x
fib_iter(50) = 12586269025

The memoized and iterative versions are ~184,000× faster than naive for n=35. The gap grows exponentially for larger inputs.