936 Fundamental

936-mutual-recursion — Mutual Recursion

Functional Programming

Tutorial

The Problem

Mutually recursive functions call each other: is_even(n) = (n == 0) || is_odd(n-1) and is_odd(n) = (n != 0) && is_even(n-1). Neither function can be defined in terms of only itself; they require simultaneous definition. In OCaml, let rec is_even n = ... and is_odd n = ... uses and to co-define them. Rust does not need special syntax — any two functions in the same module can call each other freely since function names are resolved at link time, not at definition time. This difference reveals a fundamental design choice between definition-order-sensitive and definition-order-free languages.

🎯 Learning Outcomes

• Implement mutually recursive functions in Rust without special syntax

• Understand why OCaml requires let rec ... and ... while Rust does not

• Apply mutual recursion to expression tree evaluation with multiple constructors

• Recognize when mutual recursion clarifies problem structure vs when a single recursive function suffices

• Compare Rust's implicit mutual recursion support with OCaml's explicit and keyword

Code Example

#![allow(clippy::all)]
/// 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));
    }
}

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."

Key Differences

Syntax: OCaml requires explicit let rec ... and ... for mutual recursion; Rust uses ordinary fn with no special syntax.

Definition order: OCaml is definition-order-sensitive — forward references require and; Rust resolves names globally within the module regardless of definition order.

Type co-definition: OCaml type a = ... and b = ... for mutually recursive types; Rust allows struct A { b: Box<B> } followed by struct B { a: Box<A> } in any order.

Clarity: OCaml's explicit and documents mutual dependencies; Rust's approach requires reading both functions to discover the mutual dependency.

OCaml Approach

OCaml requires let rec is_even n = ... and is_odd n = ... because OCaml processes definitions sequentially. Without and, is_odd is not in scope when is_even is defined. let rec ... and ... co-defines both simultaneously. This makes the mutual dependency explicit and machine-verifiable. For type definitions: type even_tree = Even | ENode of odd_tree and odd_tree = Odd | ONode of even_tree works similarly. The and keyword appears for both let rec and type co-definitions.

Full Source

#![allow(clippy::all)]
/// 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));
    }
}

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."

✓ Tests Rust test suite

#[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));
    }
}

Deep 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

Exercises

Implement a mutual recursive descent parser for arithmetic with parse_expr, parse_term, and parse_factor functions.

Write mutually recursive is_even_count(list: &[i32]) -> bool and is_odd_count(list: &[i32]) -> bool that check parity of the list length.

Define a mutually recursive type JsonLike = Null | Bool(bool) | Num(f64) | Arr(Vec<JsonLike>) | Obj(Vec<(String, JsonLike)>) and implement a depth-counting function.

Open Source Repos

functional-rust

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

Rust

Tutorial

The Problem

🎯 Learning Outcomes

Code Example

Key Differences

OCaml Approach

Full Source

Deep Comparison

Mutual Recursion with and: OCaml vs Rust

The Core Insight

OCaml Approach

Rust Approach

Side-by-Side

What Rust Learners Should Notice

Further Reading

Exercises

Open Source Repos

Mutual Recursion with `and`: OCaml vs Rust