A Tarte da Piper

Recursão

Uma função é recursiva quando se chama a si própria.

Uma diferença fundamental entre uma chamada de função e um ciclo é que chamar uma função coloca na pilha o endereço para onde se deve regressar. Isto significa que uma função recursiva costuma exigir mais espaço na pilha do que um ciclo equivalente.

Como consequência, uma função que não para de se chamar a si própria pode acabar por esgotar todo o espaço da pilha. É a isto que se chama stack overflow.

É por isso que todas as funções recursivas têm de ter pelo menos um caso base, ou seja, uma situação em que a função termina sem se chamar a si própria. Qualquer chamada recursiva tem de acabar por chegar a um caso base.

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

Repara que factorial tem de fazer push rdi antes de se chamar recursivamente e pop rdi depois. Isto acontece porque ainda precisa de n quando a chamada recursiva termina, para calcular n * (n-1)!.

Repara também que usar um registo preservado pela função chamada não resolveria este problema.

Apesar de uma função recursiva poder ser quem chama, também é, ela própria, a função chamada por outra função. Isso significa que a função também tem de preservar os registos que a função chamada é obrigada a salvaguardar antes de os usar, e repor o seu valor depois de os usar. Normalmente isto faz-se com uma sequência de push/pop, como já vimos num conceito anterior.

Como cada frame de uma função recursiva, com exceção do caso base, também é quem chama e tem de preservar as suas próprias variáveis locais, esta sequência de push/pop tem de se repetir em cada frame. Mesmo guardar a variável diretamente na pilha, sem usar registos, continuaria a custar os mesmos 8 bytes por frame.

Isto significa que cada chamada recursiva acrescenta 8 bytes à pilha, para o endereço de retorno que o call coloca lá, mais 8 bytes por cada variável local que precise de guardar. A função vai continuar a acrescentar esses bytes à pilha a cada frame, até chegar ao caso base. Só então é que começa a desenrolar-se pela ordem inversa, com cada chamada recursiva a usar tantos pop quantos forem necessários e, no fim, um ret.

Por exemplo, se factorial fosse chamada com o argumento 10, chamar-se-ia a si própria nove vezes antes de chegar ao caso base de 1. Nessa altura, teriam sido usados 144 bytes para guardar o n (8 bytes) e o endereço de retorno (8 bytes) de cada frame anterior.

Chamada de cauda

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

Considera, 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 si próprio, obtendo o seu quadrado;
• de seguida chama times_three, que devolve o triplo do argumento recebido.

Como resultado, triple_of_square devolve 3*x², em que x é o seu argumento, passado em rdi.

Repara que não se faz nenhum trabalho em triple_of_square depois de chamar times_three: a função limita-se a regressar. Numa situação como esta, 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

É a isto que se chama uma chamada de cauda.

A principal vantagem de uma chamada de cauda é evitar o custo extra do call. Um call coloca um endereço de retorno na pilha e, para que o controlo volte a esse ponto, tem de existir um ret correspondente.

Uma chamada de cauda evita as duas coisas: não há endereço de retorno para colocar na pilha nem ret extra com que fazer par, apenas o ret da própria função chamada.

Recursão de cauda

Uma chamada de cauda é especialmente útil em funções recursivas que podem chamar-se a si próprias muitas vezes antes de terminar.

No entanto, nem todas as chamadas recursivas podem ser convertidas diretamente numa chamada de cauda. Como um jmp transfere o controlo 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 que vimos antes não é recursiva de cauda. Depois da chamada recursiva, ainda precisa de multiplicar o resultado pelo n atual, com imul rax, rdi.

Em situações como esta, às vezes é possível usar um acumulador que vai acumulando resultados parciais e é devolvido no final. Por exemplo, podemos definir uma factorial_helper que faz a maior parte do trabalho, e depois factorial prepara um acumulador e transfere o controlo para 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 já não se faz nenhum trabalho depois da chamada recursiva, também já não é preciso guardar o rdi. Não há call nem push rdi, pelo que cada iteração recursiva acrescenta 0 bytes à pilha: não se usa espaço adicional na pilha. Esta versão consegue lidar com valores de n arbitrariamente grandes sem esgotar a pilha. É simultaneamente mais eficiente e mais segura.

Em alguns casos, manipulando a ordem das funções, é possível evitar até o jmp para a função auxiliar. Por exemplo, factorial e triple_of_square podem ser reescritas desta forma:

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 excerto acima, a execução de factorial passa diretamente para factorial_helper. O mesmo acontece com triple_of_square e times_three. Em ambos os casos, a execução continua sequencialmente e parece que a função de cauda é apenas uma etiqueta local dentro da função "principal".

Na realidade, não há nenhuma diferença essencial entre uma etiqueta local e uma função. O assembly x86-64 não dá tratamento especial a nenhuma delas: são apenas endereços numa secção com código executável, como section .text.

Assim, uma função recursiva de cauda pode ser encarada como essencialmente o mesmo que um ciclo em que a chamada recursiva salta de volta para o início, e o caso base é a condição que termina o ciclo.