Why recursive async functions require 'static parameters in Rust?

Question

Given a simple async function:

async fn foo(n: usize) -> usize {
    if n > 0 { foo(n - 1).await }
    else { 0 }
}

The compiler complains that async fn must be rewritten to return a boxed dyn Future.

| async fn foo(n: usize) -> usize {
|                           ^^^^^ recursive `async fn`
  = note: a recursive `async fn` must be rewritten to return a boxed `dyn Future`.

For more information about this error, try `rustc --explain E0733`.

---

Compiler explanation (rustc --explain E0733):

To achieve async recursion, the async fn needs to be desugared such that the Future is explicit in the return type:

use std::future::Future;
fn foo_desugared(n: usize) -> impl Future<Output = ()> {
    async move {
        if n > 0 {
            foo_desugared(n - 1).await;
        }
    }
}

Finally, the future is wrapped in a pinned box:

use std::future::Future;
use std::pin::Pin;
fn foo_recursive(n: usize) -> Pin<Box<dyn Future<Output = ()>>> {
    Box::pin(async move {
        if n > 0 {
            foo_recursive(n - 1).await;
        }
    })
}

The Box<...> ensures that the result is of known size, and the pin is required to keep it in the same place in memory.

---

Now consider this code:

fn foo(n: &usize) -> Pin<Box<dyn Future<Output = usize>>> {
    Box::pin(async move {
        if *n > 0 {
            foo(&n).await
        } else {
            0
        }
    })
}

The compiler complains that the lifetime of &n should be 'static.

|   fn foo(n: &usize) -> Pin<Box<dyn Future<Output = usize>>> {
|             ------ help: add explicit lifetime `'static` to the type of `n`: `&'static usize`
| /     Box::pin(async move {
| |         if *n > 0 {
| |             foo(&n).await
| |         } else {
| |             0
| |         }
| |     })
| |______^ lifetime `'static` required

Please help me understand what is going on.

Answer 1

Trait objects (dyn Trait) will by default have a static lifetime, unless otherwise specified. Because of this, boxed futures (and other traits) without a specified lifetime cannot depend on borrowed data, unless that data is borrowed for the 'static lifetime. (Which is what your error message complains about).

To solve this, you can either specify the lifetime explicitly, or you can just use '_, in which case it will use the elided lifetime of the n: &usize parameter:

//        .--  will use elided lifetime from here
//        v                      v--  give the future a non-'static lifetime
fn foo(n: &usize) -> Pin<Box<dyn '_ + Future<Output = usize>>> {
// or: fn foo<'a>(n: &'a usize) -> Pin<Box<dyn 'a + Future<Output = usize>>>
    Box::pin(async move {
        if *n > 0 {
            foo(&n).await // <-- no error, as the future lifetime now depends on the
                          //     lifetime of n instead of having a 'static lifetime
        } else {
            0
        }
    })
}