ExamplesBy LevelBy TopicLearning Paths
937 Intermediate
← 936938 →

937-tail-recursive-accumulator — Tail-Recursive Accumulator

Functional Programming

Tutorial

The Problem

Naive recursion — sum(list) = head + sum(tail) — builds up a call stack one frame per element. For a list of 100,000 elements, this overflows the stack. The solution is tail recursion: make the recursive call the very last operation, enabling the compiler to reuse the current stack frame (tail-call optimization, TCO). OCaml guarantees TCO for tail-recursive functions. Rust does NOT guarantee TCO — the compiler may or may not optimize it. For stack safety in Rust, idiomatic code uses iterators (.iter().sum()) or explicit loops, which the compiler will never stack-overflow.

🎯 Learning Outcomes

  • • Understand the difference between naive recursion and tail-recursive accumulator style
  • • Recognize that Rust does NOT guarantee tail-call optimization
  • • Use iterators as the idiomatic Rust alternative to TCO-dependent recursion
  • • Implement both OCaml-style accumulator and Rust-idiomatic iterator versions
  • • Compare OCaml's TCO guarantee with Rust's iterator-based stack safety

    • Code Example

    #![allow(clippy::all)]
/// Tail-Recursive Accumulator Pattern
///
/// OCaml relies on tail-call optimization (TCO) for stack safety.
/// Rust does NOT guarantee TCO, so idiomatic Rust uses iterators
/// or explicit loops. We show both styles for comparison.

/// Naive recursive sum — would blow the stack on large inputs in both languages.
pub fn sum_naive(list: &[i64]) -> i64 {
    match list {
        [] => 0,
        [h, rest @ ..] => h + sum_naive(rest),
    }
}

/// Tail-recursive style using an explicit loop (since Rust has no TCO guarantee).
pub fn sum_tr(list: &[i64]) -> i64 {
    let mut acc = 0i64;
    let mut slice = list;
    loop {
        match slice {
            [] => return acc,
            [h, rest @ ..] => {
                acc += h;
                slice = rest;
            }
        }
    }
}

/// Idiomatic Rust: use iterators. This is the preferred approach.
pub fn sum_iter(list: &[i64]) -> i64 {
    list.iter().sum()
}

/// Tail-recursive reverse — process from front, collect into Vec in reverse.
/// OCaml's `h :: acc` prepends; Rust's Vec::insert(0, h) is O(n) per call.
/// We use a VecDeque-style push_front or simply iterate backwards.
pub fn rev_tr<T: Clone>(list: &[T]) -> Vec<T> {
    // Functional accumulator style: fold from left, building reversed result
    list.iter().rev().cloned().collect()
}

/// Explicit recursive version mirroring OCaml's pattern.
pub fn rev_recursive<T: Clone>(list: &[T]) -> Vec<T> {
    fn go<T: Clone>(acc: &mut Vec<T>, slice: &[T]) {
        match slice {
            [] => {}
            [h, rest @ ..] => {
                // In OCaml: h :: acc (prepend). In Rust we build reversed by
                // inserting at front — but that's O(n). Instead we push and
                // the recursion order naturally reverses.
                go(acc, rest);
                acc.push(h.clone());
            }
        }
    }
    let mut result = Vec::new();
    go(&mut result, list);
    result
}

/// Idiomatic Rust reverse.
pub fn rev_iter<T: Clone>(list: &[T]) -> Vec<T> {
    list.iter().rev().cloned().collect()
}

/// Tail-recursive Fibonacci with accumulator.
pub fn fib_tr(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)
}

/// Iterative Fibonacci — idiomatic Rust.
pub fn fib_iter(n: u64) -> u64 {
    let (mut a, mut b) = (0u64, 1u64);
    for _ in 0..n {
        let tmp = a + b;
        a = b;
        b = tmp;
    }
    a
}

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

    #[test]
    fn test_sum() {
        let big: Vec<i64> = (1..=100_000).collect();
        let expected: i64 = 100_000 * 100_001 / 2;
        assert_eq!(sum_tr(&big), expected);
        assert_eq!(sum_iter(&big), expected);
    }

    #[test]
    fn test_sum_empty() {
        assert_eq!(sum_tr(&[]), 0);
        assert_eq!(sum_iter(&[]), 0);
    }

    #[test]
    fn test_rev() {
        assert_eq!(rev_tr(&[1, 2, 3]), vec![3, 2, 1]);
        assert_eq!(rev_recursive(&[1, 2, 3]), vec![3, 2, 1]);
        assert_eq!(rev_tr::<i32>(&[]), Vec::<i32>::new());
    }

    #[test]
    fn test_rev_iter() {
        assert_eq!(rev_iter(&[1, 2, 3]), vec![3, 2, 1]);
        assert_eq!(rev_iter::<i32>(&[]), Vec::<i32>::new());
    }

    #[test]
    fn test_fib() {
        assert_eq!(fib_tr(0), 0);
        assert_eq!(fib_tr(1), 1);
        assert_eq!(fib_tr(10), 55);
        assert_eq!(fib_tr(40), 102334155);
    }

    #[test]
    fn test_fib_iter() {
        assert_eq!(fib_iter(10), 55);
        assert_eq!(fib_iter(40), 102334155);
    }
}

    Key Differences

  • TCO guarantee: OCaml guarantees TCO for tail-recursive functions; Rust has no such guarantee — use iterators instead.
  • Stack safety: OCaml programs can be stack-safe using accumulator-style recursion; Rust programs should use iterators or explicit loops.
  • Fold direction: OCaml List.fold_left is tail-recursive (safe); List.fold_right is not (unsafe for large lists). Rust's .fold() is always O(1) stack.
  • Practical difference: In OCaml, writing tail-recursive functions is a required skill; in Rust, it's rarely necessary because iterator adapters cover all cases.

    • OCaml Approach

    OCaml guarantees TCO for functions where the recursive call is in tail position. sum_tr acc = function | [] -> acc | x :: rest -> sum_tr (acc + x) rest is tail-recursive and stack-safe for any list length. OCaml's List.fold_left f init xs is implemented this way. OCaml's List.fold_right f xs init is NOT tail-recursive (requires explicit rev + fold_left). The distinction between tail and non-tail recursive functions is more practically important in OCaml than in Rust.

    Full Source

    #![allow(clippy::all)]
/// Tail-Recursive Accumulator Pattern
///
/// OCaml relies on tail-call optimization (TCO) for stack safety.
/// Rust does NOT guarantee TCO, so idiomatic Rust uses iterators
/// or explicit loops. We show both styles for comparison.

/// Naive recursive sum — would blow the stack on large inputs in both languages.
pub fn sum_naive(list: &[i64]) -> i64 {
    match list {
        [] => 0,
        [h, rest @ ..] => h + sum_naive(rest),
    }
}

/// Tail-recursive style using an explicit loop (since Rust has no TCO guarantee).
pub fn sum_tr(list: &[i64]) -> i64 {
    let mut acc = 0i64;
    let mut slice = list;
    loop {
        match slice {
            [] => return acc,
            [h, rest @ ..] => {
                acc += h;
                slice = rest;
            }
        }
    }
}

/// Idiomatic Rust: use iterators. This is the preferred approach.
pub fn sum_iter(list: &[i64]) -> i64 {
    list.iter().sum()
}

/// Tail-recursive reverse — process from front, collect into Vec in reverse.
/// OCaml's `h :: acc` prepends; Rust's Vec::insert(0, h) is O(n) per call.
/// We use a VecDeque-style push_front or simply iterate backwards.
pub fn rev_tr<T: Clone>(list: &[T]) -> Vec<T> {
    // Functional accumulator style: fold from left, building reversed result
    list.iter().rev().cloned().collect()
}

/// Explicit recursive version mirroring OCaml's pattern.
pub fn rev_recursive<T: Clone>(list: &[T]) -> Vec<T> {
    fn go<T: Clone>(acc: &mut Vec<T>, slice: &[T]) {
        match slice {
            [] => {}
            [h, rest @ ..] => {
                // In OCaml: h :: acc (prepend). In Rust we build reversed by
                // inserting at front — but that's O(n). Instead we push and
                // the recursion order naturally reverses.
                go(acc, rest);
                acc.push(h.clone());
            }
        }
    }
    let mut result = Vec::new();
    go(&mut result, list);
    result
}

/// Idiomatic Rust reverse.
pub fn rev_iter<T: Clone>(list: &[T]) -> Vec<T> {
    list.iter().rev().cloned().collect()
}

/// Tail-recursive Fibonacci with accumulator.
pub fn fib_tr(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)
}

/// Iterative Fibonacci — idiomatic Rust.
pub fn fib_iter(n: u64) -> u64 {
    let (mut a, mut b) = (0u64, 1u64);
    for _ in 0..n {
        let tmp = a + b;
        a = b;
        b = tmp;
    }
    a
}

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

    #[test]
    fn test_sum() {
        let big: Vec<i64> = (1..=100_000).collect();
        let expected: i64 = 100_000 * 100_001 / 2;
        assert_eq!(sum_tr(&big), expected);
        assert_eq!(sum_iter(&big), expected);
    }

    #[test]
    fn test_sum_empty() {
        assert_eq!(sum_tr(&[]), 0);
        assert_eq!(sum_iter(&[]), 0);
    }

    #[test]
    fn test_rev() {
        assert_eq!(rev_tr(&[1, 2, 3]), vec![3, 2, 1]);
        assert_eq!(rev_recursive(&[1, 2, 3]), vec![3, 2, 1]);
        assert_eq!(rev_tr::<i32>(&[]), Vec::<i32>::new());
    }

    #[test]
    fn test_rev_iter() {
        assert_eq!(rev_iter(&[1, 2, 3]), vec![3, 2, 1]);
        assert_eq!(rev_iter::<i32>(&[]), Vec::<i32>::new());
    }

    #[test]
    fn test_fib() {
        assert_eq!(fib_tr(0), 0);
        assert_eq!(fib_tr(1), 1);
        assert_eq!(fib_tr(10), 55);
        assert_eq!(fib_tr(40), 102334155);
    }

    #[test]
    fn test_fib_iter() {
        assert_eq!(fib_iter(10), 55);
        assert_eq!(fib_iter(40), 102334155);
    }
}
    ✓ Tests Rust test suite 
    #[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_sum() {
        let big: Vec<i64> = (1..=100_000).collect();
        let expected: i64 = 100_000 * 100_001 / 2;
        assert_eq!(sum_tr(&big), expected);
        assert_eq!(sum_iter(&big), expected);
    }

    #[test]
    fn test_sum_empty() {
        assert_eq!(sum_tr(&[]), 0);
        assert_eq!(sum_iter(&[]), 0);
    }

    #[test]
    fn test_rev() {
        assert_eq!(rev_tr(&[1, 2, 3]), vec![3, 2, 1]);
        assert_eq!(rev_recursive(&[1, 2, 3]), vec![3, 2, 1]);
        assert_eq!(rev_tr::<i32>(&[]), Vec::<i32>::new());
    }

    #[test]
    fn test_rev_iter() {
        assert_eq!(rev_iter(&[1, 2, 3]), vec![3, 2, 1]);
        assert_eq!(rev_iter::<i32>(&[]), Vec::<i32>::new());
    }

    #[test]
    fn test_fib() {
        assert_eq!(fib_tr(0), 0);
        assert_eq!(fib_tr(1), 1);
        assert_eq!(fib_tr(10), 55);
        assert_eq!(fib_tr(40), 102334155);
    }

    #[test]
    fn test_fib_iter() {
        assert_eq!(fib_iter(10), 55);
        assert_eq!(fib_iter(40), 102334155);
    }
}

    Deep Comparison

    Tail-Recursive Accumulator Pattern: OCaml vs Rust

    The Core Insight

    This pattern reveals a fundamental philosophical difference: OCaml optimizes recursion (via TCO) to make it as efficient as loops; Rust provides powerful iterators that make loops as expressive as recursion. Both achieve stack safety, but through opposite strategies.

    OCaml Approach

    OCaml guarantees tail-call optimization: if a function's last action is a recursive call, the compiler reuses the current stack frame. The accumulator pattern (let rec go acc = function ...) transforms any linear recursion into tail position. This is essential for processing large lists — without it, sum_naive on 100K elements would overflow the stack. The pattern is so fundamental that OCaml programmers internalize it early.

    Rust Approach

    Rust does NOT guarantee TCO (though LLVM sometimes applies it as an optimization). Instead, idiomatic Rust uses iterators: list.iter().sum() is stack-safe by design because it compiles to a simple loop. The iterator approach is also more composable — you can chain .filter(), .map(), .take() etc. For Fibonacci, a simple for loop with mutable accumulators is clearest. Recursive patterns still work for small inputs or tree structures.

    Side-by-Side

    ConceptOCamlRust
    Stack safetyGuaranteed TCOIterators / loops
    Sumlet rec go acc = function ...iter().sum()
    Reversego (h :: acc) titer().rev().collect()
    Fibonaccigo a b (n-1)for loop with mutation
    Large inputTCO handles itIterators handle it
    StyleRecursion is idiomaticIteration is idiomatic

    What Rust Learners Should Notice

  • • Don't write recursive functions in Rust for linear data — use iterators. They're zero-cost abstractions that compile to the same machine code as hand-written loops
  • • The accumulator pattern is still useful for tree structures where iterators don't naturally apply
  • • Rust's slice patterns ([h, rest @ ..]) are powerful for recursive code but less common than iterator chains
  • • iter().sum() requires the Sum trait — Rust's trait system handles the dispatch
  • • When you see OCaml's tail recursion, think "what iterator chain would express this in Rust?"

    • Further Reading

  • • [The Rust Book — Iterators](https://doc.rust-lang.org/book/ch13-02-iterators.html)
  • • [Cornell CS3110 — Tail Recursion](https://cs3110.github.io/textbook/chapters/data/lists.html)

    • Exercises

  • Implement count_recursive(list: &[i32], pred: impl Fn(&i32) -> bool) -> usize both naively and in accumulator style, and test with a 1M-element input.
  • Write a tail-recursive (loop-based) flatten_recursive<T: Clone>(nested: &[Vec<T>]) -> Vec<T> without using iterator .flatten().
  • Implement map_accumulate<T, U, A, F>(list: &[T], init: A, f: F) -> (Vec<U>, A) that applies a stateful transform to each element using an explicit accumulator.

    • Open Source Repos

    functional-rust

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

    Rust