067: Mutual Recursion

Difficulty: 1 Level: Beginner Two functions that call each other — Rust handles it naturally, OCaml needs the `and` keyword.

The Problem This Solves

Some algorithms are most naturally expressed as two functions that call each other. The classic example: `is_even(n)` returns true if `n == 0`, otherwise delegates to `is_odd(n - 1)`. And `is_odd(n)` returns false if `n == 0`, otherwise delegates to `is_even(n - 1)`. Neither function can be defined without the other. More practically: an expression evaluator might have `eval_expr` that handles addition and multiplication, and `eval_mul` that handles a special case of multiplication with additional logic. They call each other. Or a parser might have `parse_expr` calling `parse_term` and `parse_term` calling `parse_factor` calling back into `parse_expr` for grouped expressions. OCaml requires explicit syntax (`let rec ... and ...`) to co-define mutually recursive functions because definitions are processed sequentially. Understanding this difference helps you reason about when forward declarations matter and why Rust doesn't need them.

The Intuition

Mutual recursion means two (or more) functions form a cycle in their call graph: A calls B, and B calls A. In OCaml, the compiler processes definitions top-to-bottom. If you write `let is_even` first, then `let is_odd`, the body of `is_even` can't reference `is_odd` because it hasn't been defined yet. The `and` keyword co-defines them simultaneously: `let rec is_even = ... and is_odd = ...`. In Rust, all items (functions, structs, impl blocks) in a module are visible to each other regardless of order. The compiler does a full pass over all items before resolving names. So `is_even` can call `is_odd` even if `is_odd` is defined further down the file. No special syntax needed. Stack depth warning: the naive mutual recursion for `is_even(1_000_000)` would make 1,000,000 recursive calls and overflow the stack. For deep recursion, use the iterative version: `n % 2 == 0`. Or use a trampoline (see the tail-recursive accumulator example 068 for the pattern).

How It Works in Rust

// No special syntax needed — these two functions can call each other freely
pub fn is_even(n: u32) -> bool {
 match n {
     0 => true,
     n => is_odd(n - 1),   // calls is_odd — defined below, that's fine
 }
}

pub fn is_odd(n: u32) -> bool {
 match n {
     0 => false,
     n => is_even(n - 1),  // calls is_even — defined above, also fine
 }
}

For production use (avoids stack overflow):

pub fn is_even_iter(n: u32) -> bool { n % 2 == 0 }

Mutual recursion over algebraic data types — an expression evaluator where `eval_expr` and `eval_mul` call each other:

pub fn eval_expr(e: &Expr) -> i32 {
 match e {
     Expr::Lit(n) => *n,
     Expr::Add(l, r) => eval_expr(l) + eval_expr(r),
     Expr::Mul(l, r) => eval_mul(l, r),   // delegate to specialized handler
 }
}

fn eval_mul(l: &Expr, r: &Expr) -> i32 {
 eval_expr(l) * eval_expr(r)   // calls back into eval_expr
}

This pattern is common when you want to separate concerns within a recursive evaluator — different arms of the match delegate to different helpers, and those helpers may recurse back to the main function.

What This Unlocks

Recursive descent parsers: `parse_expr` → `parse_term` → `parse_factor` → `parse_expr` forms a natural mutual recursion that mirrors the grammar.
State machines: `state_a` transitions to `state_b`, `state_b` transitions to `state_a` — mutual recursion models the cycle directly.
Separation of concerns in evaluators: split a large `eval` match into specialized helpers that can call back into `eval` for recursive cases.

Key Differences

Concept	OCaml	Rust
Mutual recursion syntax	`let rec f = ... and g = ...` — required	No special syntax — functions see each other automatically
Why the difference	Definitions processed top-to-bottom	All module items resolved in one pass
Stack safety	Same risk of overflow	Same; neither guarantees TCO for mutual recursion
Trampoline	Manual or via continuation	Manual; same pattern (see example 068)

/// Mutual Recursion with `and`
///
/// OCaml uses `let rec ... and ...` for mutually recursive functions.
/// Rust doesn't need special syntax — functions can call each other
/// freely as long as they're in scope. The compiler handles it.

/// Mutually recursive even/odd check.
/// In OCaml, these require `and` to co-define them.
/// In Rust, mutual recursion "just works" — no special syntax needed.
pub fn is_even(n: u32) -> bool {
    match n {
        0 => true,
        n => is_odd(n - 1),
    }
}

pub fn is_odd(n: u32) -> bool {
    match n {
        0 => false,
        n => is_even(n - 1),
    }
}

/// Expression tree with mutual recursion over variants.
#[derive(Debug, Clone)]
pub enum Expr {
    Lit(i32),
    Add(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
}

impl Expr {
    pub fn lit(n: i32) -> Self { Expr::Lit(n) }
    pub fn add(l: Expr, r: Expr) -> Self { Expr::Add(Box::new(l), Box::new(r)) }
    pub fn mul(l: Expr, r: Expr) -> Self { Expr::Mul(Box::new(l), Box::new(r)) }
}

pub fn eval_expr(e: &Expr) -> i32 {
    match e {
        Expr::Lit(n) => *n,
        Expr::Add(l, r) => eval_expr(l) + eval_expr(r),
        Expr::Mul(l, r) => eval_mul(l, r),
    }
}

fn eval_mul(l: &Expr, r: &Expr) -> i32 {
    eval_expr(l) * eval_expr(r)
}

/// Iterative is_even — avoids stack overflow for large n.
pub fn is_even_iter(n: u32) -> bool {
    n % 2 == 0
}

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

    #[test]
    fn test_is_even() {
        assert!(is_even(4));
        assert!(!is_even(7));
        assert!(is_even(0));
    }

    #[test]
    fn test_is_odd() {
        assert!(is_odd(7));
        assert!(!is_odd(4));
        assert!(!is_odd(0));
    }

    #[test]
    fn test_eval_expr() {
        // (2 + 3) * 4 = 20
        let e = Expr::mul(Expr::add(Expr::lit(2), Expr::lit(3)), Expr::lit(4));
        assert_eq!(eval_expr(&e), 20);
    }

    #[test]
    fn test_eval_simple() {
        assert_eq!(eval_expr(&Expr::lit(42)), 42);
        assert_eq!(eval_expr(&Expr::add(Expr::lit(1), Expr::lit(2))), 3);
    }

    #[test]
    fn test_nested_expr() {
        // (1 + 2) * (3 + 4) = 21
        let e = Expr::mul(
            Expr::add(Expr::lit(1), Expr::lit(2)),
            Expr::add(Expr::lit(3), Expr::lit(4)),
        );
        assert_eq!(eval_expr(&e), 21);
    }

    #[test]
    fn test_is_even_iter() {
        assert!(is_even_iter(100));
        assert!(!is_even_iter(101));
    }
}

fn main() {
    println!("{:?}", is_even(4));
    println!("{:?}", !is_even(7));
    println!("{:?}", is_even(0));
}

let rec is_even = function
  | 0 -> true
  | n -> is_odd (n - 1)
and     is_odd = function
  | 0 -> false
  | n -> is_even (n - 1)

type expr =
  | Lit of int
  | Add of expr * expr
  | Mul of expr * expr

let rec eval_expr = function
  | Lit n      -> n
  | Add (l, r) -> eval_expr l + eval_expr r
  | Mul (l, r) -> eval_mul l r
and eval_mul l r =
  eval_expr l * eval_expr r

let () =
  assert (is_even 4 = true);
  assert (is_odd 7 = true);
  assert (is_even 0 = true);
  let e = Mul (Add (Lit 2, Lit 3), Lit 4) in
  assert (eval_expr e = 20);
  print_endline "All assertions passed."

📊 Detailed Comparison

Mutual Recursion with `and`: OCaml vs Rust

The Core Insight

Mutual recursion — functions that call each other — highlights a fundamental difference in how the two languages handle name resolution. OCaml processes definitions sequentially and needs explicit `and` to co-define functions; Rust resolves all items in a scope simultaneously, making mutual recursion invisible at the syntax level.

OCaml Approach

OCaml's `let rec is_even = ... and is_odd = ...` explicitly tells the compiler that these functions are defined together and may reference each other. Without `and`, `is_odd` wouldn't be in scope when `is_even` is compiled. The same `and` keyword works for mutually recursive types and modules. This sequential processing is a deliberate design choice that makes code easier to reason about locally.

Rust Approach

In Rust, all items (functions, types, traits) within a module are visible to each other regardless of definition order. `is_even` can call `is_odd` and vice versa with no special syntax. This is because Rust separates name resolution from compilation — it first collects all names, then type-checks. For the expression evaluator, `eval_expr` and `eval_mul` call each other naturally.

Side-by-Side

Concept	OCaml	Rust
Mutual recursion	`let rec ... and ...`	No special syntax needed
Name resolution	Sequential (top-down)	All items visible simultaneously
Recursive types	`type ... and ...`	Enums reference each other freely
Forward reference	Not allowed without `and`	Always allowed within module
Stack safety	No guaranteed TCO	No guaranteed TCO (use iteration)

What Rust Learners Should Notice

Rust's "all items visible" approach means you never need forward declarations for functions — a big ergonomic win
However, `let` bindings within a function body ARE sequential (like OCaml's `let`) — only module-level items are mutually visible
Neither language guarantees tail-call optimization, so deep mutual recursion (e.g., `is_even(1_000_000)`) can overflow the stack
The expression evaluator pattern (enum + match + mutual functions) is extremely common in interpreters and compilers — both languages excel at this
Rust's `Box::new` for recursive enum variants is the main additional cost compared to OCaml's GC-managed types