A Recursive Rust Opaque Return Type Has No Finite Concrete Shape

Return-position impl Iterator hides a concrete type from callers, but the compiler still needs one finite concrete type for the function body. The failing fixture returns a Chain containing another call with the same opaque return, producing E0720.

Expand the hidden type equation

Suppose the hidden type is T. The body returns Chain<Once<u8>, T>, so T would need to equal a type containing T directly. Expanding again adds another Chain forever. No finite stack layout results.

The official E0720 explanation frames this as an opaque type expanding recursively. impl Trait hides the name, not the requirement for a statically known representation.

This is related to recursive structs that store themselves by value. Both need indirection or a non-recursive representation to end size expansion.

The repair adds Box indirection and dynamic dispatch

The repaired fixture returns Box<dyn Iterator<Item = u8>>. A Box has fixed pointer size, while its allocation can contain different concrete iterator types at each branch. The assertion proves depth three yields the expected descending sequence.

This repair allocates once per recursive level and dynamically dispatches iterator calls. It is correct evidence, not automatically the best production implementation.

The Book explains how Box enables recursive types by inserting a known-sized pointer.

An explicit iterator state machine can avoid allocation

For this countdown, a range or custom iterator storing one integer is much simpler. It has one finite struct type, no recursion, and no per-level allocation. Many recursive iterator constructions can be converted into an explicit stack stored in a Vec or small fixed buffer.

I choose based on maximum depth, performance, readability, and whether yielded work must remain lazy. An explicit stack also avoids call-stack overflow on adversarial depth.

Enums can represent a fixed set of iterator branches without dynamic dispatch, but a recursively nested enum still needs pointer indirection somewhere if it contains itself.

Opaque returns require one type across branches too

Even without recursion, returning different iterator adapter types from if branches fails because one impl Trait return represents one hidden concrete type. Boxing, an enum such as Either, or arranging both branches into one adapter shape can solve that problem.

The Reference describes abstract return types. The function chooses the hidden type once; it does not mean “any implementor on each return.”

This is the opposite choice from argument-position impl Trait, where each caller supplies a concrete type.

Recursive async functions share the size problem

An async function returns an opaque future whose state stores the future of recursive calls. Direct recursion therefore needs boxing or another indirection, reflected by a neighbouring diagnostic. A loop is often preferable for tail-recursive workflows.

When boxing futures or iterators, lifetimes and Send requirements remain. Box<dyn Iterator + 'a> may borrow input; adding 'static can unnecessarily reject it. Pin<Box<dyn Future>> addresses immovable future polling but is not needed for ordinary Iterator solely due to recursion.

Measure abstraction cost where it matters

Dynamic dispatch can block inlining, while enum or generic approaches can increase code size. Allocation dominates some tiny operations but is irrelevant in others. I benchmark realistic depth and item work before optimising.

Tests include zero depth, normal depth, maximum accepted depth, ordering, early iterator drop, and resource cleanup. If input controls depth, a limit prevents memory and stack denial of service regardless of compilation strategy.

My E0720 checklist

• What concrete type equation does the opaque return body imply?
• Does expanding a recursive call place the hidden type inside itself?
• Can the algorithm become a loop, range, or explicit-stack iterator?
• Is Box plus dynamic dispatch acceptable for allocation and hot-path costs?
• Would a finite enum represent branch variation without erasure?
• What lifetime and Send bounds must the erased object retain?
• Can untrusted recursion depth exhaust stack or heap?
• Do tests cover zero, limits, ordering, early drop, and cleanup?

The core principle is that opacity hides type identity from callers, not representation from the compiler. E0720 exposes an infinite type equation. I break it with the simplest honest state representation and measure whether indirection belongs in the final design.