333 Advanced

333: Async Recursion

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "333: Async Recursion" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Recursive async functions have a fundamental problem: the compiler needs to know the future's size at compile time to allocate it on the stack. Key difference from OCaml: 1. **Explicit boxing**: Rust requires explicit `Box::pin` for recursive futures; OCaml's closures are always on the heap.

Tutorial

The Problem

Recursive async functions have a fundamental problem: the compiler needs to know the future's size at compile time to allocate it on the stack. A recursive async function has an infinitely-nested type (each recursive call adds another layer of future type). The solution is Box::pin() — heap-allocating the future and using a type alias BoxFuture<'a, T> to break the recursive type definition. This is the standard pattern for tree traversals and parser combinators in async Rust.

🎯 Learning Outcomes

• Understand why recursive async fn requires Box::pin — infinite type recursion

• Use BoxFuture<'a, T> = Pin<Box<dyn Future<Output = T> + 'a>> as the return type

• Implement recursive async tree operations using Box::pin(async move { ... })

• Recognize the performance cost: each recursive call allocates a heap-pinned future

Code Example

fn async_sum(t: &Tree) -> BoxFuture<'_, i64> {
    Box::pin(async move {
        match t {
            Tree::Leaf => 0,
            Tree::Node{value,left,right} =>
                *value as i64 + async_sum(left).await + async_sum(right).await,
        }
    })
}

let rec sum_tree = function
  | Leaf -> 0
  | Node { value; left; right } -> value + sum_tree left + sum_tree right

Key Differences

Explicit boxing: Rust requires explicit Box::pin for recursive futures; OCaml's closures are always on the heap.

async-recursion crate: The async-recursion crate provides #[async_recursion] macro that generates the Box::pin boilerplate automatically.

Allocation cost: Each recursive level allocates a heap future; for very deep recursion, this adds GC pressure (Rust) or risk of stack overflow (OCaml).

Pattern: BoxFuture<'a, T> is the standard type alias for any dynamically-dispatched future — used throughout async-trait and similar crates.

OCaml Approach

OCaml's Lwt recursive functions don't require boxing — closures are always heap-allocated:

let rec sum_tree = function
  | Leaf -> Lwt.return 0
  | Node { value; left; right } ->
    let* l = sum_tree left in
    let* r = sum_tree right in
    Lwt.return (value + l + r)

OCaml closures naturally handle recursive types without explicit boxing.

Full Source

#![allow(clippy::all)]
//! # Async Recursion
//!
//! Recursive async functions need `Box::pin` — the future's size must be known at compile time.

use std::future::Future;
use std::pin::Pin;
use std::task::{Context, Poll, RawWaker, RawWakerVTable, Waker};

/// Type alias for a heap-pinned future with lifetime 'a.
pub type BoxFuture<'a, T> = Pin<Box<dyn Future<Output = T> + 'a>>;

/// A binary tree for demonstrating recursive async operations.
#[derive(Debug, Clone)]
pub enum Tree<T> {
    Leaf,
    Node {
        value: T,
        left: Box<Tree<T>>,
        right: Box<Tree<T>>,
    },
}

impl<T> Tree<T> {
    pub fn leaf() -> Box<Self> {
        Box::new(Self::Leaf)
    }

    pub fn node(value: T, left: Box<Self>, right: Box<Self>) -> Box<Self> {
        Box::new(Self::Node { value, left, right })
    }
}

impl Tree<i32> {
    /// Create a sample tree for testing.
    pub fn sample() -> Box<Self> {
        //       1
        //      / \
        //     2   3
        //    / \   \
        //   4   5   6
        Self::node(
            1,
            Self::node(
                2,
                Self::node(4, Self::leaf(), Self::leaf()),
                Self::node(5, Self::leaf(), Self::leaf()),
            ),
            Self::node(3, Self::node(6, Self::leaf(), Self::leaf()), Self::leaf()),
        )
    }
}

/// Async sum of all values in the tree (recursive, uses Box::pin).
pub fn async_sum(tree: &Tree<i32>) -> BoxFuture<'_, i64> {
    Box::pin(async move {
        match tree {
            Tree::Leaf => 0,
            Tree::Node { value, left, right } => {
                *value as i64 + async_sum(left).await + async_sum(right).await
            }
        }
    })
}

/// Async depth calculation (recursive).
pub fn async_depth<T>(tree: &Tree<T>) -> BoxFuture<'_, usize> {
    Box::pin(async move {
        match tree {
            Tree::Leaf => 0,
            Tree::Node { left, right, .. } => {
                1 + async_depth(left).await.max(async_depth(right).await)
            }
        }
    })
}

/// Async count of nodes (recursive).
pub fn async_count<T>(tree: &Tree<T>) -> BoxFuture<'_, usize> {
    Box::pin(async move {
        match tree {
            Tree::Leaf => 0,
            Tree::Node { left, right, .. } => {
                1 + async_count(left).await + async_count(right).await
            }
        }
    })
}

/// A minimal single-threaded executor for running futures.
pub fn block_on<F: Future>(fut: F) -> F::Output {
    unsafe fn clone_waker(ptr: *const ()) -> RawWaker {
        RawWaker::new(ptr, &VTABLE)
    }
    unsafe fn noop(_: *const ()) {}

    static VTABLE: RawWakerVTable = RawWakerVTable::new(clone_waker, noop, noop, noop);

    let waker = unsafe { Waker::from_raw(RawWaker::new(std::ptr::null(), &VTABLE)) };
    let mut cx = Context::from_waker(&waker);
    let mut fut = Box::pin(fut);

    loop {
        if let Poll::Ready(value) = fut.as_mut().poll(&mut cx) {
            return value;
        }
    }
}

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

    #[test]
    fn test_leaf_sum_is_zero() {
        assert_eq!(block_on(async_sum(&Tree::Leaf)), 0);
    }

    #[test]
    fn test_sample_tree_sum() {
        let tree = Tree::sample();
        assert_eq!(block_on(async_sum(&tree)), 21); // 1+2+3+4+5+6 = 21
    }

    #[test]
    fn test_sample_tree_depth() {
        let tree = Tree::sample();
        assert_eq!(block_on(async_depth(&tree)), 3);
    }

    #[test]
    fn test_sample_tree_count() {
        let tree = Tree::sample();
        assert_eq!(block_on(async_count(&tree)), 6);
    }

    #[test]
    fn test_single_node() {
        let tree = Tree::node(42, Tree::leaf(), Tree::leaf());
        assert_eq!(block_on(async_sum(&tree)), 42);
        assert_eq!(block_on(async_depth(&tree)), 1);
        assert_eq!(block_on(async_count(&tree)), 1);
    }

    #[test]
    fn test_left_skewed_tree() {
        let tree = Tree::node(
            1,
            Tree::node(2, Tree::node(3, Tree::leaf(), Tree::leaf()), Tree::leaf()),
            Tree::leaf(),
        );
        assert_eq!(block_on(async_depth(&tree)), 3);
        assert_eq!(block_on(async_sum(&tree)), 6);
    }
}

(* OCaml: recursive tree operations (sync, as Lwt analogy) *)

type tree = Leaf | Node of { value: int; left: tree; right: tree }

let leaf = Leaf
let node v l r = Node { value = v; left = l; right = r }

let rec sum_tree = function
  | Leaf -> 0
  | Node { value; left; right } -> value + sum_tree left + sum_tree right

let rec depth_tree = function
  | Leaf -> 0
  | Node { left; right; _ } -> 1 + max (depth_tree left) (depth_tree right)

let sample =
  node 1
    (node 2 (node 4 leaf leaf) (node 5 leaf leaf))
    (node 3 (node 6 leaf leaf) leaf)

let () =
  Printf.printf "Sum: %d\n" (sum_tree sample);
  Printf.printf "Depth: %d\n" (depth_tree sample)

✓ Tests Rust test suite

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

    #[test]
    fn test_leaf_sum_is_zero() {
        assert_eq!(block_on(async_sum(&Tree::Leaf)), 0);
    }

    #[test]
    fn test_sample_tree_sum() {
        let tree = Tree::sample();
        assert_eq!(block_on(async_sum(&tree)), 21); // 1+2+3+4+5+6 = 21
    }

    #[test]
    fn test_sample_tree_depth() {
        let tree = Tree::sample();
        assert_eq!(block_on(async_depth(&tree)), 3);
    }

    #[test]
    fn test_sample_tree_count() {
        let tree = Tree::sample();
        assert_eq!(block_on(async_count(&tree)), 6);
    }

    #[test]
    fn test_single_node() {
        let tree = Tree::node(42, Tree::leaf(), Tree::leaf());
        assert_eq!(block_on(async_sum(&tree)), 42);
        assert_eq!(block_on(async_depth(&tree)), 1);
        assert_eq!(block_on(async_count(&tree)), 1);
    }

    #[test]
    fn test_left_skewed_tree() {
        let tree = Tree::node(
            1,
            Tree::node(2, Tree::node(3, Tree::leaf(), Tree::leaf()), Tree::leaf()),
            Tree::leaf(),
        );
        assert_eq!(block_on(async_depth(&tree)), 3);
        assert_eq!(block_on(async_sum(&tree)), 6);
    }
}

Deep Comparison

OCaml vs Rust: Async Recursion

Recursive Sum

OCaml:

let rec sum_tree = function
  | Leaf -> 0
  | Node { value; left; right } -> value + sum_tree left + sum_tree right

Rust:

fn async_sum(t: &Tree) -> BoxFuture<'_, i64> {
    Box::pin(async move {
        match t {
            Tree::Leaf => 0,
            Tree::Node{value,left,right} =>
                *value as i64 + async_sum(left).await + async_sum(right).await,
        }
    })
}

Key Differences

Aspect	OCaml	Rust
Direct recursion	Yes	No — requires `Box::pin`
Async support	Lwt wraps naturally	Must heap-allocate
Return type	Simple `int`	`BoxFuture<'_, i64>`
Memory	GC handles closures	Explicit heap allocation
Crate helper	N/A	`#[async_recursion]` macro

Exercises

Implement recursive async JSON traversal: count all leaf nodes in a nested JsonValue structure using BoxFuture.

Use the async-recursion crate's #[async_recursion] macro and compare the generated code to the manual BoxFuture approach.

Implement a recursive descent parser using async functions, where each production rule is a separate async function.

Open Source Repos

functional-rust

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

Rust