068 Intermediate GitHub

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

#![allow(dead_code)]
// 068: Tail-Recursive Accumulator
// Transform naive recursion into tail-recursive form by carrying an accumulator.
// Rust does NOT guarantee TCO — `iter().fold()` and explicit loops are the
// idiomatic replacement for accumulator recursion on large inputs.

// --- Sum ---

// Naive: the `+` happens AFTER the recursive call returns, so the call is not
// in tail position. Each frame stays on the stack.
fn sum_naive(v: &[i32]) -> i32 {
    match v {
        [] => 0,
        [x, rest @ ..] => *x + sum_naive(rest),
    }
}

// Tail-recursive: the recursive call is the last operation; the accumulator
// carries the running total forward. Matches the OCaml `aux acc lst` idiom.
fn sum_tail(v: &[i32]) -> i32 {
    fn aux(acc: i32, v: &[i32]) -> i32 {
        match v {
            [] => acc,
            [x, rest @ ..] => aux(acc + *x, rest),
        }
    }
    aux(0, v)
}

// Idiomatic Rust: `.sum()` is the accumulator pattern compiled to a loop —
// stack-safe for any input size.
fn sum_fold(v: &[i32]) -> i32 {
    v.iter().sum()
}

// --- Factorial ---

fn fact_naive(n: u64) -> u64 {
    if n <= 1 {
        1
    } else {
        n * fact_naive(n - 1)
    }
}

fn fact_tail(n: u64) -> u64 {
    fn aux(acc: u64, n: u64) -> u64 {
        if n <= 1 {
            acc
        } else {
            aux(acc * n, n - 1)
        }
    }
    aux(1, n)
}

fn fact_fold(n: u64) -> u64 {
    (1..=n).product()
}

// --- Fibonacci ---

fn fib_naive(n: u64) -> u64 {
    if n <= 1 {
        n
    } else {
        fib_naive(n - 1) + fib_naive(n - 2)
    }
}

// Accumulator recursion: `a` is the current Fibonacci number, `b` is the next.
// Each step shifts the pair forward — O(n) time vs exponential for the naive form.
fn fib_tail(n: u64) -> u64 {
    fn aux(a: u64, b: u64, n: u64) -> u64 {
        if n == 0 {
            a
        } else {
            aux(b, a + b, n - 1)
        }
    }
    aux(0, 1, n)
}

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

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

    #[test]
    fn test_sum_empty() {
        assert_eq!(sum_naive(&[]), 0);
        assert_eq!(sum_tail(&[]), 0);
        assert_eq!(sum_fold(&[]), 0);
    }

    #[test]
    fn test_sum_single() {
        assert_eq!(sum_naive(&[42]), 42);
        assert_eq!(sum_tail(&[42]), 42);
        assert_eq!(sum_fold(&[42]), 42);
    }

    #[test]
    fn test_sum_multiple() {
        assert_eq!(sum_naive(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_tail(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_fold(&[1, 2, 3, 4, 5]), 15);
    }

    #[test]
    fn test_factorial() {
        assert_eq!(fact_naive(0), 1);
        assert_eq!(fact_tail(0), 1);
        assert_eq!(fact_naive(5), 120);
        assert_eq!(fact_tail(5), 120);
        assert_eq!(fact_fold(5), 120);
        assert_eq!(fact_fold(10), 3_628_800);
    }

    #[test]
    fn test_fibonacci() {
        assert_eq!(fib_tail(0), 0);
        assert_eq!(fib_tail(1), 1);
        assert_eq!(fib_tail(10), 55);
        assert_eq!(fib_fold(10), 55);
        assert_eq!(fib_naive(10), 55);
        assert_eq!(fib_tail(50), 12_586_269_025);
    }

    #[test]
    fn test_large_input_fold_is_stack_safe() {
        // `sum_fold` handles 100,000 elements — iterators compile to loops.
        // `sum_tail` would overflow the stack here because Rust does not
        // guarantee tail-call optimisation.
        let large: Vec<i32> = vec![1; 100_000];
        assert_eq!(sum_fold(&large), 100_000);
    }
}

(* 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

#![allow(dead_code)]
// 068: Tail-Recursive Accumulator
// Transform naive recursion into tail-recursive form by carrying an accumulator.
// Rust does NOT guarantee TCO — `iter().fold()` and explicit loops are the
// idiomatic replacement for accumulator recursion on large inputs.

// --- Sum ---

// Naive: the `+` happens AFTER the recursive call returns, so the call is not
// in tail position. Each frame stays on the stack.
fn sum_naive(v: &[i32]) -> i32 {
    match v {
        [] => 0,
        [x, rest @ ..] => *x + sum_naive(rest),
    }
}

// Tail-recursive: the recursive call is the last operation; the accumulator
// carries the running total forward. Matches the OCaml `aux acc lst` idiom.
fn sum_tail(v: &[i32]) -> i32 {
    fn aux(acc: i32, v: &[i32]) -> i32 {
        match v {
            [] => acc,
            [x, rest @ ..] => aux(acc + *x, rest),
        }
    }
    aux(0, v)
}

// Idiomatic Rust: `.sum()` is the accumulator pattern compiled to a loop —
// stack-safe for any input size.
fn sum_fold(v: &[i32]) -> i32 {
    v.iter().sum()
}

// --- Factorial ---

fn fact_naive(n: u64) -> u64 {
    if n <= 1 {
        1
    } else {
        n * fact_naive(n - 1)
    }
}

fn fact_tail(n: u64) -> u64 {
    fn aux(acc: u64, n: u64) -> u64 {
        if n <= 1 {
            acc
        } else {
            aux(acc * n, n - 1)
        }
    }
    aux(1, n)
}

fn fact_fold(n: u64) -> u64 {
    (1..=n).product()
}

// --- Fibonacci ---

fn fib_naive(n: u64) -> u64 {
    if n <= 1 {
        n
    } else {
        fib_naive(n - 1) + fib_naive(n - 2)
    }
}

// Accumulator recursion: `a` is the current Fibonacci number, `b` is the next.
// Each step shifts the pair forward — O(n) time vs exponential for the naive form.
fn fib_tail(n: u64) -> u64 {
    fn aux(a: u64, b: u64, n: u64) -> u64 {
        if n == 0 {
            a
        } else {
            aux(b, a + b, n - 1)
        }
    }
    aux(0, 1, n)
}

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

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

    #[test]
    fn test_sum_empty() {
        assert_eq!(sum_naive(&[]), 0);
        assert_eq!(sum_tail(&[]), 0);
        assert_eq!(sum_fold(&[]), 0);
    }

    #[test]
    fn test_sum_single() {
        assert_eq!(sum_naive(&[42]), 42);
        assert_eq!(sum_tail(&[42]), 42);
        assert_eq!(sum_fold(&[42]), 42);
    }

    #[test]
    fn test_sum_multiple() {
        assert_eq!(sum_naive(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_tail(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_fold(&[1, 2, 3, 4, 5]), 15);
    }

    #[test]
    fn test_factorial() {
        assert_eq!(fact_naive(0), 1);
        assert_eq!(fact_tail(0), 1);
        assert_eq!(fact_naive(5), 120);
        assert_eq!(fact_tail(5), 120);
        assert_eq!(fact_fold(5), 120);
        assert_eq!(fact_fold(10), 3_628_800);
    }

    #[test]
    fn test_fibonacci() {
        assert_eq!(fib_tail(0), 0);
        assert_eq!(fib_tail(1), 1);
        assert_eq!(fib_tail(10), 55);
        assert_eq!(fib_fold(10), 55);
        assert_eq!(fib_naive(10), 55);
        assert_eq!(fib_tail(50), 12_586_269_025);
    }

    #[test]
    fn test_large_input_fold_is_stack_safe() {
        // `sum_fold` handles 100,000 elements — iterators compile to loops.
        // `sum_tail` would overflow the stack here because Rust does not
        // guarantee tail-call optimisation.
        let large: Vec<i32> = vec![1; 100_000];
        assert_eq!(sum_fold(&large), 100_000);
    }
}

(* 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 test_sum_empty() {
        assert_eq!(sum_naive(&[]), 0);
        assert_eq!(sum_tail(&[]), 0);
        assert_eq!(sum_fold(&[]), 0);
    }

    #[test]
    fn test_sum_single() {
        assert_eq!(sum_naive(&[42]), 42);
        assert_eq!(sum_tail(&[42]), 42);
        assert_eq!(sum_fold(&[42]), 42);
    }

    #[test]
    fn test_sum_multiple() {
        assert_eq!(sum_naive(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_tail(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_fold(&[1, 2, 3, 4, 5]), 15);
    }

    #[test]
    fn test_factorial() {
        assert_eq!(fact_naive(0), 1);
        assert_eq!(fact_tail(0), 1);
        assert_eq!(fact_naive(5), 120);
        assert_eq!(fact_tail(5), 120);
        assert_eq!(fact_fold(5), 120);
        assert_eq!(fact_fold(10), 3_628_800);
    }

    #[test]
    fn test_fibonacci() {
        assert_eq!(fib_tail(0), 0);
        assert_eq!(fib_tail(1), 1);
        assert_eq!(fib_tail(10), 55);
        assert_eq!(fib_fold(10), 55);
        assert_eq!(fib_naive(10), 55);
        assert_eq!(fib_tail(50), 12_586_269_025);
    }

    #[test]
    fn test_large_input_fold_is_stack_safe() {
        // `sum_fold` handles 100,000 elements — iterators compile to loops.
        // `sum_tail` would overflow the stack here because Rust does not
        // guarantee tail-call optimisation.
        let large: Vec<i32> = vec![1; 100_000];
        assert_eq!(sum_fold(&large), 100_000);
    }
}

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