Usare algoritmi ricorsivi per sfogliare strutture ad albero

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

About Paolo Zaboi 44 Articles
Fermamente convinto che "I predatori dell'Arca Perduta" sia uno dei migliori film della storia del cinema, vive e passa il suo tempo in quel di Milano. Adora i film commercialissimi, tutto ciò che è Marvel, le vecchie avventure grafiche della Lucas e le serie TV. Giocatore (nel poco tempo libero) su Pc e Playstation, con fiducia e speranza, attende dagli anni '80 l'uscita della prossima console Atari. Ha creato questo blog un po' per spirito di condivisione... è un po' per scrivere in libertà di tutto quello che gli piace. Odia leggere i lunghi profili sui blog per questo il resto lo trovate solo su Linkedin: https://www.linkedin.com/in/paolozaboi ------ Firmly convinced that "Riders of the Lost Ark" is one of the best movies in cinema history, he lives and spend all his time in Milan. He loves movies, everything Marvel, Lucas's old graphic adventures and TV series. Player (in leisure time) on PC and Playstation, with confidence and hope, expects the release of the next Atari console from the 1980's. He created this blog (maybe...) for sharing spirit ... or simply to write free about anything he loves. He hates reading long profiles on blogs so all the rest is on Linkedin: https://www.linkedin.com/in/paolozaboi