Rust 什么时候保证尾递归? [英] When is tail recursion guaranteed in Rust?

问题描述

在 C 编程语言中，很容易出现尾递归:

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:

是否保证 Rust 编译器会应用尾递归?

例如，如果我们声明了一些像 std::Vec 这样需要销毁的变量，它会在递归调用之前(允许尾递归)还是在递归调用之后销毁?调用返回(禁止尾递归)?

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)?

推荐答案

尾递归 (重用堆栈帧用于对同一函数的尾调用)或 尾调用优化(重用堆栈Rust 永远保证对任何函数的尾调用框架，尽管优化器可能选择执行它们.

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.

另见:

• 递归函数计算阶乘导致堆栈溢出
• RFC 81:保证消除尾调用
• RFC 1888:正确的尾调用

这篇关于Rust 什么时候保证尾递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！