A torta de Piper

Recursão

Uma função é recursiva quando chama a si mesma.

Uma diferença importante entre uma chamada de função e um laço é que chamar uma função empilha o endereço de retorno na pilha. Isso significa que uma função recursiva geralmente exige mais espaço de pilha do que um laço equivalente.

Como consequência, uma função que fica chamando a si mesma pode acabar esgotando todo o espaço da pilha. Isso se chama estouro de pilha.

É por isso que toda função recursiva precisa ter pelo menos um caso base, que é uma situação em que a função retorna sem chamar a si mesma. Toda chamada recursiva precisa chegar a um caso base em algum momento.

Por exemplo, a função fatorial n! = n * (n - 1) * ... * 1 pode ser definida recursivamente com 1 como caso base:

factorial:
    ; the argument `n` is passed on `rdi`
    ; the factorial will be returned on `rax`

    cmp rdi, 1
    jle .base_case     ; base case -> if rdi <= 1, return 1

    push rdi           ; save n
    dec rdi            ; rdi = n - 1
    call factorial     ; recursive call, rax = (n - 1)!
    pop rdi            ; restore n
    imul rax, rdi      ; rax = n * (n - 1)! = n!
    ret
.base_case:
    mov rax, 1
    ret

Repare que factorial precisa executar push rdi antes de se chamar recursivamente e pop rdi depois. Isso acontece porque ela ainda precisa de n quando a chamada recursiva retorna, para calcular n * (n-1)!.

Repare também que usar um registrador salvo pela função chamada não resolveria esse problema.

Ainda que uma função recursiva seja uma possível chamadora de si mesma, ela também é a função chamada por alguma outra função. Isso significa que a função também precisa preservar os registradores salvos pela função chamada antes de usá-los, e restaurar o valor deles depois de usá-los. Normalmente isso é feito com uma sequência de push/pop, como vimos em um conceito anterior.

Como cada quadro de uma função recursiva, com exceção do caso base, também é um chamador que precisa preservar as próprias variáveis locais, essa sequência de push/pop precisa se repetir a cada quadro. Mesmo guardar a variável direto na pilha, sem usar registradores, ainda custaria os mesmos 8 bytes por quadro.

Isso significa que cada chamada recursiva acrescenta 8 bytes à pilha pelo endereço de retorno empilhado pelo call, mais 8 bytes para cada variável local que ela precise salvar. A função vai continuar acrescentando esses bytes à pilha a cada quadro até chegar ao caso base. Só então ela começa a se desfazer na ordem inversa: cada chamada recursiva usa quantos pop forem necessários e depois um ret.

Por exemplo, se factorial fosse chamada com o argumento 10, ela chamaria a si mesma nove vezes antes de chegar ao caso base de 1. Nesse ponto, 144 bytes teriam sido usados para armazenar o n (8 bytes) e o endereço de retorno (8 bytes) de cada quadro anterior.

Chamada de cauda

Em algumas situações, uma função não realiza mais nenhum trabalho depois de chamar outra e antes de retornar.

Considere, por exemplo:

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    call times_three
    ret

A função triple_of_square:

• multiplica o argumento recebido (em rdi) por ele mesmo, obtendo o seu quadrado;
• depois chama times_three, que retorna três vezes o argumento recebido.

Como resultado, triple_of_square retorna 3*x², em que x é o argumento dela, recebido em rdi.

Repare que nenhum trabalho é feito em triple_of_square depois de chamar times_three: a função simplesmente retorna. Numa situação como essa, em vez de usar call, a função pode usar jmp e transferir a execução para a função chamada:

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    jmp times_three

Isso se chama chamada de cauda.

A principal vantagem de uma chamada de cauda é evitar o custo extra do call. Um call empilha um endereço de retorno na pilha e, para que o controle volte àquele ponto, é preciso haver um ret correspondente.

Uma chamada de cauda pula os dois: não há endereço de retorno para empilhar nem ret extra para fazer par, apenas o ret da própria função chamada.

Recursão de cauda

Uma chamada de cauda é especialmente útil para funções recursivas que podem chamar a si mesmas muitas vezes antes de retornar.

No entanto, nem toda chamada recursiva pode ser convertida diretamente em uma chamada de cauda. Como um jmp transfere o controle para a função chamada, quem chama não pode realizar mais nenhum trabalho depois da chamada de cauda.

Por exemplo, a função factorial de antes não é recursiva de cauda. Depois da chamada recursiva, ela ainda precisa multiplicar o resultado pelo n atual, usando imul rax, rdi.

Em situações como essa, às vezes é possível usar um acumulador que vai juntando cálculos parciais e é retornado no final. Por exemplo, podemos definir uma factorial_helper que faz a maior parte do trabalho e então a factorial prepara um acumulador e transfere o controle para a factorial_helper:

factorial_helper:
    ; the argument `n` is passed on `rdi`
    ; `rax` is used as an accumulator and will be returned at the end

    cmp rdi, 1
    jle .base_case

    imul rax, rdi        ; we accumulate the partial result on `rax`
    dec rdi              ; rdi = n - 1
    jmp factorial_helper ; tail call to accumulate (n - 1)!
.base_case:
    ret                  ; returns the factorial already accumulated on `rax`

factorial:
    mov rax, 1           ; initial value for the accumulator
    jmp factorial_helper ; tail call

Como não se faz mais nenhum trabalho depois da chamada recursiva, também não precisamos mais salvar o rdi. Não há call nem push rdi, então cada iteração recursiva acrescenta 0 bytes à pilha: nenhum espaço extra de pilha é usado. Essa versão consegue lidar com qualquer valor de n, por maior que seja, sem estourar a pilha. Ela é ao mesmo tempo mais eficiente e mais segura.

Em alguns casos, reorganizando a ordem das funções, até o jmp para a auxiliar pode ser evitado. Por exemplo, factorial e triple_of_square podem ser reescritas assim:

factorial:
    mov rax, 1
factorial_helper:
    cmp rdi, 1
    jle .base_case

    imul rax, rdi
    dec rdi
    jmp factorial_helper
.base_case:
    ret

triple_of_square:
    imul rdi, rdi
times_three:
    imul rax, rdi, 3
    ret

No trecho acima, a execução de factorial continua direto para factorial_helper. O mesmo acontece com triple_of_square e times_three. Nos dois casos, a execução segue em sequência e parece que a função de cauda é apenas um rótulo local dentro da função "principal".

Na verdade, não há diferença essencial entre qualquer rótulo local e uma função. O assembly x86-64 não dá tratamento especial a nenhum deles: são apenas endereços em uma seção com código executável, como section .text.

Dessa forma, uma função recursiva de cauda pode ser vista como essencialmente o mesmo que um laço em que a chamada recursiva salta de volta para o topo e o caso base é a condição que encerra o laço.