511 Intermediate

Recursive Closures and Y Combinator

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Recursive Closures and Y Combinator" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. In lambda calculus, the Y combinator `Y(f) = f(Y(f))` enables recursion without named functions — it passes the function to itself as an argument. Key difference from OCaml: 1. **`let rec` vs. named `fn`**: OCaml's `let rec` makes anonymous recursive closures natural; Rust requires named `fn` for the recursive case.

Tutorial

The Problem

In lambda calculus, the Y combinator Y(f) = f(Y(f)) enables recursion without named functions — it passes the function to itself as an argument. Rust closures are anonymous and cannot capture themselves (they don't exist yet when their body is evaluated). The workarounds are: (1) a named fn (simplest), (2) open recursion — a step(self_, n) function where self_ is the recursive delegate, (3) a struct Y(Box<dyn Fn(&Y, A) -> B>) that passes itself explicitly. These are not just curiosities — they illustrate how recursive computation works at the type level.

🎯 Learning Outcomes

• Understand why closures cannot be self-referential in Rust

• Implement open recursion via a higher-order step function

• Build a Y<A, B> combinator struct with call(&self, arg) -> B

• Implement y_factorial and fib_open using the Y combinator

• Recognise that named functions are always the practical choice for real code

Code Example

// Named recursion is straightforward
fn factorial(n: u64) -> u64 {
    if n <= 1 { 1 } else { n * factorial(n - 1) }
}

// Y combinator needs boxing for type recursion
struct Y<A, B>(Box<dyn Fn(&Y<A, B>, A) -> B>);

(* let rec makes recursion natural *)
let rec factorial n =
  if n <= 1 then 1 else n * factorial (n - 1)

(* Y combinator for fun *)
let y f = (fun x -> f (fun v -> x x v))
          (fun x -> f (fun v -> x x v))

Key Differences

**let rec vs. named fn**: OCaml's let rec makes anonymous recursive closures natural; Rust requires named fn for the recursive case.

Y combinator cost: Rust's Y struct uses Box<dyn Fn> — heap allocation and vtable dispatch per call. OCaml's Y combinator similarly uses indirect dispatch.

Open recursion pattern: Both Rust and OCaml can express open recursion (pass self_ as an argument); OCaml's is syntactically lighter.

Practical recommendation: In both languages, named recursive functions are the right choice for production code; the Y combinator is for learning and theory.

OCaml Approach

OCaml's let rec makes recursive closures trivial:

let rec factorial n = if n <= 1 then 1 else n * factorial (n-1)

(* Y combinator — possible but not idiomatic *)
let y f = (fun x -> f (fun v -> x x v)) (fun x -> f (fun v -> x x v))
let factorial = y (fun self_ n -> if n <= 1 then 1 else n * self_ (n-1))

OCaml's let rec is the normal way; the Y combinator is a theoretical exercise or used when recursion must be abstracted.

Full Source

#![allow(clippy::all)]
//! Recursive Closures (Y Combinator)
//!
//! Techniques for self-referential closures and the Y combinator in Rust.

/// Approach 1: Named recursive function (simplest — always prefer this)
pub fn factorial(n: u64) -> u64 {
    if n <= 1 {
        1
    } else {
        n * factorial(n - 1)
    }
}

/// Approach 2: Open recursion via higher-order function.
/// The step function receives itself as an argument.
pub fn factorial_open<F>(step: F, n: u64) -> u64
where
    F: Fn(&dyn Fn(u64) -> u64, u64) -> u64,
{
    fn apply<F>(step: &F, n: u64) -> u64
    where
        F: Fn(&dyn Fn(u64) -> u64, u64) -> u64,
    {
        step(&|m| apply(step, m), n)
    }
    apply(&step, n)
}

/// Approach 3: Y combinator using Box<dyn Fn>
pub struct Y<A, B>(pub Box<dyn Fn(&Y<A, B>, A) -> B>);

impl<A, B> Y<A, B> {
    pub fn call(&self, arg: A) -> B {
        (self.0)(self, arg)
    }
}

/// Create a Y combinator for factorial.
pub fn y_factorial() -> Y<u64, u64> {
    Y(Box::new(|y, n| if n <= 1 { 1 } else { n * y.call(n - 1) }))
}

/// Fibonacci using open recursion.
pub fn fib_open(n: u64) -> u64 {
    let step = |self_: &dyn Fn(u64) -> u64, n: u64| -> u64 {
        if n <= 1 {
            n
        } else {
            self_(n - 1) + self_(n - 2)
        }
    };
    factorial_open(step, n)
}

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

    #[test]
    fn test_factorial_named() {
        assert_eq!(factorial(0), 1);
        assert_eq!(factorial(1), 1);
        assert_eq!(factorial(5), 120);
        assert_eq!(factorial(10), 3628800);
    }

    #[test]
    fn test_factorial_open() {
        let step = |self_: &dyn Fn(u64) -> u64, n: u64| -> u64 {
            if n <= 1 {
                1
            } else {
                n * self_(n - 1)
            }
        };
        assert_eq!(factorial_open(step, 6), 720);
    }

    #[test]
    fn test_y_factorial() {
        let fact = y_factorial();
        assert_eq!(fact.call(0), 1);
        assert_eq!(fact.call(5), 120);
        assert_eq!(fact.call(6), 720);
    }

    #[test]
    fn test_fib_open() {
        assert_eq!(fib_open(0), 0);
        assert_eq!(fib_open(1), 1);
        assert_eq!(fib_open(10), 55);
    }

    #[test]
    fn test_y_combinator_structure() {
        // Test that Y combinator works for custom function
        let double_until_100 = Y(Box::new(
            |y: &Y<i32, i32>, n: i32| {
                if n >= 100 {
                    n
                } else {
                    y.call(n * 2)
                }
            },
        ));
        assert_eq!(double_until_100.call(1), 128);
    }
}

(* Recursive closures and Y combinator in OCaml *)

(* Natural recursion with let rec *)
let rec factorial n = if n <= 1 then 1 else n * factorial (n - 1)

(* Open recursion: pass self as argument *)
let factorial_open self n = if n <= 1 then 1 else n * self self (n - 1)
let factorial_via_open n = factorial_open factorial_open n

(* Y combinator in OCaml *)
(* Works in OCaml because it has lazy evaluation option or recursive types *)
(* Using explicit recursion trick: *)
let y f =
  let rec x a = f (fun v -> x a v) a in
  x

(* Usage of Y combinator *)
let fact_step self n = if n <= 1 then 1 else n * self (n - 1)
let factorial_y = y fact_step

let () =
  Printf.printf "factorial(5) = %d\n" (factorial 5);
  Printf.printf "factorial_via_open(6) = %d\n" (factorial_via_open 6);
  Printf.printf "factorial_y(7) = %d\n" (factorial_y 7);

  (* Anonymous recursive via Y *)
  let fib = y (fun self n ->
    if n <= 1 then n
    else self (n-1) + self (n-2))
  in
  Printf.printf "fib(10) = %d\n" (fib 10)

✓ Tests Rust test suite

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

    #[test]
    fn test_factorial_named() {
        assert_eq!(factorial(0), 1);
        assert_eq!(factorial(1), 1);
        assert_eq!(factorial(5), 120);
        assert_eq!(factorial(10), 3628800);
    }

    #[test]
    fn test_factorial_open() {
        let step = |self_: &dyn Fn(u64) -> u64, n: u64| -> u64 {
            if n <= 1 {
                1
            } else {
                n * self_(n - 1)
            }
        };
        assert_eq!(factorial_open(step, 6), 720);
    }

    #[test]
    fn test_y_factorial() {
        let fact = y_factorial();
        assert_eq!(fact.call(0), 1);
        assert_eq!(fact.call(5), 120);
        assert_eq!(fact.call(6), 720);
    }

    #[test]
    fn test_fib_open() {
        assert_eq!(fib_open(0), 0);
        assert_eq!(fib_open(1), 1);
        assert_eq!(fib_open(10), 55);
    }

    #[test]
    fn test_y_combinator_structure() {
        // Test that Y combinator works for custom function
        let double_until_100 = Y(Box::new(
            |y: &Y<i32, i32>, n: i32| {
                if n >= 100 {
                    n
                } else {
                    y.call(n * 2)
                }
            },
        ));
        assert_eq!(double_until_100.call(1), 128);
    }
}

Deep Comparison

OCaml vs Rust: Recursive Closures

OCaml

(* let rec makes recursion natural *)
let rec factorial n =
  if n <= 1 then 1 else n * factorial (n - 1)

(* Y combinator for fun *)
let y f = (fun x -> f (fun v -> x x v))
          (fun x -> f (fun v -> x x v))

Rust

// Named recursion is straightforward
fn factorial(n: u64) -> u64 {
    if n <= 1 { 1 } else { n * factorial(n - 1) }
}

// Y combinator needs boxing for type recursion
struct Y<A, B>(Box<dyn Fn(&Y<A, B>, A) -> B>);

Key Differences

OCaml: let rec enables natural recursion

Rust: Named functions recurse naturally; closures need tricks

OCaml: Y combinator is a simple lambda expression

Rust: Y combinator requires Box to break type recursion

Both: Open recursion passes "self" as explicit parameter

Exercises

Fibonacci with Y: Implement Fibonacci via the Y combinator and verify y_fib.call(10) == 55.

Trampolining: Implement a Trampoline<T> enum (Done(T) | More(Box<dyn FnOnce() -> Trampoline<T>>)) to make the Y-combinator stack-safe for large inputs.

Memoised Y: Extend the Y combinator to wrap the recursive step with a HashMap cache — implement memo_y_factorial that uses memoization inside the Y combinator.

Open Source Repos

functional-rust

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

Rust