Ricorsione

Le basi della ricorsione

Accade spesso che il modo più naturale per progettare l'algoritmo sia applicare l'algoritmo stesso; un algoritmo ricorsivo che costruisca una sua parte richiamando se stesso è detto ricorsivo.

Esempio di conto alla rovescia

Metodo che vuole stampare a schermo il conto alla rovescia partendo da 3:

• Stampa 3;
• Chiama ContoAllaRovescia(2);
• Stampa 2;
• Chiama ContoAllaRovescia(1);
• Stampa 1;
• Chiama ContoAllaRovescia(0);
• Ritorna al metodo principale.

La ricorsione in questo caso è possibile perché a ogni chiamata del metodo corrisponde una copia distinta della variabile num che è locale alla chiamata corrispondente. Se il numero fosse composto da una sola cifra, potremmo addirittura usare un costrutto switch che ad ogni numero associa il suo nome in parola.

Unendo queste due modalità, posso creare un unico metodo che, dato un numero di più cifre, scriva in ordine il nome dei numeri che lo compongono (per esempio, se voglio stampare a video 987, il mio algoritmo parte, vede che il numero non è <10, così lo divide per 10, ottiene 98, lo divide nuovamente e ottiene 9, che può stampare a video. Vedi esempio a pag 268...).

Quando viene effettuata una chiamata ricorsiva, essa viene eseguita e il resto dell'algoritmo resta come in pausa, e verrà concluso una volta che il metodo ricorsivo sarà terminato. Nella stessa maniera, se il metodo ricorsivo chiama al suo interno un metodo ricorsivo, il primo terminerà la sua esecuzione solo una volta che sarà terminato anche l'ultimo, e così via.

Linee guida per un corretto uso della ricorsione

La struttura di base per una corretta definizione di un metodo ricorsivo è la seguente:

• Nel blocco dell'istruzione devono essere previsti uno o più casi nei quali il metodo può eseguire o non un metodo ricorsivo; il nucleo della definizione del metodo deve quindi contenere un blocco else o qualche altra istruzione condizionale che permetta di gestire i diversi casi in base alle proprietà del parametro del metodo;