068 Intermediate

068 — Tail-Recursive Accumulator

Functional Programming

Tutorial

The Problem

Tail recursion optimization (TCO) transforms tail-recursive functions into loops, enabling recursion on large inputs without stack overflow. OCaml guarantees TCO for tail-recursive functions. Rust does not — instead, it encourages using iterators and explicit loops which compile to the same efficient code without TCO guarantees.

Understanding the accumulator pattern — rewriting f(x) = x + f(x-1) into f_acc(x, acc) = f_acc(x-1, acc+x) — is essential for writing stack-safe recursive functions in any language. It is the bridge between mathematical induction and efficient iteration.

🎯 Learning Outcomes

• Understand the difference between naive recursion (not tail-recursive) and accumulator-based recursion (tail-recursive)

• Convert sum([1,2,3,4,5]) from 1 + sum([2,3,4,5]) to sum_acc([2,3,4,5], 1)

• Recognize that Rust's fold is the idiomatic equivalent of a tail-recursive accumulator

• Write both recursive and loop-based versions and verify they produce identical results

• Understand why deep naive recursion causes stack overflow in Rust but not OCaml

• Convert naive recursion to tail-recursive form by passing a growing accumulator forward instead of building the result on the call stack

• Use iter().fold(init, |acc, x| ...) as Rust's idiomatic tail-recursive accumulator — always implemented as a loop

Code Example

//! # Tail-Recursive Accumulator
//!
//! This example demonstrates transforming naive recursion into tail-recursive
//! form using an accumulator. Since Rust does not guarantee tail-call
//! optimisation, the idiomatic replacement for an OCaml tail-recursive helper
//! is usually an iterative loop or a fold over an iterator.
//!
//! For each problem (sum, factorial, Fibonacci) we provide:
//!   * a naive recursive version — clear, but not stack-safe for large inputs;
//!   * an iterative version that mirrors the OCaml `aux acc` pattern;
//!   * a fold-based version that is the most idiomatic Rust translation.
//!
//! All arithmetic operations use checked variants and return [`Option`] so
//! overflow is reported rather than silently wrapping.

/// Naive recursive sum — equivalent to OCaml's `sum_naive`.
///
/// This version recurses once per element and is **not** stack-safe for long
/// slices. It is retained here only to demonstrate the baseline.
pub fn sum_naive(xs: &[i64]) -> i64 {
    match xs.split_first() {
        None => 0,
        Some((head, tail)) => head + sum_naive(tail),
    }
}

/// Iterative sum using an explicit accumulator — the direct translation of
/// OCaml's `sum_tail`.
pub fn sum_tail(xs: &[i64]) -> i64 {
    let mut acc = 0i64;
    for &x in xs {
        acc += x;
    }
    acc
}

/// Fold-based sum — the most idiomatic Rust translation of an accumulator
/// loop. (`xs.iter().sum()` is even shorter, but `fold` makes the
/// accumulator explicit, which is the point of this example.)
#[allow(clippy::unnecessary_fold)]
pub fn sum_fold(xs: &[i64]) -> i64 {
    xs.iter().fold(0, |acc, &x| acc + x)
}

/// Checked sum that returns [`None`] on overflow. This is the preferred API
/// for user-supplied data.
pub fn sum_checked(xs: &[i64]) -> Option<i64> {
    xs.iter().try_fold(0i64, |acc, &x| acc.checked_add(x))
}

/// Naive recursive factorial — equivalent to OCaml's `fact_naive`.
///
/// Returns [`None`] if the result would overflow `u64`.
pub fn fact_naive(n: u64) -> Option<u64> {
    if n <= 1 {
        Some(1)
    } else {
        fact_naive(n - 1).and_then(|sub| sub.checked_mul(n))
    }
}

/// Iterative factorial with an accumulator — direct translation of OCaml's
/// `fact_tail`.
///
/// Returns [`None`] if the result would overflow `u64`.
pub fn fact_tail(n: u64) -> Option<u64> {
    let mut acc: u64 = 1;
    let mut i = n;
    while i > 1 {
        acc = acc.checked_mul(i)?;
        i -= 1;
    }
    Some(acc)
}

/// Fold-based factorial — idiomatic Rust via `try_fold`.
///
/// Returns [`None`] if the result would overflow `u64`.
pub fn fact_fold(n: u64) -> Option<u64> {
    (1..=n).try_fold(1u64, |acc, x| acc.checked_mul(x))
}

/// Naive doubly-recursive Fibonacci — equivalent to OCaml's `fib_naive`.
///
/// Runs in exponential time; use [`fib_tail`] for anything non-trivial.
pub fn fib_naive(n: u64) -> u64 {
    if n <= 1 {
        n
    } else {
        fib_naive(n - 1) + fib_naive(n - 2)
    }
}

/// Iterative Fibonacci carrying the last two values as an accumulator —
/// direct translation of OCaml's `fib_tail`.
///
/// Returns [`None`] if the result would overflow `u64`.
pub fn fib_tail(n: u64) -> Option<u64> {
    let (mut a, mut b): (u64, u64) = (0, 1);
    for _ in 0..n {
        let next = a.checked_add(b)?;
        a = b;
        b = next;
    }
    Some(a)
}

/// Fold-based Fibonacci — idiomatic Rust using `try_fold` over the step
/// count, keeping `(a, b)` as the state.
pub fn fib_fold(n: u64) -> Option<u64> {
    (0..n)
        .try_fold((0u64, 1u64), |(a, b), _| Some((b, a.checked_add(b)?)))
        .map(|(a, _)| a)
}

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

    #[test]
    fn sum_variants_agree_on_small_input() {
        let xs = [1, 2, 3, 4, 5];
        assert_eq!(sum_naive(&xs), 15);
        assert_eq!(sum_tail(&xs), 15);
        assert_eq!(sum_fold(&xs), 15);
        assert_eq!(sum_checked(&xs), Some(15));
    }

    #[test]
    fn sum_of_empty_is_zero() {
        assert_eq!(sum_tail(&[]), 0);
        assert_eq!(sum_fold(&[]), 0);
        assert_eq!(sum_checked(&[]), Some(0));
    }

    #[test]
    fn sum_checked_detects_overflow() {
        assert_eq!(sum_checked(&[i64::MAX, 1]), None);
    }

    #[test]
    fn sum_tail_handles_large_input() {
        let large = vec![1i64; 100_000];
        assert_eq!(sum_tail(&large), 100_000);
        assert_eq!(sum_fold(&large), 100_000);
    }

    #[test]
    fn factorial_small_values() {
        assert_eq!(fact_naive(5), Some(120));
        assert_eq!(fact_tail(5), Some(120));
        assert_eq!(fact_fold(5), Some(120));
        assert_eq!(fact_tail(0), Some(1));
        assert_eq!(fact_tail(1), Some(1));
    }

    #[test]
    fn factorial_overflow_returns_none() {
        // 21! overflows u64 (20! is the largest representable factorial).
        assert!(fact_tail(20).is_some());
        assert_eq!(fact_tail(21), None);
        assert_eq!(fact_fold(100), None);
    }

    #[test]
    fn fibonacci_known_values() {
        let expected = [0u64, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
        for (n, &want) in expected.iter().enumerate() {
            assert_eq!(fib_tail(n as u64), Some(want), "fib_tail({n})");
            assert_eq!(fib_fold(n as u64), Some(want), "fib_fold({n})");
            assert_eq!(fib_naive(n as u64), want, "fib_naive({n})");
        }
    }

    #[test]
    fn fibonacci_overflow_returns_none() {
        // fib(92) is the largest Fibonacci number representable in u64.
        assert!(fib_tail(92).is_some());
        assert_eq!(fib_tail(93), None);
        assert_eq!(fib_fold(200), None);
    }

    #[test]
    fn fib_tail_handles_deep_input() {
        // A naive recursive Fibonacci would take exponential time here; the
        // accumulator version runs in O(n) time and constant stack.
        assert_eq!(fib_tail(90), Some(2_880_067_194_370_816_120));
        assert_eq!(fib_tail(92), Some(7_540_113_804_746_346_429));
    }
}

(* 068: Tail-Recursive Accumulator *)
(* Transform naive recursion into tail-recursive form *)

(* Approach 1: Naive vs tail-recursive sum *)
let rec sum_naive = function
  | [] -> 0
  | x :: xs -> x + sum_naive xs

let sum_tail lst =
  let rec aux acc = function
    | [] -> acc
    | x :: xs -> aux (acc + x) xs
  in
  aux 0 lst

(* Approach 2: Factorial *)
let rec fact_naive n =
  if n <= 1 then 1 else n * fact_naive (n - 1)

let fact_tail n =
  let rec aux acc n =
    if n <= 1 then acc
    else aux (acc * n) (n - 1)
  in
  aux 1 n

(* Approach 3: Fibonacci with accumulator *)
let fib_tail n =
  let rec aux a b n =
    if n = 0 then a
    else aux b (a + b) (n - 1)
  in
  aux 0 1 n

let rec fib_naive n =
  if n <= 1 then n
  else fib_naive (n - 1) + fib_naive (n - 2)

(* Tests *)
let () =
  assert (sum_naive [1; 2; 3; 4; 5] = 15);
  assert (sum_tail [1; 2; 3; 4; 5] = 15);
  assert (sum_tail [] = 0);
  assert (fact_naive 5 = 120);
  assert (fact_tail 5 = 120);
  assert (fact_tail 0 = 1);
  assert (fib_tail 0 = 0);
  assert (fib_tail 1 = 1);
  assert (fib_tail 10 = 55);
  assert (fib_naive 10 = 55);
  (* Tail-recursive can handle large inputs *)
  let large = List.init 100000 (fun _ -> 1) in
  assert (sum_tail large = 100000);
  Printf.printf "✓ All tests passed\n"

Key Differences

TCO guarantee: OCaml guarantees TCO for tail calls. Rust does not — tail-recursive functions in Rust still allocate stack frames. Use fold or explicit loops instead.

**fold = tail recursion**: Rust's iter().fold(init, |acc, x| ...) is exactly the accumulator pattern, compiled to an efficient loop. It is the idiomatic replacement.

Stack overflow: sum_recursive on a 100,000-element slice will likely stack overflow in Rust. OCaml's sum_acc on a 100,000-element list is safe due to TCO.

Mutual recursion: Even in OCaml, mutually recursive tail calls (A calls B, B calls A) are not always optimized. Both languages should use loops for mutual recursion at scale.

TCO in OCaml vs Rust: OCaml guarantees tail-call optimization. A tail-recursive function in OCaml is as stack-efficient as a loop, regardless of input size. Rust does NOT guarantee TCO — Rust's compiler may or may not optimize tail calls. Use loops or fold for large inputs.

Accumulator as explicit loop: The accumulator pattern is equivalent to a while loop with a mutable accumulator variable. Rust often prefers the loop for clarity; OCaml uses the accumulator for immutability.

Difference in fold direction: fold_left with an accumulator processes left-to-right (same order as a loop). fold_right processes right-to-left and is not tail-recursive on linked lists. For sums, the order doesn't matter; for string concatenation, it does.

**iter().fold() as the idiomatic Rust accumulator:** In Rust, slice.iter().fold(init, |acc, x| f(acc, x)) is the idiomatic tail-recursive accumulator — implemented as a loop internally, safe for any input size.

OCaml Approach

OCaml's tail-recursive sum: let rec sum_acc acc = function [] -> acc | x :: t -> sum_acc (acc + x) t. This is guaranteed to be compiled to a loop by OCaml's TCO. The non-tail-recursive let rec sum = function [] -> 0 | x :: t -> x + sum t risks stack overflow for large lists. Idiomatic OCaml always uses the accumulator form for list traversals.

Full Source

//! # Tail-Recursive Accumulator
//!
//! This example demonstrates transforming naive recursion into tail-recursive
//! form using an accumulator. Since Rust does not guarantee tail-call
//! optimisation, the idiomatic replacement for an OCaml tail-recursive helper
//! is usually an iterative loop or a fold over an iterator.
//!
//! For each problem (sum, factorial, Fibonacci) we provide:
//!   * a naive recursive version — clear, but not stack-safe for large inputs;
//!   * an iterative version that mirrors the OCaml `aux acc` pattern;
//!   * a fold-based version that is the most idiomatic Rust translation.
//!
//! All arithmetic operations use checked variants and return [`Option`] so
//! overflow is reported rather than silently wrapping.

/// Naive recursive sum — equivalent to OCaml's `sum_naive`.
///
/// This version recurses once per element and is **not** stack-safe for long
/// slices. It is retained here only to demonstrate the baseline.
pub fn sum_naive(xs: &[i64]) -> i64 {
    match xs.split_first() {
        None => 0,
        Some((head, tail)) => head + sum_naive(tail),
    }
}

/// Iterative sum using an explicit accumulator — the direct translation of
/// OCaml's `sum_tail`.
pub fn sum_tail(xs: &[i64]) -> i64 {
    let mut acc = 0i64;
    for &x in xs {
        acc += x;
    }
    acc
}

/// Fold-based sum — the most idiomatic Rust translation of an accumulator
/// loop. (`xs.iter().sum()` is even shorter, but `fold` makes the
/// accumulator explicit, which is the point of this example.)
#[allow(clippy::unnecessary_fold)]
pub fn sum_fold(xs: &[i64]) -> i64 {
    xs.iter().fold(0, |acc, &x| acc + x)
}

/// Checked sum that returns [`None`] on overflow. This is the preferred API
/// for user-supplied data.
pub fn sum_checked(xs: &[i64]) -> Option<i64> {
    xs.iter().try_fold(0i64, |acc, &x| acc.checked_add(x))
}

/// Naive recursive factorial — equivalent to OCaml's `fact_naive`.
///
/// Returns [`None`] if the result would overflow `u64`.
pub fn fact_naive(n: u64) -> Option<u64> {
    if n <= 1 {
        Some(1)
    } else {
        fact_naive(n - 1).and_then(|sub| sub.checked_mul(n))
    }
}

/// Iterative factorial with an accumulator — direct translation of OCaml's
/// `fact_tail`.
///
/// Returns [`None`] if the result would overflow `u64`.
pub fn fact_tail(n: u64) -> Option<u64> {
    let mut acc: u64 = 1;
    let mut i = n;
    while i > 1 {
        acc = acc.checked_mul(i)?;
        i -= 1;
    }
    Some(acc)
}

/// Fold-based factorial — idiomatic Rust via `try_fold`.
///
/// Returns [`None`] if the result would overflow `u64`.
pub fn fact_fold(n: u64) -> Option<u64> {
    (1..=n).try_fold(1u64, |acc, x| acc.checked_mul(x))
}

/// Naive doubly-recursive Fibonacci — equivalent to OCaml's `fib_naive`.
///
/// Runs in exponential time; use [`fib_tail`] for anything non-trivial.
pub fn fib_naive(n: u64) -> u64 {
    if n <= 1 {
        n
    } else {
        fib_naive(n - 1) + fib_naive(n - 2)
    }
}

/// Iterative Fibonacci carrying the last two values as an accumulator —
/// direct translation of OCaml's `fib_tail`.
///
/// Returns [`None`] if the result would overflow `u64`.
pub fn fib_tail(n: u64) -> Option<u64> {
    let (mut a, mut b): (u64, u64) = (0, 1);
    for _ in 0..n {
        let next = a.checked_add(b)?;
        a = b;
        b = next;
    }
    Some(a)
}

/// Fold-based Fibonacci — idiomatic Rust using `try_fold` over the step
/// count, keeping `(a, b)` as the state.
pub fn fib_fold(n: u64) -> Option<u64> {
    (0..n)
        .try_fold((0u64, 1u64), |(a, b), _| Some((b, a.checked_add(b)?)))
        .map(|(a, _)| a)
}

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

    #[test]
    fn sum_variants_agree_on_small_input() {
        let xs = [1, 2, 3, 4, 5];
        assert_eq!(sum_naive(&xs), 15);
        assert_eq!(sum_tail(&xs), 15);
        assert_eq!(sum_fold(&xs), 15);
        assert_eq!(sum_checked(&xs), Some(15));
    }

    #[test]
    fn sum_of_empty_is_zero() {
        assert_eq!(sum_tail(&[]), 0);
        assert_eq!(sum_fold(&[]), 0);
        assert_eq!(sum_checked(&[]), Some(0));
    }

    #[test]
    fn sum_checked_detects_overflow() {
        assert_eq!(sum_checked(&[i64::MAX, 1]), None);
    }

    #[test]
    fn sum_tail_handles_large_input() {
        let large = vec![1i64; 100_000];
        assert_eq!(sum_tail(&large), 100_000);
        assert_eq!(sum_fold(&large), 100_000);
    }

    #[test]
    fn factorial_small_values() {
        assert_eq!(fact_naive(5), Some(120));
        assert_eq!(fact_tail(5), Some(120));
        assert_eq!(fact_fold(5), Some(120));
        assert_eq!(fact_tail(0), Some(1));
        assert_eq!(fact_tail(1), Some(1));
    }

    #[test]
    fn factorial_overflow_returns_none() {
        // 21! overflows u64 (20! is the largest representable factorial).
        assert!(fact_tail(20).is_some());
        assert_eq!(fact_tail(21), None);
        assert_eq!(fact_fold(100), None);
    }

    #[test]
    fn fibonacci_known_values() {
        let expected = [0u64, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
        for (n, &want) in expected.iter().enumerate() {
            assert_eq!(fib_tail(n as u64), Some(want), "fib_tail({n})");
            assert_eq!(fib_fold(n as u64), Some(want), "fib_fold({n})");
            assert_eq!(fib_naive(n as u64), want, "fib_naive({n})");
        }
    }

    #[test]
    fn fibonacci_overflow_returns_none() {
        // fib(92) is the largest Fibonacci number representable in u64.
        assert!(fib_tail(92).is_some());
        assert_eq!(fib_tail(93), None);
        assert_eq!(fib_fold(200), None);
    }

    #[test]
    fn fib_tail_handles_deep_input() {
        // A naive recursive Fibonacci would take exponential time here; the
        // accumulator version runs in O(n) time and constant stack.
        assert_eq!(fib_tail(90), Some(2_880_067_194_370_816_120));
        assert_eq!(fib_tail(92), Some(7_540_113_804_746_346_429));
    }
}

(* 068: Tail-Recursive Accumulator *)
(* Transform naive recursion into tail-recursive form *)

(* Approach 1: Naive vs tail-recursive sum *)
let rec sum_naive = function
  | [] -> 0
  | x :: xs -> x + sum_naive xs

let sum_tail lst =
  let rec aux acc = function
    | [] -> acc
    | x :: xs -> aux (acc + x) xs
  in
  aux 0 lst

(* Approach 2: Factorial *)
let rec fact_naive n =
  if n <= 1 then 1 else n * fact_naive (n - 1)

let fact_tail n =
  let rec aux acc n =
    if n <= 1 then acc
    else aux (acc * n) (n - 1)
  in
  aux 1 n

(* Approach 3: Fibonacci with accumulator *)
let fib_tail n =
  let rec aux a b n =
    if n = 0 then a
    else aux b (a + b) (n - 1)
  in
  aux 0 1 n

let rec fib_naive n =
  if n <= 1 then n
  else fib_naive (n - 1) + fib_naive (n - 2)

(* Tests *)
let () =
  assert (sum_naive [1; 2; 3; 4; 5] = 15);
  assert (sum_tail [1; 2; 3; 4; 5] = 15);
  assert (sum_tail [] = 0);
  assert (fact_naive 5 = 120);
  assert (fact_tail 5 = 120);
  assert (fact_tail 0 = 1);
  assert (fib_tail 0 = 0);
  assert (fib_tail 1 = 1);
  assert (fib_tail 10 = 55);
  assert (fib_naive 10 = 55);
  (* Tail-recursive can handle large inputs *)
  let large = List.init 100000 (fun _ -> 1) in
  assert (sum_tail large = 100000);
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn sum_variants_agree_on_small_input() {
        let xs = [1, 2, 3, 4, 5];
        assert_eq!(sum_naive(&xs), 15);
        assert_eq!(sum_tail(&xs), 15);
        assert_eq!(sum_fold(&xs), 15);
        assert_eq!(sum_checked(&xs), Some(15));
    }

    #[test]
    fn sum_of_empty_is_zero() {
        assert_eq!(sum_tail(&[]), 0);
        assert_eq!(sum_fold(&[]), 0);
        assert_eq!(sum_checked(&[]), Some(0));
    }

    #[test]
    fn sum_checked_detects_overflow() {
        assert_eq!(sum_checked(&[i64::MAX, 1]), None);
    }

    #[test]
    fn sum_tail_handles_large_input() {
        let large = vec![1i64; 100_000];
        assert_eq!(sum_tail(&large), 100_000);
        assert_eq!(sum_fold(&large), 100_000);
    }

    #[test]
    fn factorial_small_values() {
        assert_eq!(fact_naive(5), Some(120));
        assert_eq!(fact_tail(5), Some(120));
        assert_eq!(fact_fold(5), Some(120));
        assert_eq!(fact_tail(0), Some(1));
        assert_eq!(fact_tail(1), Some(1));
    }

    #[test]
    fn factorial_overflow_returns_none() {
        // 21! overflows u64 (20! is the largest representable factorial).
        assert!(fact_tail(20).is_some());
        assert_eq!(fact_tail(21), None);
        assert_eq!(fact_fold(100), None);
    }

    #[test]
    fn fibonacci_known_values() {
        let expected = [0u64, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
        for (n, &want) in expected.iter().enumerate() {
            assert_eq!(fib_tail(n as u64), Some(want), "fib_tail({n})");
            assert_eq!(fib_fold(n as u64), Some(want), "fib_fold({n})");
            assert_eq!(fib_naive(n as u64), want, "fib_naive({n})");
        }
    }

    #[test]
    fn fibonacci_overflow_returns_none() {
        // fib(92) is the largest Fibonacci number representable in u64.
        assert!(fib_tail(92).is_some());
        assert_eq!(fib_tail(93), None);
        assert_eq!(fib_fold(200), None);
    }

    #[test]
    fn fib_tail_handles_deep_input() {
        // A naive recursive Fibonacci would take exponential time here; the
        // accumulator version runs in O(n) time and constant stack.
        assert_eq!(fib_tail(90), Some(2_880_067_194_370_816_120));
        assert_eq!(fib_tail(92), Some(7_540_113_804_746_346_429));
    }
}

Deep Comparison

Core Insight

Tail recursion with an accumulator prevents stack overflow for large inputs. OCaml guarantees tail-call optimization. Rust does NOT guarantee TCO, making explicit loops the idiomatic replacement.

OCaml Approach

• Naive: let rec sum = function [] -> 0 | x::xs -> x + sum xs

• Tail-recursive: let rec aux acc = function [] -> acc | x::xs -> aux (acc+x) xs

• TCO guaranteed by the compiler

Rust Approach

• Recursive version works but may overflow stack

• Idiomatic: iter().fold() or explicit loop

• No guaranteed TCO in Rust

Comparison Table

Feature	OCaml	Rust
TCO guaranteed	Yes	No
Accumulator pattern	`aux acc rest`	loop + mutable acc
Idiomatic	Tail recursion	`.fold()` or `for` loop
Stack overflow risk	No (with TCO)	Yes (with recursion)

Exercises

Fibonacci with accumulator: Write fib_acc(n: u64, a: u64, b: u64) -> u64 where a and b carry the last two Fibonacci numbers. Verify it does not overflow for n=100 (use u128).

Flatten accumulator: Write flatten_acc<T: Clone>(lists: &[Vec<T>], acc: Vec<T>) -> Vec<T> that flattens nested lists using an accumulator. Compare with iter().flatten().collect().

CPS transformation: Transform sum_recursive into continuation-passing style (CPS): sum_cps(v: &[i32], k: impl Fn(i32) -> i32) -> i32. This makes any recursion tail-recursive.

Tail-recursive flatten: Implement flatten_acc<T: Clone>(nested: &[Vec<T>], acc: Vec<T>) -> Vec<T> that flattens a list of lists using an accumulator — pass the accumulator forward rather than appending on the way back.

CPS transform: Convert a non-tail-recursive function to continuation-passing style (CPS): factorial_cps(n: u64, k: impl FnOnce(u64) -> u64) -> u64. The CPS form is always tail-recursive. Call it with factorial_cps(5, |x| x) to get the result.

Open Source Repos

functional-rust

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

Rust