时间戳

首页 > 解决方案 > Rust 什么时候保证尾递归？

recursion - Rust 什么时候保证尾递归？

问题描述

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它会在递归调用之前（允许尾递归）还是在递归调用返回之后（禁止尾递归）被销毁？

标签： recursionrusttail-recursion

解决方案

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

它发生在这个函数中吗？

截至目前，编译器资源管理器上可用的最新版 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 中的一个尾递归函数，它执行非常相似的任务：

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

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

        call    read_all

事实证明，在 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 条指令（而且call看不到）：

example::fibonacci:
        push    1
        pop     rdx
        xor     ecx, ecx
.LBB0_1:
        mov     rax, rdx
        test    rdi, rdi
        je      .LBB0_3
        dec     rdi
        add     rcx, rax
        mov     rdx, rcx
        mov     rcx, rax
        jmp     .LBB0_1
.LBB0_3:
        ret

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

重点是什么？

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

推荐阅读