La torta di Piper

Ricorsione

Una funzione è ricorsiva quando chiama se stessa.

Una differenza fondamentale tra una chiamata di funzione e un ciclo è che chiamare una funzione inserisce nello stack l'indirizzo a cui tornare. Questo significa che una funzione ricorsiva di solito richiede più spazio nello stack rispetto a un ciclo equivalente.

Di conseguenza, una funzione che continua a chiamare se stessa può alla fine esaurire tutto lo spazio dello stack. Questa situazione si chiama stack overflow.

Ecco perché ogni funzione ricorsiva deve avere almeno un caso base, cioè una situazione in cui la funzione termina senza chiamare se stessa. Ogni chiamata ricorsiva deve prima o poi raggiungere un caso base.

Per esempio, la funzione fattoriale n! = n * (n - 1) * ... * 1 può essere definita ricorsivamente con 1 come 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

Nota che factorial deve eseguire push rdi prima della chiamata ricorsiva e pop rdi dopo. Questo perché, una volta terminata la chiamata ricorsiva, ha ancora bisogno di n per calcolare n * (n-1)!.

Nota anche che usare un registro callee-saved non risolverebbe questo problema.

Anche se una funzione ricorsiva è un potenziale chiamante di se stessa, è a sua volta chiamata da un'altra funzione. Questo significa che la funzione deve anche preservare i registri callee-saved prima di usarli e ripristinarne il valore dopo l'uso. Di solito lo si fa con una sequenza di push/pop, come abbiamo visto in un concetto precedente.

Poiché ogni frame di una funzione ricorsiva, con l'eccezione del caso base, è anche un chiamante che deve preservare le proprie variabili locali, questa sequenza di push/pop deve essere ripetuta per ogni frame. Anche memorizzare la variabile direttamente nello stack, senza usare registri, costerebbe comunque gli stessi 8 byte per frame.

Questo significa che ogni chiamata ricorsiva aggiunge 8 byte allo stack per l'indirizzo di ritorno inserito da call, più 8 byte per ogni variabile locale che deve salvare. La funzione continuerà ad aggiungere quei byte allo stack a ogni frame finché non raggiunge il suo caso base. Solo allora inizia a risalire in ordine inverso, con ogni chiamata ricorsiva che usa tanti pop quanti ne servono e poi un ret.

Per esempio, se factorial fosse chiamata con argomento 10, chiamerebbe se stessa nove volte prima di raggiungere il caso base di 1. A quel punto, sarebbero stati usati 144 byte per memorizzare il valore di n (8 byte) e l'indirizzo di ritorno (8 byte) per ogni frame precedente.

Chiamata in coda

In alcune situazioni, una funzione non svolge altro lavoro dopo aver chiamato un'altra funzione e prima di restituire il controllo.

Considera, per esempio:

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    call times_three
    ret

La funzione triple_of_square:

• moltiplica per se stesso l'argomento passato (in rdi), ottenendone il quadrato;
• poi chiama times_three, che restituisce tre moltiplicato per l'argomento passato.

Di conseguenza, triple_of_square restituisce 3*x², dove x è il suo argomento, passato in rdi.

Nota che in triple_of_square non viene svolto altro lavoro dopo la chiamata a times_three: la funzione restituisce semplicemente. In una situazione come questa, invece di usare call, una funzione potrebbe usare jmp e trasferire l'esecuzione alla funzione chiamata:

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    jmp times_three

Questa si chiama chiamata in coda.

Il vantaggio principale di una chiamata in coda è evitare il costo extra di call. Una call inserisce un indirizzo di ritorno nello stack, e perché il controllo torni a quel punto deve esserci un ret corrispondente.

Una chiamata in coda salta entrambe le cose: non c'è alcun indirizzo di ritorno da inserire e nessun ret extra con cui accoppiarlo, solo il ret della funzione chiamata.

Ricorsione in coda

Una chiamata in coda è particolarmente utile per le funzioni ricorsive che possono chiamare se stesse molte volte prima di restituire il controllo.

Tuttavia, non tutte le chiamate ricorsive possono essere trasformate direttamente in una chiamata in coda. Poiché un jmp trasferisce il controllo alla funzione chiamata, il chiamante non può svolgere altro lavoro dopo la chiamata in coda.

Per esempio, la funzione factorial di prima non è ricorsiva in coda. Dopo la chiamata ricorsiva, deve ancora moltiplicare il risultato per il valore corrente di n, usando imul rax, rdi.

In situazioni come questa, a volte è possibile usare un accumulatore che raccoglie i calcoli parziali e viene restituito alla fine. Per esempio, possiamo definire una funzione factorial_helper che fa la maggior parte del lavoro, e poi factorial imposta un accumulatore e trasferisce il controllo 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

Dato che dopo la chiamata ricorsiva non viene svolto altro lavoro, non abbiamo più bisogno di salvare rdi. Non c'è alcuna call né push rdi, quindi ogni iterazione ricorsiva aggiunge 0 byte allo stack: non viene usato spazio aggiuntivo nello stack. Questa versione può gestire n arbitrariamente grandi senza overflow dello stack. È sia più efficiente sia più sicura.

In alcuni casi, manipolando l'ordine delle funzioni, si può evitare anche il jmp verso la funzione ausiliaria. Per esempio, factorial e triple_of_square possono essere riscritte in questo modo:

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

Nel frammento sopra, l'esecuzione di factorial passa direttamente a factorial_helper. Lo stesso accade con triple_of_square e times_three. In entrambi i casi, l'esecuzione continua in modo sequenziale e sembra che la funzione in coda sia solo un'etichetta locale all'interno della funzione «main».

In realtà, non c'è alcuna differenza essenziale tra un'etichetta locale e una funzione. L'assembly x86-64 non riserva alcun trattamento speciale a nessuno di essi: sono solo indirizzi in una sezione con codice eseguibile, come section .text.

In questo modo, una funzione ricorsiva in coda può essere pensata essenzialmente come un ciclo in cui la chiamata ricorsiva salta di nuovo all'inizio, e il caso base è la condizione che termina il ciclo.