Are recursive async functions ok?

help
1

Hi all,

I have a task that needs to do some work, sleep for a bit (some logic to calculate how long), then repeat.

If this was old-school synchronous code on the JVM (wasting a thread) I'd be concerned about blowing up the stack by having the function call itself (in Java every method call is added to the stack, I would expect the same to be true of at least debug-enabled Rust), so I'd probably want to put it in an infinite loop or check that my language/compiler was able to do tail call optimisation. But with Rust's async keyword do I need to be concerned about any of those things?

I'd also be worried about lifetime scopes in this case, I'd want to make sure that all teh appropriate drops are called every time I recurse.

1 Like
2

Here is a great page about recursive async functions:

https://rust-lang.github.io/async-book/07_workarounds/04_recursion.html

4 Likes
3

You seem to be imagining doing this using a tail recursive function instead of a loop. Why?

4

partially habit, partially information management and termination criteria. Of course they are equivalent so it boils down to a matter of style. For sure there are cases where a tail call optimised form of an algorithm is cleaner, and for those I'd use tailcall - Rust to guarantee the optimization actually happens.

Given the pinning requirement (c.f. the selected answer to this question) for doing this sort of thing when going async, it for sure feels like a (potentially infinite) loop is preferable.

5

oh fantastic, thanks! This wasn't there when I read the book, but it was updated just last month to coincide with

Support for recursion in async fn has become stable in Rust 1.77.

6

The async recursion support is only letting async recursion type-check successfully, not any support for tail call elimination. If you write a tail recursive async function you’ll indefinitely accumulate Boxed copies of your future (and they will become increasingly slow to poll because each Future::poll() must recurse to the end of that chain anew).

Just write a loop.

6 Likes
7

If you really need tail call elimination, it’s possible to write a continuation-passing style async trampoline:

struct Cps<T>(Pin<Box<dyn Future<Output=ControlFlow<T, Cps<T>>>>>);

impl<T,F:'static,Cont> From<F> for Cps<T> where F:Future<Output=ControlFlow<T,Cont>>, Cont: Into<Self> {
    fn from(fut:F)->Self {
        Cps(Box::pin(async move { fut.await.map_continue(Cont::into) }))
    }
}

impl<T:'static> IntoFuture for Cps<T>{
    type Output = T;
    type IntoFuture = Pin<Box<dyn Future<Output = T>>>;

    fn into_future(mut self) -> Self::IntoFuture {
        Box::pin(async move {
            loop {
                match self.0.await {
                    ControlFlow::Break(x) => return x,
                    ControlFlow::Continue(c) => { self = c }
                }
            }
        })
    }
}

Edit: I didn't care for the ergonomics, so I made an alternate version.

6 Likes
8

I was once advised that async functions cannot be recursive.

Recursion means a value is returned from the function.

The term that was used is something like "a non-terminating process that happens to refer to itself".