Are C++20 coroutines allowed to be recursive? Or does recursing require boxing?
For a stackless coroutine the compiler normally has to build a state machine to represent the possible execution contexts, but if the state machine includes itself then it has indeterminate size. Normally you solve this by boxing the state machine at yield points and using dynamic dispatch to call or resume a pending coroutine - which may be significantly slower than using a stackful coroutine to begin with (in which case, the stack is allocated on the heap up front, leading to a higher price to spawn the coroutine, but lower to resume or yield).
I'm curious. Intuitively, a non-recursive coroutine would yield a state machine that only goes "forward". If you add tail recursion into the mix, you could have cycles in the state machines (going back to the begin state), correct? Of course non-tail recursion would not work within a single frame.
Yes, a tail recursive coroutine could reuse its previous frame context across yields.
With a state machine transform the `resume()` method on a coroutine is a state transformation, it doesn't necessarily know what is "forward" or "backward" in the control flow graph. There are some tricky bits though, since tail recursive functions can have multiple exits but single entries. A recursive coroutine might have multiple exits and multiple entries, so it's not always clear what is "forward" and what is "backward."
The state is allowed to be heap-allocated but can be optimized onto the stack. But if it calls recursively without control flowing back out again, then I’d think the nested state could live on the stack so long as the compiler knows the nested state never has to be held across yield/resume.
For a stackless coroutine the compiler normally has to build a state machine to represent the possible execution contexts, but if the state machine includes itself then it has indeterminate size. Normally you solve this by boxing the state machine at yield points and using dynamic dispatch to call or resume a pending coroutine - which may be significantly slower than using a stackful coroutine to begin with (in which case, the stack is allocated on the heap up front, leading to a higher price to spawn the coroutine, but lower to resume or yield).