ExamplesBy LevelBy TopicLearning Paths
273 Intermediate
← 272273 →

Fibonacci Variants

RecursionIterationAccumulatorsFold

Tutorial Video

Text description (accessibility)

This video demonstrates the "Fibonacci Variants" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Recursion, Iteration, Accumulators, Fold. Compute the nth Fibonacci number using three different strategies: direct recursion, tail-recursive accumulator, and a fold over a range — then add an idiomatic iterative Rust version for comparison. Key difference from OCaml: 1. **Tail

Tutorial

The Problem

Compute the nth Fibonacci number using three different strategies: direct recursion, tail-recursive accumulator, and a fold over a range — then add an idiomatic iterative Rust version for comparison.

🎯 Learning Outcomes

  • • How OCaml tail-call optimisation maps to a simple loop or inner-function recursion in Rust
  • • How List.fold_left over a dummy list translates to (0..n).fold over a range
  • • Why pattern matching on u64 cleanly handles the base cases without if/else
  • • The ergonomic difference between Rust's mutable-local-variable loop and OCaml's accumulator style

    • 🦀 The Rust Way

    Rust mirrors each OCaml variant directly. fib_naive is a straightforward match; fib_tail uses a nested fn go with the same accumulator pattern; fib_fold uses (0..n).fold. A fourth fib_iter variant uses an explicit for loop, which is the most idiomatic Rust style and avoids any stack concerns.

    Code Example

    pub fn fib_iter(n: u64) -> u64 {
    let mut a = 0u64;
    let mut b = 1u64;
    for _ in 0..n {
        let next = a + b;
        a = b;
        b = next;
    }
    a
}

    Key Differences

  • Tail-call optimisation: OCaml guarantees TCO for tail calls; Rust does not, so fib_tail could theoretically overflow for very large n. The iterative fib_iter is the safe Rust default.
  • Fold target: OCaml folds over a List.init n Fun.id dummy list; Rust folds over a 0..n range — no allocation needed.
  • Pattern matching on integers: Both languages support it, but Rust's match arm n => … binds the same variable name, which is clean and identical in structure to OCaml's function clauses.
  • Mutability: fib_iter uses two mut locals, which would be unidiomatic in OCaml; in Rust it is perfectly natural and zero-cost.

    • OCaml Approach

    OCaml uses three styles: naked double recursion (fib_naive), an inner go function that threads accumulator values and is tail-call optimised by the compiler (fib_tail), and a fold over a dummy integer list created with List.init (fib_fold). The tail-recursive version is idiomatic OCaml for linear recursion.

    Full Source

    #![allow(clippy::all)]
// Solution 1: Direct recursion — mirrors OCaml `fib_naive`
// Exponential time; useful only for illustration and small n.
pub fn fib_naive(n: u64) -> u64 {
    match n {
        0 => 0,
        1 => 1,
        n => fib_naive(n - 1) + fib_naive(n - 2),
    }
}

// Solution 2: Tail-recursive with accumulator — mirrors OCaml `fib_tail`
// Linear time, O(1) stack in optimised builds (Rust does not guarantee TCO,
// but the recursion depth is bounded by n which is fine for typical inputs).
pub fn fib_tail(n: u64) -> u64 {
    fn go(a: u64, b: u64, n: u64) -> u64 {
        match n {
            0 => a,
            n => go(b, a + b, n - 1),
        }
    }
    go(0, 1, n)
}

// Solution 3: Fold-based — mirrors OCaml `fib_fold`
// Uses `(0..n).fold` instead of `List.fold_left` on a dummy list.
pub fn fib_fold(n: u64) -> u64 {
    let (a, _) = (0..n).fold((0u64, 1u64), |(a, b), _| (b, a + b));
    a
}

// Solution 4: Idiomatic Rust iterator — explicit state machine
// Most natural Rust style: `Iterator` with internal mutable state.
pub fn fib_iter(n: u64) -> u64 {
    let mut a = 0u64;
    let mut b = 1u64;
    for _ in 0..n {
        let next = a + b;
        a = b;
        b = next;
    }
    a
}

#[cfg(test)]
mod tests {
    use super::*;

    const KNOWN: &[(u64, u64)] = &[(0, 0), (1, 1), (2, 1), (3, 2), (5, 5), (10, 55), (20, 6765)];

    #[test]
    fn test_naive_known_values() {
        for &(n, expected) in KNOWN {
            assert_eq!(fib_naive(n), expected, "fib_naive({n})");
        }
    }

    #[test]
    fn test_tail_known_values() {
        for &(n, expected) in KNOWN {
            assert_eq!(fib_tail(n), expected, "fib_tail({n})");
        }
    }

    #[test]
    fn test_fold_known_values() {
        for &(n, expected) in KNOWN {
            assert_eq!(fib_fold(n), expected, "fib_fold({n})");
        }
    }

    #[test]
    fn test_iter_known_values() {
        for &(n, expected) in KNOWN {
            assert_eq!(fib_iter(n), expected, "fib_iter({n})");
        }
    }

    #[test]
    fn test_all_implementations_agree() {
        for n in 0..=20u64 {
            let expected = fib_naive(n);
            assert_eq!(fib_tail(n), expected, "tail disagrees at {n}");
            assert_eq!(fib_fold(n), expected, "fold disagrees at {n}");
            assert_eq!(fib_iter(n), expected, "iter disagrees at {n}");
        }
    }

    #[test]
    fn test_base_cases() {
        assert_eq!(fib_naive(0), 0);
        assert_eq!(fib_naive(1), 1);
        assert_eq!(fib_tail(0), 0);
        assert_eq!(fib_tail(1), 1);
        assert_eq!(fib_fold(0), 0);
        assert_eq!(fib_fold(1), 1);
        assert_eq!(fib_iter(0), 0);
        assert_eq!(fib_iter(1), 1);
    }

    #[test]
    fn test_larger_value() {
        // fib(30) = 832040
        assert_eq!(fib_tail(30), 832_040);
        assert_eq!(fib_fold(30), 832_040);
        assert_eq!(fib_iter(30), 832_040);
    }
}
    ✓ Tests Rust test suite 
    #[cfg(test)]
mod tests {
    use super::*;

    const KNOWN: &[(u64, u64)] = &[(0, 0), (1, 1), (2, 1), (3, 2), (5, 5), (10, 55), (20, 6765)];

    #[test]
    fn test_naive_known_values() {
        for &(n, expected) in KNOWN {
            assert_eq!(fib_naive(n), expected, "fib_naive({n})");
        }
    }

    #[test]
    fn test_tail_known_values() {
        for &(n, expected) in KNOWN {
            assert_eq!(fib_tail(n), expected, "fib_tail({n})");
        }
    }

    #[test]
    fn test_fold_known_values() {
        for &(n, expected) in KNOWN {
            assert_eq!(fib_fold(n), expected, "fib_fold({n})");
        }
    }

    #[test]
    fn test_iter_known_values() {
        for &(n, expected) in KNOWN {
            assert_eq!(fib_iter(n), expected, "fib_iter({n})");
        }
    }

    #[test]
    fn test_all_implementations_agree() {
        for n in 0..=20u64 {
            let expected = fib_naive(n);
            assert_eq!(fib_tail(n), expected, "tail disagrees at {n}");
            assert_eq!(fib_fold(n), expected, "fold disagrees at {n}");
            assert_eq!(fib_iter(n), expected, "iter disagrees at {n}");
        }
    }

    #[test]
    fn test_base_cases() {
        assert_eq!(fib_naive(0), 0);
        assert_eq!(fib_naive(1), 1);
        assert_eq!(fib_tail(0), 0);
        assert_eq!(fib_tail(1), 1);
        assert_eq!(fib_fold(0), 0);
        assert_eq!(fib_fold(1), 1);
        assert_eq!(fib_iter(0), 0);
        assert_eq!(fib_iter(1), 1);
    }

    #[test]
    fn test_larger_value() {
        // fib(30) = 832040
        assert_eq!(fib_tail(30), 832_040);
        assert_eq!(fib_fold(30), 832_040);
        assert_eq!(fib_iter(30), 832_040);
    }
}

    Deep Comparison

    OCaml vs Rust: Fibonacci Variants

    Side-by-Side Code

    OCaml

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

(* Tail-recursive with accumulator *)
let fib_tail n =
  let rec go a b = function
    | 0 -> a
    | n -> go b (a + b) (n - 1)
  in go 0 1 n

(* Fold-based *)
let fib_fold n =
  let a, _ = List.init n Fun.id
    |> List.fold_left (fun (a, b) _ -> (b, a + b)) (0, 1)
  in a

    Rust (idiomatic — iterative loop)

    pub fn fib_iter(n: u64) -> u64 {
    let mut a = 0u64;
    let mut b = 1u64;
    for _ in 0..n {
        let next = a + b;
        a = b;
        b = next;
    }
    a
}

    Rust (functional/recursive — mirrors OCaml fib_tail)

    pub fn fib_tail(n: u64) -> u64 {
    fn go(a: u64, b: u64, n: u64) -> u64 {
        match n {
            0 => a,
            n => go(b, a + b, n - 1),
        }
    }
    go(0, 1, n)
}

    Rust (fold-based — mirrors OCaml fib_fold)

    pub fn fib_fold(n: u64) -> u64 {
    let (a, _) = (0..n).fold((0u64, 1u64), |(a, b), _| (b, a + b));
    a
}

    Type Signatures

    ConceptOCamlRust
    Naive recursionval fib_naive : int -> intfn fib_naive(n: u64) -> u64
    Tail-recursiveval fib_tail : int -> intfn fib_tail(n: u64) -> u64
    Fold-basedval fib_fold : int -> intfn fib_fold(n: u64) -> u64
    Accumulator state(a, b) threaded through go(a, b) tuple in .fold closure
    Fold inputList.init n Fun.id (dummy list)0..n (range, zero allocation)

    Key Insights

  • Tail-call optimisation: OCaml guarantees TCO; the compiler will turn go b (a+b) (n-1) into a jump. Rust provides no such guarantee, so the recursive fib_tail accumulates stack frames for large n. For safety, fib_iter is preferred in production Rust code.
  • Fold without a list: OCaml's fib_fold creates a dummy list with List.init n Fun.id just to have something to fold over — a common OCaml idiom. Rust avoids allocation entirely by folding over a 0..n range iterator; the semantics are identical but the performance is better.
  • Nested function scope: Both OCaml's let rec go ... in go 0 1 n and Rust's fn go(...) { ... }; go(0, 1, n) use a local helper to hide the accumulator from the public API. The idiom is structurally identical across both languages.
  • Integer type choice: OCaml uses arbitrary-precision integers by default (in practice boxed int). Rust requires an explicit type: u64 is chosen here to handle values up to fib(93) without overflow. For larger inputs a u128 or BigInt crate would be needed.
  • Pattern matching on integers: OCaml function | 0 -> ... | 1 -> ... | n -> ... maps directly to Rust match n { 0 => ..., 1 => ..., n => ... }. Both bind n in the catch-all arm; the structural parallel is exact.

    • When to Use Each Style

    **Use idiomatic Rust (fib_iter) when:** you want safe, stack-overflow-free code for any input size with zero overhead.

    **Use fold-based (fib_fold) when:** you are composing with other iterator adaptors or want a purely expression-oriented style without mutable variables.

    **Use recursive (fib_tail) when:** demonstrating the OCaml accumulator pattern to learners, or when the problem structure is naturally recursive and input is bounded (e.g., ≤ 10 000).

    **Avoid fib_naive in production:** its O(2ⁿ) time complexity makes it unusable for any n > ~35.

    Exercises

  • Implement the Tribonacci sequence (each term is the sum of the three preceding terms) using the same structural techniques as the Fibonacci variants.
  • Implement a generalized_fibonacci that takes an initial pair (a, b) and computes the n-th term, then verify that golden_ratio emerges from fib(n+1) / fib(n) as n grows.
  • Compare the performance of the recursive, memoized, iterative, and matrix-exponentiation Fibonacci variants for computing fib(50) and explain the asymptotic complexity of each.

    • Open Source Repos

    functional-rust

    View the source for this example on GitHub — OCaml and Rust side by side in the repo.

    Rust