🎓 A1Learner
🔍

Rust Async Recursion

Async recursion is an async function that calls itself. An async fn compiles into a state machine with a fixed size.

The direct way does not compile

This looks exactly like sync recursion — and fails. The error text below is real rustc output (E0733), captured during this course's research.

async fn countdown(n: u32) {
    if n > 0 {
        countdown(n - 1).await; // error[E0733]: recursion in an
                                // async fn requires boxing
    }
}

Box::pin breaks the circle

One change: box the recursive call. The future type is now finite. Each level stores a pointer to the next level. It does not store the whole next level.

async fn countdown(n: u32) {
    if n == 0 {
        println!("liftoff!");
    } else {
        println!("T-minus {n}");
        Box::pin(countdown(n - 1)).await;
    }
}

It works with values too

Tree recursion works in sync code. The async version changes nothing except the Box::pin around the recursive call. With Node { size: 1, children: [2, 3 -> [4]] } this returns 10.

async fn sum_tree(node: &Node) -> u64 {
    let mut total = node.size;
    for child in &node.children {
        total += Box::pin(sum_tree(child)).await;
    }
    total
}

Example

async fn countdown(n: u32) {
    if n == 0 {
        println!("liftoff!");
    } else {
        println!("T-minus {n}");
        Box::pin(countdown(n - 1)).await;
    }
}

#[tokio::main]
async fn main() {
    countdown(3).await;
}

Key points

  • A future's size must be known at compile time.
  • A recursive call would put the future inside itself, inside itself... an infinitely sized type.
  • The compiler refuses with error E0733: 'recursion in an async fn requires boxing'.
  • The fix: wrap only the recursive call in Box::pin — Box::pin(countdown(n - 1)).await.
  • The depth now lives on the heap.
  • The future itself stays pointer-sized at each level.
  • The async fn keeps its natural signature.
  • Direct Box::pin in the async fn works on modern Rust.
  • Very old code wrapped the whole body in a non-async fn.
  • That fn returned Pin<Box<dyn Future>>.
  • You may still meet that shape.
  • Every level allocates one Box.
  • Tree-shaped recursion (filesystems, JSON, DOMs) is shallow.
  • The cost is trivial.
  • A million-deep chain pays a million boxes.
  • If the recursive future must erase its type and be Send, name it explicitly.
  • Send is what spawning needs.
  • Write fn walk(...) -> Pin<Box<dyn Future<Output = T> + Send + 'a>>.
  • The box is the same idea, with the type written out.

Each level awaits a boxed copy of the level below it. The Box moves that level's state machine onto the heap. So every future is small and fixed-size. The call chain can still be as deep as your data needs.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

Exercise

Why does a directly recursive async fn fail to compile?