recursion - 什么时候可以在Rust中保证尾递归？

Question

C语言

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

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

只需返回，就像递归调用的返回值一样。当此递归可能重复一千甚至一百万次时，这一点尤其重要。它将在堆栈上使用很多内存。

rust

现在，我有一个Rust函数，该函数可以递归调用一百万次:

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),
    }
}

(这是一个最小的示例，真实的示例更复杂，但是它捕获了主要思想)

在这里，递归调用的返回值按原样返回，但是:

是否保证Rust编译器将应用尾递归？

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

Answer 1

只要在尾部位置调用递归函数(基本上是函数的最后一条语句)，就可以保证Tail calls。

尾调用优化Rust不能保证的优化，尽管优化器可以选择执行它。

if we declare some variable that needs to be destroyed

据我了解，这是问题的症结之一，因为更改已破坏的堆栈变量的位置会引起争议。

也可以看看:

Recursive function calculating factorials leads to stack overflow

RFC 81: guaranteed tail call elimination

RFC 1888: Proper tail calls