La ricorsione - 1° post

C'era una volta un re che chiese alla sua serva raccontami una favola e la serva incominciò e disse:

c'era una volta un re che chiese alla sua serva raccontami una favola e la serva incominciò e disse:

c'era una volta un re che chiese alla sua serva raccontami una favola e la serva incominciò e disse: c'era una volta .....

La filastrocca che apre questo articolo potrebbe essere la metafora, espressa nella lingua italiana, della ricorsione.

In generale un oggetto si può definire ricorsivo quando viene definito in termini di se stesso.

All'interno del corpo di una funzione è possibile, naturalmente, inserire chiamate ad altre funzioni dichiarate esternamente, ma è anche possibile invocare la funzione stessa. In questo secondo caso parliamo di funzione ricorsiva.

Per poter definire un processo ricorsivo occorrono:

1. Una condizione che permetta di stabilire se si è di fronte ad un caso particolare risolvibile banalmente
2. La soluzione del caso particolare
3. La soluzione più generale che contiene una o più chiamate ricorsive.

Primo esempio: il problema del fattoriale di un numero

Occupiamo del calcolo ricorsivo del fattoriale di un numero.

1. La condizione che ci permette di individuare il caso particolare è n == 0
2. Soluzione del caso particolare 0! = 1 se n == 0
3. Soluzione del caso più generale n! = (n - 1)! * n se n > 0

Scriviamo una implementazione C++ della funzione:

int fattoriale(int n){

if(n > 0)

return fattoriale(n - 1) * n;

else

return 1;

}

void main(void){

int n;

cout << "Digitare un numero intero" << endl;

cin >> n;

cout << " il fattoriale di " << n << " è " << fattoriale(n);

}

Secondo esempio: il problema delle Torri di Hanoi

Questa volta vedremo come la ricorsione ci condurrà ad una soluzione decisamente elegante e pulita del noto problema delle Torri di Hanoi.

Semplificando all’osso, si tratta di spostare una serie di
anelli concentrici da una pertica di partenza ad una di destinazione
appoggiandosi su una pertica di appoggio.

Una sola regola non sovrapporre anelli di diametro superiore
ad anellli di diametro inferiore.

Qui la soluzione ricorsiva si dimostra straordinariamente semplice, elegante ed efficace.

L’idea è questa: supponiamo di avere una funzione capace di spostarmi (n –1) anelli dalla pertica di partenza a quella di appoggio, lavorando su quella di destinazione potrei portarmi nella seguente situazione:

Il passo successivo consiste nello spostare semplicemente l’anello più grande rimasto dalla pertica di partenza a quella di destinazione.

La soluzione si completa riutilizzando la funzione precedentemente ipotizzata per spostare gli

(n-1) anelli dalla pertica di appoggio a quella di destinazione, lavorando sulla pertica di partenza.

Per implementare una soluzione ci serviremo di Matlab creando una funzione ricorsiva in uno script m-file. La funzione viene scritta seguendo esattamente la strategia appena illustrata.

Nella funzione sono facilmente individuabili:

1. la condizione che discrimina il caso generale dal caso banale
2. il caso generale viene risolto con una chiamata ricorsiva alla stessa funzione, uno spostamento e una seconda chiamata ricorsiva
3. il caso banale (spostamento di un solo anello) si risolve con lo spostamento dell'anello

Usiamo la funzione appena scritta per spostare tre anelli dalla pertica 1 alla 3

La funzione restituisce gli spostamenti e ci garantisce che in 7 mosse il gioco è chiuso.

Se gli anelli da spostare sono 4 gli spostamenti da eseguire sono 15. All'aumentare degli anelli crescono qli spostamenti da effettuare per risolvere il problema. La ricorsione ci garantisce comunque una soluzione.

Nel prossimo post vedremo la ricorsione applicata alla grafica, parleremo di frattali e il concetto di ricorsione continuerà a stupirci.