Assembly Base con MASM

Capitolo 26: La ricorsione

Un determinato procedimento si definisce ricorsivo quando contiene un richiamo a se stesso; la ricorsione può essere diretta o indiretta. Si parla di ricorsione diretta o auto ricorsione, quando un procedimento richiama direttamente se stesso; si parla, invece, di ricorsione indiretta o mutua ricorsione, quando un procedimento A richiama un procedimento B che, a sua volta, richiama di nuovo il procedimento A.
In generale, la ricorsione indiretta può coinvolgere n procedimenti A1, A2, A3, ..., An; in tal caso, il procedimento A1 richiama il procedimento A2 che richiama il procedimento A3 e così via, sino al procedimento An che richiama di nuovo il procedimento A1.

In matematica troviamo numerosi esempi di procedimenti ricorsivi; in questo caso, il termine procedimento è riferito ad un algoritmo identificato da una funzione matematica. Come già sappiamo, una funzione matematica riceve una lista di argomenti (variabili indipendenti) che vengono elaborati da un apposito algoritmo in modo da ottenere un risultato finale (variabile dipendente); possiamo dire quindi che un algoritmo è ricorsivo quando la sua definizione contiene un richiamo (diretto o indiretto) all'algoritmo stesso.

Consideriamo, ad esempio, il caso della funzione fattoriale; dato un numero intero positivo n, si definisce fattoriale di n il prodotto dei primi n numeri interi positivi consecutivi decrescenti, a partire da n. Simbolicamente, il fattoriale di n si scrive: 
n!
Inoltre, per convenzione si pone: 
0! = 1
(per la dimostrazione si può consultare un testo di matematica).

Se, ad esempio, n=5, si ottiene: 
5! = 5 * 4 * 3 * 2 * 1 = 120
Si osserva subito che: 
5! = 5 * 4 * 3 * 2 * 1 = 5 * (4 * 3 * 2 * 1) = 5 * 4! = 5 * (5 - 1)!
In sostanza, si può scrivere la relazione generale: 
n! = n * (n - 1)!
Questa relazione dice che il fattoriale di n si ottiene moltiplicando n per il fattoriale di n-1; l'algoritmo appena enunciato è chiaramente ricorsivo in quanto contiene un riferimento a se stesso.
Un algoritmo ricorsivo può essere paragonato ad una sorta di loop dal quale si esce non appena viene raggiunta una determinata condizione (condizione di uscita); nel caso del fattoriale di n si nota subito che la condizione di uscita è rappresentata da: 
(n - 1) = 0 e cioè: n = 1
In questo caso, infatti, si ha: 
(n - 1)! = (1 - 1)! = 0! = 1
Vediamo allora come si applicano questi concetti per calcolare ricorsivamente il fattoriale del numero 5; possiamo scrivere: A questo punto abbiamo ottenuto tutti i fattori necessari, per cui, procedendo a ritroso si ottiene: Un altro caso di funzione matematica definibile ricorsivamente è rappresentato dall'elevamento a potenza intera positiva, di un numero intero positivo diverso da 1; dati due numeri interi positivi m e n, con n diverso da 1, si definisce potenza di ordine m del numero n, il prodotto di m fattori tutti uguali a n.
Simbolicamente, la potenza di ordine m del numero n viene rappresentata come: 
nm
Se, ad esempio, n=2 e m=4 possiamo scrivere quindi: 
24 = 2 * 2 * 2 * 2 = 16
Anche in questo caso si osserva subito che: 
24 = 2 * 2 * 2 * 2 = 2 * (2 * 2 * 2) = 2 * 23 = 2 * 24 - 1
Possiamo scrivere quindi la relazione generale: 
nm = n * nm - 1
Questa relazione dice che la potenza di ordine m del numero n si ottiene moltiplicando n per la potenza di ordine m-1 del numero n; anche questo algoritmo è chiaramente ricorsivo in quanto contiene un riferimento a se stesso.
Per calcolare questa funzione in modo ricorsivo, dobbiamo determinare la condizione di uscita dalla ricorsione; tale condizione può essere facilmente individuata osservando che, ad esempio, si ha: Dati allora tre numeri interi positivi n, a e b, con n diverso da 1, possiamo scrivere quindi in generale: Da questa formula ricaviamo subito: In definitiva, data la formula generale: 
nm = n * nm - 1
possiamo dire che la condizione di uscita dalla ricorsione è: 
(m - 1) = 0 e cioè: m = 1
In questo caso, infatti, si ha: 
nm - 1 = n1 - 1 = n0 = 1
Vediamo, ad esempio, come si calcola ricorsivamente la potenza con esponente 4 del numero 2: A questo punto abbiamo ottenuto tutti i fattori necessari, per cui, procedendo a ritroso si ottiene:

26.1 La ricorsione nei linguaggi di programmazione

I linguaggi di programmazione che supportano la ricorsione, permettono la definizione di sottoprogrammi ricorsivi; un sottoprogramma si definisce ricorsivo quando contiene una chiamata, diretta o indiretta, a se stesso.
Si ha la ricorsione diretta quando un sottoprogramma chiama direttamente se stesso; si ha, invece, la ricorsione indiretta quando un sottoprogramma A chiama un sottoprogramma B che, a sua volta, chiama di nuovo il sottoprogramma A.
In generale, dati n sottoprogrammi indicati con A1, A2, A3, ..., An, si ha la ricorsione indiretta quando A1 chiama A2 che chiama A3 e così via, sino ad An che chiama di nuovo A1.
Si può osservare che nel caso di ricorsione diretta, un sottoprogramma ricorsivo svolge allo stesso tempo il ruolo di caller e di callee!

Tra i casi più importanti di linguaggi di programmazione che supportano la ricorsione troviamo, ad esempio, il C e il Pascal; la ricorsione, invece, non viene supportata dalle vecchie versioni del BASIC e del FORTRAN77.

In Figura 26.1 vediamo l'implementazione non ricorsiva di un sottoprogramma che calcola il fattoriale di un numero n.
Figura 26.1 - Calcolo non ricorsivo di n!

In Figura 26.2 vediamo, invece, l'implementazione ricorsiva di un sottoprogramma che calcola il fattoriale di un numero n.
Figura 26.2 - Calcolo ricorsivo di n!

Nelle architetture a 16 bit, il tipo unsigned long del C rappresenta un intero senza segno a 32 bit compreso quindi tra 0 e 4294967295; il Pascal non dispone di un tale tipo di dato, per cui al suo posto si può utilizzare il Longint (intero con segno a 32 bit) che ci permette, però, di gestire interi positivi compresi tra 0 e +2147483647.
Nel calcolo del fattoriale di un numero n bisogna tenere presente che anche per valori di n relativamente piccoli, si possono ottenere come risultato numeri piuttosto grandi. Ad esempio, già 9! supera abbondantemente il valore massimo (65535) rappresentabile con 16 bit; analogamente, 13! supera il valore massimo (4294967295) rappresentabile con 32 bit!

In Figura 26.3 vediamo l'implementazione non ricorsiva di un sottoprogramma che calcola la potenza con esponente m di un numero n.
Figura 26.3 - Calcolo non ricorsivo di nm

In Figura 26.4 vediamo, invece, l'implementazione ricorsiva di un sottoprogramma che calcola la potenza con esponente m di un numero n.
Figura 26.4 - Calcolo ricorsivo di nm

In generale, si nota subito che la versione ricorsiva di un generico algoritmo è più compatta e più comprensibile della versione non ricorsiva; si nota, inoltre, che l'implementazione pratica di un algoritmo ricorsivo rispecchia fedelmente la formulazione matematica dell'algoritmo stesso.

26.2 La ricorsione in Assembly

Analizzando la Figura 26.2 e la Figura 26.4 si può avere l'impressione che la ricorsione sia una sorta di fenomeno "paranormale"; questa impressione è legata al fatto che un sottoprogramma ricorsivo sembra in grado di fornirci "magicamente" il risultato esatto dopo aver chiamato ripetutamente se stesso e senza aver effettuato, apparentemente, alcun calcolo!
In realtà, i fenomeni paranormali e le magie, ovviamente, non centrano niente; vediamo allora con l'ausilio dell'Assembly, come può essere svelato il "mistero" della ricorsione.

Supponiamo di voler implementare una procedura ricorsiva dotata di argomenti, variabili locali e valore di ritorno; il problema fondamentale che dobbiamo affrontare è legato al metodo da seguire per garantire che, ogni volta che la procedura chiama se stessa, vengano create nuove copie degli argomenti e delle variabili locali che non vadano a sovrascrivere le copie precedentemente inserite nello stack.
Per chiarire questo aspetto, vediamo un esempio pratico in Assembly, relativo al calcolo ricorsivo del fattoriale di un numero n; scriviamo una procedura fatt che riceve in BX un numero intero senza segno a 16 bit e restituisce in EAX il risultato a 32 bit.
In base a quanto detto in precedenza, per ottenere un risultato valido in EAX, dobbiamo inserire in BX valori compresi tra 0 e 12; affinché i calcoli si svolgano in modo corretto, prima di chiamare la procedura fatt è necessario azzerare i 16 bit più significativi di EBX. La prima versione di questa procedura, ispirata all'esempio di Figura 26.2, è la seguente: Sulla sinistra notiamo che per ogni istruzione è presente il relativo offset e il codice macchina prodotto dall'assembler; da queste informazioni si ricava che la procedura fatt viene definita all'offset 0064h di un segmento di codice.
Analizziamo in dettaglio quello che succede nel caso in cui fatt venga chiamata con (E)BX=3; in questo caso, fatt dovrebbe restituirci EAX=6. Per rendere più chiara la spiegazione viene mostrato, passo dopo passo, lo stato dello stack del programma; le condizioni iniziali sono rappresentate da SP=0200h e si assume, inoltre, che l'indirizzo di ritorno sia 0031h.

La CPU incontra nel programma principale una istruzione di chiamata NEAR a fatt ed esegue quindi i seguenti passi: Appena entrati in fatt abbiamo quindi: SP=019Eh e (E)BX=3, mentre in EAX viene caricato il valore 1; siccome BX è diverso da zero, la CPU salta all'istruzione DEC ed esegue i seguenti passi: Appena entrati ricorsivamente in fatt abbiamo: SP=019Ch e (E)BX=2, mentre in EAX viene caricato il valore 1; siccome BX è diverso da zero, la CPU salta all'istruzione DEC ed esegue i seguenti passi: Appena entrati ricorsivamente in fatt abbiamo: SP=019Ah e (E)BX=1, mentre in EAX viene caricato il valore 1; siccome BX è diverso da zero, la CPU salta all'istruzione DEC ed esegue i seguenti passi: Appena entrati ricorsivamente in fatt abbiamo: SP=0198h e (E)BX=0, mentre in EAX viene caricato il valore 1; siccome BX vale zero, la CPU salta all'etichetta exit_fatt e, incontrando l'istruzione RET, di tipo NEAR, esegue i seguenti passi: All'indirizzo CS:0072h troviamo l'istruzione MUL e in quel momento abbiamo: SP=019Ah, EAX=1 e (E)BX=0; l'istruzione MUL moltiplica EAX=1 per EBX=0 e ottiene EDX:EAX=0. Subito dopo la CPU incontra l'istruzione RET di tipo NEAR ed esegue i seguenti passi: All'indirizzo CS:0072h troviamo l'istruzione MUL e in quel momento abbiamo: SP=019Ch, EAX=0 e (E)BX=0; l'istruzione MUL moltiplica EAX=0 per EBX=0 e ottiene EDX:EAX=0. Subito dopo la CPU incontra l'istruzione RET di tipo NEAR ed esegue i seguenti passi: All'indirizzo CS:0072h troviamo l'istruzione MUL e in quel momento abbiamo: SP=019Eh, EAX=0 e (E)BX=0; l'istruzione MUL moltiplica EAX=0 per EBX=0 e ottiene EDX:EAX=0. Subito dopo la CPU incontra l'istruzione RET di tipo NEAR ed esegue i seguenti passi: Il programma principale riottiene il controllo e trova in EAX il valore zero che, chiaramente, non rappresenta il risultato corretto; ripetendo l'esperimento con altri valori passati a fatt nel registro (E)BX (escluso 0), si ottiene sempre EAX=0.

Come si spiega questa situazione?

Analizzando il meccanismo ricorsivo appena descritto, si intuisce subito che il problema risiede nel fatto che ad ogni chiamata ricorsiva di fatt, il registro BX viene decrementato di uno senza che sia preservato, però, il suo contenuto originario; dopo l'ultima chiamata ricorsiva, BX ormai vale zero, per cui la moltiplicazione produce un risultato nullo!
Tutte le successive moltiplicazioni tra EAX e EBX producono di conseguenza un risultato nullo in quanto il fattore EBX vale zero; dopo l'ultima moltiplicazione, il controllo torna al programma principale che trova EAX=0.

La soluzione a questo problema ci viene suggerita dal meccanismo appena descritto, che permette alla CPU di gestire correttamente nello stack gli indirizzi di ritorno relativi alle varie chiamate ricorsive di fatt; grazie a questo meccanismo, i vari indirizzi di ritorno vanno ad occupare sempre posizioni differenti nello stack, evitando così di sovrapporsi l'uno all'altro.
Possiamo utilizzare allora questa stessa tecnica per gestire nello stack la sequenza di valori che assume BX nel corso della ricorsione; in questo modo, possiamo evitare che le modifiche apportate a BX ci facciano perdere il contenuto originale.

In base alle considerazioni appena esposte, possiamo dire che la procedura fatt, subito dopo l'istruzione JZ, deve svolgere i seguenti passi: In seguito a queste modifiche, la procedura fatt assume il seguente aspetto: Proviamo a ripetere l'esperimento e vediamo cosa succede chiamando fatt con (E)BX=3; come al solito, supponiamo che la situazione iniziale dello stack sia SP=0200h e che l'indirizzo di ritorno al caller sia 0031h.

La CPU incontra nel programma principale una istruzione di chiamata NEAR a fatt ed esegue quindi i seguenti passi: Appena entrati in fatt abbiamo quindi: SP=019Eh e (E)BX=3, mentre in EAX viene caricato il valore 1; siccome BX è diverso da zero, la CPU salta all'istruzione PUSH ed esegue i seguenti passi: Appena entrati ricorsivamente in fatt abbiamo: SP=019Ah e (E)BX=2, mentre in EAX viene caricato il valore 1; siccome BX è diverso da zero, la CPU salta all'istruzione PUSH ed esegue i seguenti passi: Appena entrati ricorsivamente in fatt abbiamo: SP=0196h e (E)BX=1, mentre in EAX viene caricato il valore 1; siccome BX è diverso da zero, la CPU salta all'istruzione PUSH ed esegue i seguenti passi: Appena entrati ricorsivamente in fatt abbiamo: SP=0192h e (E)BX=0, mentre in EAX viene caricato il valore 1; siccome BX vale zero, la CPU salta all'etichetta exit_fatt e incontrando l'istruzione RET di tipo NEAR, esegue i seguenti passi: All'indirizzo CS:0073h troviamo l'istruzione POP e in quel momento abbiamo: SP=0194h, EAX=1 e (E)BX=0; la CPU esegue quindi i seguenti passi: Subito dopo la CPU incontra un'istruzione RET di tipo NEAR ed esegue i seguenti passi: All'indirizzo CS:0073h troviamo l'istruzione POP e in quel momento abbiamo: SP=0198h, EAX=1 e (E)BX=1; la CPU esegue quindi i seguenti passi: Subito dopo la CPU incontra un'istruzione RET di tipo NEAR ed esegue i seguenti passi: All'indirizzo CS:0073h troviamo l'istruzione POP e in quel momento abbiamo: SP=019Ch, EAX=2 e (E)BX=2; la CPU esegue quindi i seguenti passi: Subito dopo la CPU incontra un'istruzione RET di tipo NEAR ed esegue i seguenti passi: Questa volta il programma principale riottiene il controllo e trova in EAX il valore 6 che è, ovviamente, il risultato corretto; si può constatare che fatt calcola correttamente il fattoriale di tutti i numeri compresi tra 0 e 12.
Grazie all'uso dello stack, la procedura fatt può preservare il contenuto di BX prima di decrementarlo e passarlo ricorsivamente a se stessa; ad ogni chiamata ricorsiva, la procedura fatt gestisce un valore di BX indipendente dal valore relativo alle altre chiamate.

Il metodo appena illustrato, utilizza i registri per il passaggio degli argomenti alla procedura fatt; come già sappiamo, si tratta di un metodo che permette di ottenere una notevole efficienza. L'aspetto negativo è rappresentato dal fatto che in questo modo stiamo impegnando diversi registri che potrebbero servirci per altri scopi; la situazione poi tende a complicarsi quando utilizziamo ulteriori registri per definire anche variabili locali all'interno di una procedura.
Per ovviare a tutti questi inconvenienti, possiamo sfruttare i concetti esposti nel precedente capitolo in relazione alle convenzioni adottate dai linguaggi di alto livello per il passaggio degli argomenti alle procedure, per la creazione delle variabili locali e per i valori di ritorno; vediamo allora come possiamo implementare la procedura fatt seguendo le convenzioni dei compilatori C e Pascal.

La procedura fatt, in versione C, assume l'aspetto seguente: Il programma principale prima di chiamare fatt deve inserire nello stack un valore compreso tra 0 e 12, del quale vogliamo calcolare il fattoriale; subito dopo avviene la chiamata di fatt. All'interno di fatt, il parametro n viene letto dallo stack all'indirizzo SS:BP+4; questo perché fatt è una procedura di tipo NEAR.
Prima di chiamare ricorsivamente fatt dobbiamo inserire nello stack una copia dell'argomento n decrementato di 1; a tale proposito viene utilizzato il registro AX per evitare di modificare l'argomento n originale presente nello stack.
Subito dopo la chiamata ricorsiva di fatt dobbiamo ripulire lo stack sommando 2 byte a SP; ricordiamo, infatti, che secondo la convenzione C il caller è tenuto a ripulire lo stack dagli argomenti passati ad una procedura. Questo stesso lavoro deve essere effettuato dal programma principale una volta che ha riottenuto il controllo.

La procedura fatt in versione Pascal assume l'aspetto seguente: L'unica differenza rispetto alla versione C è rappresentata dal fatto che secondo la convenzione Pascal è compito del callee ripulire lo stack dagli argomenti passati ad una procedura; a tale proposito, la procedura fatt utilizza l'istruzione RET con l'operando immediato 2 che somma 2 byte a SP prima di restituire il controllo al caller.

Se vogliamo interfacciare queste procedure con i compilatori C e Pascal a 16 bit, dobbiamo ricordarci che i valori di ritorno a 32 bit devono essere restituiti in DX:AX e non in EAX; a tale proposito possiamo utilizzare l'istruzione: 
shld edx, eax, 16
Come è stato spiegato in un precedente capitolo, questa istruzione fa scorrere di 16 posti verso sinistra i bit di EDX; i 16 posti rimasti liberi a destra vengono riempiti con i 16 bit più significativi di EAX, mentre il contenuto di EAX rimane inalterato. Attraverso questa istruzione, il contenuto di EAX viene copiato in DX:AX; nel rispetto della convenzione little endian, il registro DX contiene la WORD più significativa di EAX. Ulteriori dettagli su questi argomenti vengono illustrati nei capitoli dedicati all'interfacciamento tra l'Assembly e i linguaggi di alto livello.

Analizziamo in dettaglio un ulteriore esempio rappresentato dalla versione Pascal di una procedura chiamata Potenza, che calcola ricorsivamente la potenza di ordine m di un numero n; questa procedura assume il seguente aspetto: Vediamo ora quello che succede quando il programma principale chiama Potenza con argomenti base=2 e esponente=3; se la procedura non contiene errori, dovrebbe restituirci in EAX il valore 23=8.
Supponiamo che le condizioni iniziali dello stack siano rappresentate da SP=0200h e che l'indirizzo di ritorno al caller sia 0033h.

La CPU incontra nel programma principale la seguente sequenza di istruzioni: ed esegue quindi i seguenti passi: Appena entrati in Potenza, incontriamo l'istruzione PUSH bp che preserva nello stack il contenuto originario di BP (che indichiamo con oldBP1); la CPU esegue quindi i seguenti passi: Subito dopo, il contenuto (0198h) di SP viene copiato in BP, per cui possiamo dire che il parametro n=2 si trova in SS:BP+6, il parametro m=3 si trova in SS:BP+4, l'indirizzo di ritorno 0033h si trova in SS:BP+2, mentre oldBP1 si trova in SS:BP.
A questo punto abbiamo quindi: SP=0198h, n=2 e m=3, mentre in EAX viene caricato il valore 1; siccome m è diverso da zero, la CPU salta all'istruzione PUSH n ed esegue i seguenti passi: Appena entrati ricorsivamente in Potenza, incontriamo l'istruzione PUSH bp che preserva nello stack il contenuto originario di BP (che indichiamo con oldBP2); la CPU esegue quindi i seguenti passi: Subito dopo, il contenuto (0190h) di SP viene copiato in BP, per cui possiamo dire che il parametro n=2 si trova in SS:BP+6, il parametro m=2 si trova in SS:BP+4, l'indirizzo di ritorno 0096h si trova in SS:BP+2, mentre oldBP2 si trova in SS:BP.
A questo punto abbiamo quindi: SP=0190h, n=2 e m=2, mentre in EAX viene caricato il valore 1; siccome m è diverso da zero, la CPU salta all'istruzione PUSH n ed esegue i seguenti passi: Appena entrati ricorsivamente in Potenza, incontriamo l'istruzione PUSH bp che preserva nello stack il contenuto originario di BP (che indichiamo con oldBP3); la CPU esegue quindi i seguenti passi: Subito dopo, il contenuto (0188h) di SP viene copiato in BP, per cui possiamo dire che il parametro n=2 si trova in SS:BP+6, il parametro m=1 si trova in SS:BP+4, l'indirizzo di ritorno 0096h si trova in SS:BP+2, mentre oldBP3 si trova in SS:BP.
A questo punto abbiamo quindi: SP=0188h, n=2 e m=1, mentre in EAX viene caricato il valore 1; siccome m è diverso da zero, la CPU salta all'istruzione PUSH n ed esegue i seguenti passi: Appena entrati ricorsivamente in Potenza, incontriamo l'istruzione PUSH bp che preserva nello stack il contenuto originario di BP (che indichiamo con oldBP4); la CPU esegue quindi i seguenti passi: Subito dopo, il contenuto (0180h) di SP viene copiato in BP, per cui possiamo dire che il parametro n=2 si trova in SS:BP+6, il parametro m=0 si trova in SS:BP+4, l'indirizzo di ritorno 0096h si trova in SS:BP+2, mentre oldBP4 si trova in SS:BP.
A questo punto abbiamo quindi: SP=0180h, n=2 e m=0, mentre in EAX viene caricato il valore 1; siccome m vale zero, la CPU salta all'etichetta exit_proc, dove incontra l'istruzione POP bp seguita dall'istruzione RET di tipo NEAR con operando immediato 4. La CPU esegue quindi i seguenti passi: All'indirizzo CS:0096h troviamo l'istruzione MOVZX, e in quel momento abbiamo: SP=0188h, EAX=1, n=2 e m=1; la CPU esegue quindi i seguenti passi: Subito dopo la CPU incontra l'istruzione POP bp seguita dall'istruzione RET di tipo NEAR con operando immediato 4 ed esegue i seguenti passi: All'indirizzo CS:0096h troviamo l'istruzione MOVZX, e in quel momento abbiamo: SP=0190h, EAX=2, n=2 e m=2; la CPU esegue quindi i seguenti passi: Subito dopo la CPU incontra l'istruzione POP bp seguita dall'istruzione RET di tipo NEAR con operando immediato 4 ed esegue i seguenti passi: All'indirizzo CS:0096h troviamo l'istruzione MOVZX, e in quel momento abbiamo: SP=0198h, EAX=4, n=2 e m=3; la CPU esegue quindi i seguenti passi: Subito dopo la CPU incontra l'istruzione POP bp seguita dall'istruzione RET di tipo NEAR con operando immediato 4 ed esegue i seguenti passi: Il programma principale riottiene il controllo e trova in EAX il valore 8 che è proprio il risultato di 23; osserviamo che per ottenere un risultato valido, nm non deve superare il massimo valore gestibile da EAX e cioè 4294967295 = 232-1).
A differenza di quanto accade con il C, il Pascal non supporta gli interi senza segno a 32 bit, ma solo gli interi con segno a 32 bit (Longint); il Pascal dispone, invece, del tipo comp che è un intero con segno a 64 bit, che può essere restituito da una procedura attraverso la cima dello stack (ST(0)) della FPU.

Dall'esempio appena svolto, possiamo dedurre alcune considerazioni importanti. Prima di tutto osserviamo che le strutture dati di tipo LIFO (Last In First Out) come lo stack, si prestano in modo perfetto per le procedure ricorsive; l'uso dello stack, quindi, permette di implementare in modo semplice ed efficiente gli algoritmi ricorsivi.
Affinché il meccanismo appena descritto funzioni in modo perfetto è fondamentale che il contenuto originario del registro BP venga rigorosamente preservato; non ci vuole molto a capire che in caso contrario, il programma andrebbe immediatamente in crash.

26.3 Vantaggi e svantaggi delle procedure ricorsive

Attraverso i vari esempi illustrati in precedenza, possiamo analizzare i vantaggi e gli svantaggi delle procedure ricorsive.
Il vantaggio fondamentale della ricorsione è rappresentato dall'estrema compattezza del codice scritto con questa tecnica; tale compattezza diventa particolarmente evidente nel caso di algoritmi di complessità medio alta (come viene mostrato più avanti).
Abbiamo anche visto che un algoritmo ricorsivo, esteriormente ha una struttura molto più semplice e comprensibile del corrispondente algoritmo non ricorsivo; è chiaro, però, che per riuscire a risolvere ricorsivamente problemi molto complessi, bisognerebbe essere dei geni della matematica. Questo non significa che gli algoritmi non ricorsivi siano più semplici da individuare rispetto a quelli ricorsivi; anzi, nella maggior parte dei casi è vero il contrario.

In generale, possiamo dire che gli svantaggi presentati dalla ricorsione superano abbondantemente i (pochissimi) vantaggi; di fatto, la possibilità di scrivere codice molto compatto è l'unico vantaggio degno di nota della ricorsione.
Analizzando i vari esempi di questo capitolo, si nota subito che le procedure in versione non ricorsiva permettono di spingere al massimo la sequenzialità del codice; come già sappiamo, più il codice è sequenziale, più sarà eseguito velocemente dalla CPU.
Le corrispondenti procedure in versione ricorsiva, invece, chiamano ripetutamente se stesse con sensibili ripercussioni sulle prestazioni dovute al tempo necessario per il trasferimento del controllo; la conseguenza di tutto ciò è data dal fatto che in generale, la versione non ricorsiva di una procedura è molto più veloce della corrispondente versione ricorsiva.
Il principale difetto delle procedure ricorsive è rappresentato sicuramente dal notevolissimo consumo di spazio nello stack; si tratta di un aspetto piuttosto delicato che nei casi estremi può portare alla saturazione di tutto il segmento di stack del nostro programma.
In una situazione del genere, ulteriori chiamate ricorsive comportano la scrittura di dati in aree della memoria che non appartengono allo stack; nei casi estremi vengono sovrascritte aree della memoria riservate al sistema operativo, con conseguente blocco del computer!

Per evidenziare questo aspetto, possiamo osservare quello che accade nel caso della procedura Potenza; la versione non ricorsiva di questa procedura richiede uno spazio minimo nello stack, pari a 8 byte. Questi 8 byte sono necessari per contenere l'indirizzo di ritorno (2 byte), il parametro n (2 byte), il parametro m (2 byte) e il contenuto originario di BP (2 byte); se si decide, inoltre, di preservare i vari registri generali utilizzati dalla procedura, si può arrivare a circa 16 byte di spazio necessario.
Per la versione ricorsiva di Potenza, la situazione cambia radicalmente; tale versione, infatti, ha bisogno di almeno 8 byte per ogni chiamata ricorsiva, più 8 byte per la prima chiamata effettuata dal caller.
Nel caso, ad esempio, di m=3, possiamo notare che sono necessari almeno: 
8 * (3 + 1) = 8 * 4 = 32 byte
Nel caso di m=20 si arriva ad una richiesta minima di spazio nello stack pari a: 
8 * (20 + 1) = 8 * 21 = 168 byte
In generale, la procedura ricorsiva Potenza, chiamata con l'esponente m, richiede un minimo di: 
8 * (m + 1) byte di spazio nello stack
Si tenga anche presente che Potenza è una procedura estremamente semplice; nel caso di procedure molto complesse, la situazione può facilmente degenerare nella completa saturazione dello stack.
Proprio questa caratteristica molto pericolosa, spinse i progettisti della IBM a non supportare la ricorsione nel linguaggio FORTRAN77; si tratta di un linguaggio di programmazione nato intorno al 1954 e destinato alla risoluzione dei problemi matematici con il computer. La sigla FORTRAN, infatti, è la contrazione di IBM Mathematical Formula Translation System; del resto, le disponibilità di memoria dei computer dell'epoca non permettevano certo l'implementazione di procedure ricorsive.

26.4 Le Torri di Hanoi

Per evidenziare ulteriormente le caratteristiche positive e negative della ricorsione, analizziamo in dettaglio un celebre algoritmo che permette di risolvere ricorsivamente un famoso gioco chiamato: Le Torri di Hanoi; si tratta di un antico gioco dell'estremo oriente, praticato dai monaci buddisti.
La Figura 26.5 mostra una rappresentazione schematica di questo gioco; l'obiettivo è quello di trasferire tutti i dischi dal palo A al palo C servendosi del palo B. Le regole del gioco sono le seguenti: La risoluzione di questo problema con un algoritmo non ricorsivo si presenta estremamente difficile; viceversa, il problema può essere risolto con un algoritmo ricorsivo caratterizzato da una sorprendente semplicità!

Cominciamo con due soli dischi indicati con 1 e 2 e osserviamo che, in questo caso, il gioco si risolve in modo molto intuitivo con le seguenti tre mosse: In pratica, spostiamo il disco 1 dal palo di partenza al palo intermedio; poi spostiamo l'unico disco rimasto (il numero 2), dal palo di partenza al palo di arrivo e infine spostiamo il disco 1 dal palo intermedio al palo di arrivo.
Queste tre mosse sono molto importanti perché rappresentano la condizione alla quale dobbiamo cercare di pervenire nel caso di 3 o più dischi; nel caso di 2 dischi, la sequenza delle tre mosse può essere generalizzata in questo modo: Vediamo come si può applicare in pratica questo algoritmo; nel caso di 3 dischi possiamo scrivere le tre mosse: Siccome non siamo in grado di effettuare le mosse 1 e 3, dobbiamo cercare di scomporle in due o più mosse, sino a pervenire al caso (che sappiamo risolvere) di due soli dischi; osserviamo subito che la mossa: 
1. Spostare 3-1 dischi (2 dischi) dal palo A al palo B, servendosi del palo C
può essere scomposta nelle seguenti mosse: Analogamente, la mossa: 
3. Spostare 3-1 dischi (2 dischi) dal palo B al palo C, servendosi del palo A
può essere scomposta nelle seguenti mosse: A questo punto possiamo affermare che nel caso di 3 dischi, il gioco può essere risolto con la seguente sequenza di 7 mosse: Nel caso di 4 dischi possiamo scrivere le tre mosse: Siccome non siamo in grado di effettuare le mosse 1 e 3, dobbiamo cercare di scomporle in due o più mosse, sino a pervenire al caso (che sappiamo risolvere) di due soli dischi; osserviamo subito che la mossa: 
1. Spostare 4-1 dischi (3 dischi) dal palo A al palo B, servendosi del palo C
può essere scomposta nelle seguenti mosse: Analogamente, la mossa: 
3. Spostare 4-1 dischi (3 dischi) dal palo B al palo C, servendosi del palo A
può essere scomposta nelle seguenti mosse: Le mosse 1a, 3a, 1b e 3b possono essere risolte con il metodo già spiegato per il caso di 3 dischi; alla fine, per il caso di 4 dischi, si ottiene la soluzione rappresentata dalla seguente sequenza di 15 mosse: A questo punto appare evidente che nel caso generale di N dischi possiamo scrivere le tre mosse: Questo algoritmo afferma che per spostare N dischi dal palo A al palo C, dobbiamo prima spostare N-1 dischi dal palo A al palo B attraverso il palo C; subito dopo dobbiamo spostare direttamente il disco rimasto, dal palo A al palo C e infine dobbiamo spostare N-1 dischi dal palo B al palo C attraverso il palo A.
Appare evidente il fatto che questo è un classico caso di algoritmo ricorsivo; indicando quindi con N il numero di dischi, con A il palo di partenza, con C il palo di arrivo e con B il palo intermedio, possiamo schematizzare questo algoritmo con il seguente pseudo-codice: La condizione di uscita dalla ricorsione è rappresentata da N=0; infatti, quando N diventa zero vuol dire che non ci sono più dischi da spostare.

Può sembrare incredibile, ma questo (apparentemente) insignificante algoritmo funziona in modo perfetto; in Figura 26.6 vediamo una implementazione reale scritta in Linguaggio C. Come si può notare, grazie alla sintassi "evoluta" dei linguaggi di alto livello, la struttura della funzione hanoi rispecchia fedelmente la formulazione matematica dell'algoritmo ricorsivo; tale funzione è formata da appena 5 linee di codice C ed evidenzia ulteriormente l'estrema compattezza degli algoritmi ricorsivi, anche nel caso di problemi complessi.

La Figura 26.7 mostra la versione Assembly del programma che risolve ricorsivamente il gioco delle Torri di Hanoi. Il programma HANOI.ASM è dettagliatamente commentato e dovrebbe risultare abbastanza chiaro e comprensibile; come si può notare, vengono utilizzate diverse procedure della libreria EXELIB (che può essere scaricata dalla sezione Librerie di supporto per il corso assembly dell’ Area Downloads di questo sito). Il numero di dischi da spostare viene inserito attraverso la procedura readUdec16; inserendo il valore zero, si provoca la terminazione del programma.
La procedura hanoi viene chiamata secondo le convenzioni C per il passaggio degli argomenti e per la pulizia dello stack; naturalmente si può modificare facilmente la procedura stessa in modo che segua la convenzione Pascal.
Le varie mosse da compiere vengono visualizzate attraverso la stringa messaggio; come si può notare, questa stringa termina con i tre codici ASCII 10 (avanzamento linea), 13 (ritorno carrello) e '$' che indica la fine di una stringa DOS.
La stringa messaggio ha queste caratteristiche in quanto viene visualizzata attraverso il servizio 09h (Display String) dell'INT 21h (servizi DOS) descritto in un precedente capitolo; questa scelta si rende necessaria in quanto, inserendo un numero relativamente alto di dischi da spostare, vengono visualizzate moltissime mosse che vanno a riempire tutto lo schermo scomparendo poi nella parte inferiore. Per poterle visualizzare tutte, possiamo usare appunto il servizio Display String che tratta lo schermo come se fosse il foglio di una macchina da scrivere; ogni volta che il cursore oltrepassa l'ultima linea visualizzabile, il servizio Display String fa scorrere automaticamente lo schermo verso l'alto. Anche la printf del C e la WriteLn del Pascal utilizzano questo servizio del DOS; purtroppo, come accade per tutti i servizi gestiti attraverso le interruzioni software, anche Display String presenta una estrema lentezza che condiziona tutto il programma.
La procedura writeString della libreria EXELIB è infinitamente più veloce di Display String in quanto scrive direttamente nella memoria video del PC; writeString, però, è in grado di sfruttare solo la parte visibile dello schermo. Tutti questi aspetti vengono illustrati in dettaglio nella sezione Assembly Avanzato.
Se si ha la necessità di memorizzare le mosse svolte dal programma, si può utilizzare la concatenazione dei file attraverso un comando del tipo: 
hanoi > mosse.txt
Questo comando dice al DOS che tutto l'output di HANOI.EXE deve essere inviato, non allo schermo, ma al file MOSSE.TXT; attraverso un qualunque editor di testo è possibile poi visualizzare il contenuto dello stesso file MOSSE.TXT.

Indubbiamente, si può restare impressionati dall'estrema compattezza e semplicità dell'algoritmo che risolve ricorsivamente il gioco delle Torri di Hanoi; per poter esprimere, però, una valutazione più completa su questo algoritmo, bisogna verificare anche altri aspetti, come la velocità e la richiesta di spazio nello stack.
Una caratteristica piuttosto evidente della procedura hanoi è data dal fatto che, al crescere del numero di dischi da spostare, cresce in modo impressionante il numero delle mosse necessarie; parallelamente si registra un sensibile calo della velocità di esecuzione, legato evidentemente alla notevole crescita del numero di chiamate ricorsive.
Per analizzare in dettaglio questi aspetti, possiamo cercare prima di tutto di individuare la relazione che esiste tra il numero N di dischi da spostare e il numero M di mosse necessarie; in termini matematici, si tratta di determinare la funzione: 
M = f(N)
Eseguendo il programma HANOI, possiamo ricavare questa funzione in modo empirico; osserviamo subito che: Analizzando questi risultati possiamo ricavare la relazione generale che esiste tra N e M; infatti, risulta evidente che: 
M = 2N - 1
Questa relazione ci dice che al crescere del numero N di dischi, il numero M di mosse cresce in modo direttamente proporzionale alla potenza con esponente N di 2; tutto ciò giustifica il fatto che quando si va oltre i 10 dischi, si comincia a notare un sensibile rallentamento del programma, anche con CPU piuttosto potenti.
Nel caso, ad esempio, di N=16, sono necessarie ben: 
216 - 1 = 65535 mosse!
Queste considerazioni sono piuttosto preoccupanti se pensiamo che per ciascuna chiamata della procedura hanoi sono necessari almeno 12 byte di stack (2 per il parametro n, 2 per dalPalo, 2 per alPalo, 2 per viaPalo, 2 per l'indirizzo di ritorno e 2 per BP); questo significa che se il numero di chiamate ricorsive fosse pari al numero di mosse, con N=16 avremmo bisogno di ben: 
65535 * 12 = 786420 byte di stack!
Fortunatamente, però, le cose non stanno esattamente così; per rendercene conto, possiamo provare a seguire il percorso delle varie chiamate ricorsive del programma hanoi. La Figura 26.8 mostra lo schema di chiamata di hanoi nel caso di N=3; le linee rosse indicano i percorsi di andata, mentre le linee blu indicano i percorsi di ritorno. A questo punto è perfettamente inutile continuare in quanto si capisce subito che con N=3, non verranno mai superati i 48 byte di spazio necessario nello stack; questi 48 byte sono relativi quindi alla prima chiamata di hanoi effettuata dal CALLER e ai tre livelli di ricorsione indicati in Figura 26.8 con LIVELLO 1, LIVELLO 2 e LIVELLO 3. In pratica, la massima occupazione di spazio nello stack verrà raggiunta quando N diventa zero.

Ripetendo lo schema di Figura 26.8 per diversi valori di N, si può constatare che: 
12 * (1 + 1) con 1 livello di ricorsione
12 * (2 + 1) con 2 livelli di ricorsione
12 * (3 + 1) con 3 livelli di ricorsione
12 * (4 + 1) con 4 livelli di ricorsione
e così via.

Generalizzando quindi, possiamo dire che se vogliamo spostare N dischi, abbiamo bisogno come minimo di: 
12 * (N + 1) byte di spazio nello stack.
Nel caso, ad esempio, di N=16, ci servono "solamente" 204 byte e non 786420.

L'esempio delle Torri di Hanoi ci fa capire ulteriormente quanto sia importante l'analisi dettagliata del comportamento di un determinato algoritmo ricorsivo; in questo modo è possibile evitare spiacevoli sorprese in fase di esecuzione di quei programmi che fanno uso della ricorsione.
Si tenga presente che lo stack overflow (superamento della capacità massima del segmento di stack) è uno dei bug più pericolosi e più difficili da scovare; proprio per questo motivo, i compilatori dei linguaggi di alto livello offrono al programmatore la possibilità di inserire automaticamente nei programmi il codice necessario per la verifica dello stack overflow.

Gli algoritmi ricorsivi rappresentano un settore della matematica che, con l'avvento del computer, ha accresciuto enormemente la sua importanza; infatti, moltissimi problemi matematici possono essere formulati in modo ricorsivo. La ricorsione viene largamente applicata anche nei programmi che sfidano gli esseri umani nel gioco degli scacchi; per ulteriori approfondimenti si può fare riferimento ai numerosi libri che trattano questo argomento.