Linguagem C

Na linguagem de programação C, é fácil ter recursão de cauda :

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

Apenas retorne como é o valor de retorno da chamada recursiva. É especialmente importante quando essa recursão pode se repetir mil ou até um milhão de vezes. Usaria muita memória na pilha .

Ferrugem

Agora, eu tenho uma função Rust que pode se chamar recursivamente um milhão de vezes:

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

(este é um exemplo mínimo, o real é mais complexo, mas captura a ideia principal)

Aqui, o valor de retorno da chamada recursiva é retornado como está, mas:

Isso garante que o compilador Rust aplique uma recursão de cauda?

Por exemplo, se declararmos alguma variável que precisa ser destruída como a std::Vec, ela será destruída imediatamente antes da chamada recursiva (que permite recursão de cauda) ou após o retorno da chamada recursiva (que proíbe a recursão de cauda)?

As chamadas de cauda são garantidas sempre que sua função recursiva é chamada na posição de cauda (basicamente a última declaração da função).

A otimização da chamada de cauda nunca é garantida pelo Rust, embora o otimizador possa optar por executá-la.

se declararmos alguma variável que precisa ser destruída

Entendo que esse é um dos pontos problemáticos, pois alterar a localização das variáveis ​​de pilha destruídas seria controverso.

Veja também:

• A função recursiva que calcula fatoriais leva ao estouro da pilha
• RFC 81: eliminação de chamada de cauda garantida
• RFC 1888: chamadas de cauda adequadas

A resposta de Shepmaster explica que a otimização da chamada de cauda, ​​que eu prefiro chamar eliminação de chamada de cauda, ​​não está garantida no Rust. Mas essa não é a história toda! Existem muitas possibilidades entre "nunca acontece" e "garantido". Vamos dar uma olhada no que o compilador faz com algum código real.

Isso acontece nessa função?

No momento, a versão mais recente do Rust disponível no Compiler Explorer é a 1.39 e não elimina a chamada final 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

Observe esta linha: call qword ptr [rip + example::read_all@GOTPCREL]. Essa é a ligação recursiva. Como você pode ver por sua existência, não foi eliminado.

Compare isso com uma função equivalente com uma explícitaloop :

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

que não tem chamada final para eliminar e, portanto, compila uma função com apenas uma call(no endereço calculado de input.read).

Ah bem. Talvez Rust não seja tão bom quanto C. Ou é?

Isso acontece em C?

Aqui está uma função recursiva da cauda em C que executa uma tarefa muito semelhante:

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

Isso deve ser super fácil para o compilador eliminar. A chamada recursiva fica na parte inferior da função e C não precisa se preocupar com a execução de destruidores. Mas, no entanto, existe essa chamada recursiva , irritantemente não eliminada:

        call    read_all

Acontece que a otimização da chamada de cauda também não é garantida em C. Eu tentei o Clang e o gcc sob diferentes níveis de otimização, mas nada que eu tentasse transformaria essa função recursiva bastante simples em um loop.

Isso já aconteceu?

Ok, então não é garantido. O compilador pode fazer isso? Sim! Aqui está uma função que calcula os números de Fibonacci por meio de uma função interna recursiva da cauda:

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

Não apenas a chamada fibonacci_lrfinal é eliminada, toda a função é incorporada fibonacci, fornecendo apenas 12 instruções (e não uma callvista):

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

Se você comparar isso com um whileloop equivalente , o compilador gera quase o mesmo assembly.

Qual é o objetivo?

Você provavelmente não deve confiar em otimizações para eliminar chamadas finais, seja em Rust ou em C. É bom quando isso acontece, mas se você precisa ter certeza de que uma função é compilada em um loop apertado, da maneira mais certa, pelo menos para agora, é usar um loop.