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

#![allow(clippy::all)]
// 068: Tail-Recursive Accumulator
// Rust doesn't guarantee TCO — use loops or fold instead

// Approach 1: Recursive vs loop-based sum
fn sum_recursive(v: &[i32]) -> i32 {
    if v.is_empty() {
        0
    } else {
        v[0] + sum_recursive(&v[1..])
    }
}

fn sum_loop(v: &[i32]) -> i32 {
    let mut acc = 0;
    for &x in v {
        acc += x;
    }
    acc
}

fn sum_fold(v: &[i32]) -> i32 {
    v.iter().fold(0, |acc, &x| acc + x)
}

// Approach 2: Factorial
fn fact_recursive(n: u64) -> u64 {
    if n <= 1 {
        1
    } else {
        n * fact_recursive(n - 1)
    }
}

fn fact_loop(n: u64) -> u64 {
    let mut acc = 1u64;
    let mut i = n;
    while i > 1 {
        acc *= i;
        i -= 1;
    }
    acc
}

fn fact_fold(n: u64) -> u64 {
    (1..=n).fold(1, |acc, x| acc * x)
}

// Approach 3: Fibonacci with accumulator loop
fn fib_loop(n: u64) -> u64 {
    let (mut a, mut b) = (0u64, 1u64);
    for _ in 0..n {
        let tmp = a + b;
        a = b;
        b = tmp;
    }
    a
}

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() {
        assert_eq!(sum_recursive(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_loop(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_fold(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_fold(&[]), 0);
    }

    #[test]
    fn test_factorial() {
        assert_eq!(fact_recursive(5), 120);
        assert_eq!(fact_loop(5), 120);
        assert_eq!(fact_fold(5), 120);
        assert_eq!(fact_fold(0), 1);
    }

    #[test]
    fn test_fibonacci() {
        assert_eq!(fib_loop(0), 0);
        assert_eq!(fib_loop(1), 1);
        assert_eq!(fib_loop(10), 55);
        assert_eq!(fib_fold(10), 55);
    }

    #[test]
    fn test_large_input() {
        let large: Vec<i32> = vec![1; 100_000];
        assert_eq!(sum_loop(&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(clippy::all)]
// 068: Tail-Recursive Accumulator
// Rust doesn't guarantee TCO — use loops or fold instead

// Approach 1: Recursive vs loop-based sum
fn sum_recursive(v: &[i32]) -> i32 {
    if v.is_empty() {
        0
    } else {
        v[0] + sum_recursive(&v[1..])
    }
}

fn sum_loop(v: &[i32]) -> i32 {
    let mut acc = 0;
    for &x in v {
        acc += x;
    }
    acc
}

fn sum_fold(v: &[i32]) -> i32 {
    v.iter().fold(0, |acc, &x| acc + x)
}

// Approach 2: Factorial
fn fact_recursive(n: u64) -> u64 {
    if n <= 1 {
        1
    } else {
        n * fact_recursive(n - 1)
    }
}

fn fact_loop(n: u64) -> u64 {
    let mut acc = 1u64;
    let mut i = n;
    while i > 1 {
        acc *= i;
        i -= 1;
    }
    acc
}

fn fact_fold(n: u64) -> u64 {
    (1..=n).fold(1, |acc, x| acc * x)
}

// Approach 3: Fibonacci with accumulator loop
fn fib_loop(n: u64) -> u64 {
    let (mut a, mut b) = (0u64, 1u64);
    for _ in 0..n {
        let tmp = a + b;
        a = b;
        b = tmp;
    }
    a
}

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() {
        assert_eq!(sum_recursive(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_loop(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_fold(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_fold(&[]), 0);
    }

    #[test]
    fn test_factorial() {
        assert_eq!(fact_recursive(5), 120);
        assert_eq!(fact_loop(5), 120);
        assert_eq!(fact_fold(5), 120);
        assert_eq!(fact_fold(0), 1);
    }

    #[test]
    fn test_fibonacci() {
        assert_eq!(fib_loop(0), 0);
        assert_eq!(fib_loop(1), 1);
        assert_eq!(fib_loop(10), 55);
        assert_eq!(fib_fold(10), 55);
    }

    #[test]
    fn test_large_input() {
        let large: Vec<i32> = vec![1; 100_000];
        assert_eq!(sum_loop(&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() {
        assert_eq!(sum_recursive(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_loop(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_fold(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_fold(&[]), 0);
    }

    #[test]
    fn test_factorial() {
        assert_eq!(fact_recursive(5), 120);
        assert_eq!(fact_loop(5), 120);
        assert_eq!(fact_fold(5), 120);
        assert_eq!(fact_fold(0), 1);
    }

    #[test]
    fn test_fibonacci() {
        assert_eq!(fib_loop(0), 0);
        assert_eq!(fib_loop(1), 1);
        assert_eq!(fib_loop(10), 55);
        assert_eq!(fib_fold(10), 55);
    }

    #[test]
    fn test_large_input() {
        let large: Vec<i32> = vec![1; 100_000];
        assert_eq!(sum_loop(&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