L’idea
L’idea alla base della ricorsione è essenzialmente quella di creare una funzione che richiama se stessa. Normalmente un’operazione del genere porterebbe ad un loop infinito e ad un conseguente stack overflow. Per questa ragione è necessario che la ricorsione agisca su una quantità di dati assolutamente finita. La funzione dovrà richiamare se stessa solo se esistono ancora dati da elaborare (che passerà come parametro) e concludersi in caso contrario.
Usare un algoritmo ricorsivo è la soluzione ottimale per visitare una struttura ad albero.
L’idea è quella di creare funzioni molto semplici che ricevono come parametro un nodo della ramificazione, lo elaborano e richiamano se stesse tante volte quante sono le ramificazioni del nodo corrente, passando come parametro le ramificazioni successive.
Le chiamate progressive finiscono quando vengono raggiunti i nodi “foglia” dell’albero stesso.
Per quanto potente la ricorsività presenta essenzialmente due problemi. In primo luogo, se non è ben gestita, genera loop infiniti che portano al collasso dell’applicazione. In secondo luogo, anche quando vengono correttamente gestiti, generano come conseguenza un considerevole carico sullo stack. Il consiglio, proprio per questa ragione, è di ridurre al minimo la quantità di dati passate alla funzione ricorsiva utilizzando, tipicamente, dei passaggi per indirizzo, dei riferimenti o delle strutture statiche.
L’esempio
Nell’esempio seguente viene implementato un semplice algoritmo ricorsivo per scandire le cartelle all’interno di una tipica struttura ad albero: il File-System.
Viene implementata una funzione in grado di scandire tutti i file all’interno di una cartella passata come parametro. Quando, durante la scansione, viene incontrata una cartella, la funzione chiama un’altra versione di se stessa, passando come parametro la cartella trovata.
L’algoritmo termina quando non vi sono più cartelle da scandire.
Il Linguaggio: C#, Framework.NET 1.1
Il Codice:
using System;
using System.IO;
namespace RicorsioneSuFS
{
class Class1
{
[STAThread]
static void Main (string[] args)
{
DirectoryInfo d=new DirecotryInfo("C:DirectoryIniziale");
LeggiFileCartella(d);
}
static void LeggiFileCartella(DirectoryInfo pDir)
{
DirectoryInfo d=pDir;
DirectoryInfo[] subd=d.GetDirectories();
foreach (DirectoryInfo dd in subd)
{
if (dd.Attributes==FileAttributes.Directory)
{
LeggiFileCartella(pDir);
}
else
{
Console.WriteLine(dd.FullName);
}
}
}
}
}
Pubblicato su www.itvirtualcommunity.net, www.itvc.net il 12/9/2004
zabolab 