Rust 什么时候保证尾递归？

Question

C语言

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

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

只需返回递归调用的返回值即可。当这种递归可能重复一千次甚至一百万次时，这一点尤其重要。它会在堆栈上使用大量内存。

锈

现在，我有一个 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 编译器会应用尾递归？

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

Answer 1

Shepmaster 的回答解释了尾调用消除只是 Rust 中的一种优化，而不是保证。但是“从不保证”并不意味着“永远不会发生”。让我们看看编译器对一些真实代码做了什么。

它发生在这个函数中吗？

截至目前，Compiler Explorer上可用的最新 Rust 版本是 1.39，它并没有消除read_all.

example::read_all:
        push    r15
        push    r14
        push    rbx
        sub     rsp, 32
        mov     r14, rdx
        mov     r15, rsi
        mov     rbx, rdi
        mov     byte ptr [rsp + 7], 0
        lea     rdi, [rsp + 8]
        lea     rdx, [rsp + 7]
        mov     ecx, 1
        call    qword ptr [r14 + 24]
        cmp     qword ptr [rsp + 8], 1
        jne     .LBB3_1
        movups  xmm0, xmmword ptr [rsp + 16]
        movups  xmmword ptr [rbx], xmm0
        jmp     .LBB3_3
.LBB3_1:
        cmp     qword ptr [rsp + 16], 0
        je      .LBB3_2
        mov     rdi, rbx
        mov     rsi, r15
        mov     rdx, r14
        call    qword ptr [rip + example::read_all@GOTPCREL]
        jmp     .LBB3_3
.LBB3_2:
        mov     byte ptr [rbx], 3
.LBB3_3:
        mov     rax, rbx
        add     rsp, 32
        pop     rbx
        pop     r14
        pop     r15
        ret
        mov     rbx, rax
        lea     rdi, [rsp + 8]
        call    core::ptr::real_drop_in_place
        mov     rdi, rbx
        call    _Unwind_Resume@PLT
        ud2

注意这一行：call qword ptr [rip + example::read_all@GOTPCREL]。这就是（尾）递归调用。从它的存在可以看出，它并没有被消除。

将此与具有显式 的等效函数进行比较loop：

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

它没有要消除的尾调用，因此编译为一个只有一个的函数call（到 的计算地址input.read）。

那好吧。也许 Rust 不如 C。或者是吗？

它发生在C中吗？

这是 C 中的尾递归函数，它执行非常相似的任务：

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

这对于编译器来说应该是非常容易消除的。递归调用就在函数的底部，C 不必担心运行析构函数。但尽管如此，还是有递归尾调用，令人讨厌的是没有消除：

int read_all(FILE *input) {
    char buf[] = {0, 0};
    if (!fgets(buf, sizeof buf, input))
        return feof(input);
    return read_all(input);
}

事实证明，在 C 中也不能保证尾调用优化。我在不同的优化级别下尝试了 Clang 和 gcc，但我没有尝试过将这个相当简单的递归函数变成循环。

是否曾经发生的呢？

好吧，所以不能保证。编译器能做到吗？是的！这是一个通过尾递归内部函数计算斐波那契数的函数：

pub fn fibonacci(n: u64) -> u64 {
    fn fibonacci_lr(n: u64, a: u64, b: u64) -> u64 {
        match n {
            0 => a,
            _ => fibonacci_lr(n - 1, a + b, a),
        }
    }
    fibonacci_lr(n, 1, 0)
}

不仅消除了尾调用，整个fibonacci_lr函数也被内联到了 中fibonacci，只产生了 12 条指令（而且看不到 a call）：

        call    read_all

如果将其与等效while循环进行比较，编译器会生成几乎相同的程序集。

重点是什么？

您可能不应该依赖优化来消除尾调用，无论是在 Rust 中还是在 C 中。发生时很好，但是如果您需要确保函数编译为紧密循环，这是最可靠的方法，至少对于现在，是使用循环。

Answer 2

既不尾递归（重用用于尾调用相同功能的堆栈帧），也没有尾调用优化的（用于再利用的尾调用堆栈帧的任何功能）是有史以来锈病保证，尽管优化器可以选择执行它们。

如果我们声明了一些需要销毁的变量

我的理解是，这是症结之一，因为更改已销毁堆栈变量的位置会引起争议。

也可以看看：

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