Skip to content
rusthacks.dev
Concurrency

Rust Error Recursion in an Async Fn Requires Boxing

A recursive async fn has an infinitely sized future, so the compiler asks for indirection. Return a boxed future with Box::pin, or use the async-recursion crate, and prefer a loop when you can.

7 min read
Summarize in AI
Flat illustration for the post “Rust Error Recursion in an Async Fn Requires Boxing”, composed around threads.

An async fn that calls itself does not compile, and the error message tells you to box the call. Boxing fixes the compile error and leaves a second problem that the message does not mention: the recursion still runs on the thread's stack when the futures are polled, so deep recursion in async code overflows the stack exactly as it does in synchronous code. This post reproduces the error, applies the standard fixes (box the call, the async-recursion macro in one line, a hand-written boxed signature), measures what each recursion level costs, shows the depth at which it dies and gives the structure that never does: an explicit work list. Everything compiled on Rust 1.99, edition 2024, with tokio 1.

The error

rust
async fn count_down(n: u32) -> u32 {
    if n == 0 { 0 } else { 1 + count_down(n - 1).await }
}

fn main() {}
Text
error[E0733]: recursion in an async fn requires boxing
 --> src/main.rs:1:1
  |
1 | async fn count_down(n: u32) -> u32 {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
2 |     if n == 0 { 0 } else { 1 + count_down(n - 1).await }
  |                                ----------------------- recursive call here
  |
  = note: a recursive `async fn` call must introduce indirection such as `Box::pin` to avoid an infinitely sized future

An async fn returns a state machine that stores the state of the call in progress. If the body contains a call to itself, the state machine must contain a copy of itself inside, and that has infinite size. The note says what to do: introduce indirection. A Box holds a pointer of fixed size, so the type is finite. The cost model is the same as for the boxed futures in Pin and Box dyn Future.

Fix 1: box the recursive call

Since Rust 1.77 the simplest repair keeps the async fn signature and boxes only the recursive call:

rust
async fn count_down(n: u32) -> u32 {
    if n == 0 {
        0
    } else {
        1 + Box::pin(count_down(n - 1)).await
    }
}

async fn tree_size(depth: u32) -> u64 {
    if depth == 0 {
        return 1;
    }
    let (left, right) = tokio::join!(Box::pin(tree_size(depth - 1)), Box::pin(tree_size(depth - 1)));
    1 + left + right
}

#[tokio::main(flavor = "current_thread")]
async fn main() {
    println!("{}", count_down(10).await);
    println!("{}", tree_size(5).await);
}
Text
10
63

Each level allocates one box for the next level's future. The second function shows recursion that fans out: both children are boxed and joined, so a depth-5 tree has 63 nodes and 62 boxes. This form is the best default for a private helper, because the signature stays honest.

Fix 2: a boxed return type in the signature

When the function is part of a public API, or you want the box to be explicit and the signature to say "this allocates", return a boxed future:

rust
use std::future::Future;
use std::pin::Pin;

fn count_down(n: u32) -> Pin<Box<dyn Future<Output = u32>>> {
    Box::pin(async move {
        if n == 0 { 0 } else { 1 + count_down(n - 1).await }
    })
}

#[tokio::main(flavor = "current_thread")]
async fn main() {
    println!("{}", count_down(10).await);
}
Text
10

Add + Send to the dyn Future if the result will be spawned, and a lifetime if it borrows. The async-recursion crate does exactly this rewriting for you with #[async_recursion] on the function; it is worth a dependency only if you have many recursive functions, since the manual form is one line longer.

What each level costs, and where it stops

Boxing removes the compile error and nothing else. Every level still allocates, and when the outermost future is polled, the poll recurses: level 1's poll calls level 2's poll, and so on, all on the native stack. The numbers, on an Apple M1 Max in a release build with a current-thread runtime, using the boxed-signature form and the Box::pin call form against a plain loop computing the same sum:

Recursion depthBoxed signaturePer levelPlain loop
1,00044.9 µs45 ns42 ns total
10,000456 µs46 nsunder 1 ns per iteration, optimised away
100,000stack overflowno problem

About 45 nanoseconds per level (an allocation, a free and the poll chain) is cheap enough to ignore at the depths of real trees. The third row is the number that matters: at a depth of 100,000 the program aborted. Here is that run:

rust
use std::future::Future;
use std::pin::Pin;

fn sum_to(n: u64) -> Pin<Box<dyn Future<Output = u64>>> {
    Box::pin(async move { if n == 0 { 0 } else { n + sum_to(n - 1).await } })
}

#[tokio::main(flavor = "current_thread")]
async fn main() {
    println!("{}", sum_to(1_000).await);
    println!("{}", sum_to(100_000).await);
}
Text
500500
thread 'main' has overflowed its stack
fatal runtime error: stack overflow, aborting

The overflow is not a panic, so it cannot be caught: the process aborts with "has overflowed its stack". The boxes live on the heap, but the chain of poll calls does not. The threshold depends on the thread's stack size (2 MiB on Tokio's worker threads, 8 MiB on the main thread on most systems) and on how much each poll frame uses. Processing untrusted input recursively, such as a deeply nested JSON or a directory tree an attacker controls, turns this into a denial of service. The debugging steps for the abort are in debugging stack overflows.

A larger stack is a stopgap, not a fix. Builder::thread_stack_size on the runtime (or std::thread::Builder::stack_size for a thread you spawn) raises the ceiling, and each doubling buys roughly one more doubling of depth, which postpones the abort without removing it. Use it for a known deep-but-bounded workload, such as a compiler front end with generous nesting limits, and combine it with a depth limit. For anything driven by input, the structure has to change.

It is also worth knowing that the overflow is a property of how nested futures are polled, not of recursion as a concept. A hand-rolled loop that awaits a different future on each iteration, as in the next fix, never builds a chain of nested polls, and that is why it has no depth limit. Counting stack frames is the quick way to tell the two apart in a debugger: a loop shows a constant number of frames however long it runs, and the recursive version shows a pair of frames per level.

Fix 3: do not recurse, keep a work list

Any recursion over a tree can be written as a loop with an explicit stack or queue in the heap, and then the depth is limited by memory, not the call stack. A directory-style walk, with the I/O replaced by a small in-memory tree to keep the example self-contained:

rust
use std::collections::VecDeque;
use tokio::time::{sleep, Duration};

struct Node {
    name: &'static str,
    children: Vec<Node>,
}

async fn list_children(n: &Node) -> Vec<&Node> {
    sleep(Duration::from_millis(1)).await;
    n.children.iter().collect()
}

async fn walk(root: &Node) -> Vec<&'static str> {
    let mut seen = Vec::new();
    let mut queue: VecDeque<(&Node, usize)> = VecDeque::from([(root, 0)]);

    while let Some((node, depth)) = queue.pop_front() {
        seen.push(node.name);
        if depth < 10_000 {
            for child in list_children(node).await {
                queue.push_back((child, depth + 1));
            }
        }
    }
    seen
}

#[tokio::main(flavor = "current_thread", start_paused = true)]
async fn main() {
    let tree = Node {
        name: "root",
        children: vec![
            Node { name: "src", children: vec![Node { name: "main.rs", children: vec![] }, Node { name: "lib.rs", children: vec![] }] },
            Node { name: "Cargo.toml", children: vec![] },
        ],
    };
    println!("{:?}", walk(&tree).await);
}
Text
["root", "src", "Cargo.toml", "main.rs", "lib.rs"]

One future, one loop, one queue. No boxing, no recursion in the poll chain, an explicit depth cap as a safety valve, and breadth-first order as a side effect (swap pop_front for pop and push_back for push to get depth-first). It also parallelises naturally: pull a batch off the queue and process it with buffer_unordered, which bounds the concurrency too, as in buffer_unordered.

Choosing

SituationUse
Small, bounded depth (a handful of levels, a known tree)Box::pin(f(..)).await on the recursive call
Public API with recursionExplicit boxed return type, documented
Many recursive functionsThe async-recursion macro
Depth set by data (user input, file systems, parsers)An explicit stack or queue
Fan-out you want concurrentWork list plus buffer_unordered or a JoinSet

If you must recurse on data you do not control, add a depth parameter and return an error when it passes a limit, which converts a crash into a handled failure. The same advice holds for synchronous recursion in a parser, but async code adds a heap allocation to each level and hides the stack use inside the poll chain, which makes the failure less predictable.

Share

Keep reading

Get new posts by email

We send one email when a new post is published. No spam.

Unsubscribe in one click. No spam, ever.