Search code examples
recursionrusttail-recursion

When is tail recursion guaranteed in Rust?


C language

In the C programming language, it's easy to have tail recursion:

int foo(...) {
    return foo(...);
}

Just return as is the return value of the recursive call. It is especially important when this recursion may repeat a thousand or even a million times. It would use a lot of memory on the stack.

Rust

Now, I have a Rust function that might recursively call itself a million times:

fn read_all(input: &mut dyn std::io::Read) -> std::io::Result<()> {
    match input.read(&mut [0u8]) {
        Ok (  0) => Ok(()),
        Ok (  _) => read_all(input),
        Err(err) => Err(err),
    }
}

(this is a minimal example, the real one is more complex, but it captures the main idea)

Here, the return value of the recursive call is returned as is, but:

Does it guarantee that the Rust compiler will apply a tail recursion?

For instance, if we declare some variable that needs to be destroyed like a std::Vec, will it be destroyed just before the recursive call (which allows for tail recursion) or after the recursive call returns (which forbids the tail recursion)?


Solution

  • Neither tail recursion (reusing a stack frame for a tail call to the same function) nor tail call optimization (reusing the stack frame for a tail call to any function) are ever guaranteed by Rust, although the optimizer may choose to perform them.

    if we declare some variable that needs to be destroyed

    It's my understanding that this is one of the sticking points, as changing the location of destroyed stack variables would be contentious.

    See also: