Asynchronous Recursion In rust

When was the last time you used a recursive function in any piece of software?

Well, you would agree that you rarely use it—it’s like inverting a binary tree 🤣, kidding.

However, unlike in languages like Python or JavaScript, building recursive functions can be more challenging due to Rust’s strict memory safety guarantees.

This is even more apparent when trying to make recursion asynchronous.

Synchronous Recursion vs. Async Recursion in Rust

In a simple synchronous Fibonacci example, the compiler can easily compute the size of the return type because the call stack is limited (typically around 256 calls by default). For example:

fn main() {
    print!("Total {:?}", fibonacci(2));
}

fn fibonacci(n: i32) -> i32 {
    match n {
        0 | 1 => n,
        _ => fibonacci(n - 1) + fibonacci(n - 2),
    }
}

Here, the recursion is entirely synchronous. The call stack size is known and managed by the runtime, so the compiler can safely allocate the required memory.

The Challenge with Async Recursion

When you convert this recursive function to async, things get trickier. In asynchronous Rust, every async function returns a Future whose size the compiler must know at compile time.

However, in a recursive async function, the Future can be self-referential or of an unbounded size because the compiler cannot determine a fixed size for the recursively generated futures. This leads to errors—Rust complains that the recursive async function could be infinitely sized.

In essence, the compiler is saying: "Due to memory safety concerns and the unknown call stack depth for async recursion, I can't safely allocate or move around this future." This is where Pin comes into play.

What is Pin?

Pin is a smart pointer in Rust that guarantees that the value it wraps will not be moved in memory. For async recursive functions, this is important because the future generated by a recursive async function might contain self-references (or otherwise depend on its own memory location).

The Rust compiler is used Pin to ensure that once a future is created, its memory location is fixed, thus preserving safety even when the future contains references to itself.

Without the proper use of Pin (and other smart pointer techniques), you would encounter compile-time errors when writing async recursive functions because the compiler can't guarantee that the recursive future will remain in a valid location throughout its lifetime.

Using the async_recursion Crate

Instead of manually handling the complexities of Pin and writing boilerplate code to create a pinned future, we can use the async_recursion crate. This crate provides a macro that automatically expands your recursive async function into the correct form.

Under the hood, it adds the necessary Pin wrappers and template code required by the compiler. This lets you write asynchronous recursive functions in a more natural and less error-prone way.

For example, here’s how you can write an async Fibonacci sequence:

1. Create a new project:

   cargo new recurse
   

2. Install dependencies:

   
   cargo add tokio --features full
   cargo add async_recursion
   

3. Update your main.rs file:

   
   use async_recursion::async_recursion;
   
   #[tokio::main]
   async fn main() {
       print!("Fibonacci {:?}", fibonacci(10).await);
   }
   
   #[async_recursion]
   async fn fibonacci(n: u64) -> u64 {
       match n {
           0 => 0,
           1 => 1,
           _ => fibonacci(n - 1).await + fibonacci(n - 2).await,
       }
   }
   

What Changed and Why

• #[tokio::main] Macro: This sets up an asynchronous runtime so that the main function can run async code.

• #[async_recursion] Macro: This macro handles the intricate details of using Pin behind the scenes. It transforms the async recursive function into a form that the compiler can understand, ensuring that the generated futures are pinned and have a statically known size, even if the recursion goes deep.

• Call to .await: In the recursive calls, we add .await to resolve the future before performing the addition. This ensures that each recursive call completes before the result is used.

By using the async_recursion crate, you avoid the headache of manually dealing with pins and smart pointers, making it much easier to write recursive async functions in Rust despite the inherent memory safety and call stack challenges.

Feel free to reach out to me on my Linkedin for any clarifications.