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

Achille, la Tartaruga e il dilemma di un certo Zenone…

 

L’Idea

“…Il prode Achille e la piccola tartaruga decidono di fare   una gara di velocità. Achille, sicuro di vincere decide di dare un bel  vantaggio alla tartaruga. Come potrebbe mai perdere il grande  guarriero contro il piccolo e lento animale? ….La tartaruga parte e Achille aspetta. Solo dopo qualche minuto il prode Achille parte all’inseguimento. Achille, in ogni minuto, dimezza la  distanza che lo separa dalla tartaruga… riuscirà mai l’eroe a raggiungere la sua avversaria?”.

Se aveste fatto questa domanda a Zenone di Elea, matematico e filosofo   vissuto in Grecia nel V secolo avanti Cristo, vi avrebbe risposto tranquillamente di no.

Immaginate che la distanza tra Achille e la tartaruga sia un numero intero che continuate a dividere per due ad ogni minuto della gara. Il risutato, per quanto piccolo, non sarà mai uguale a zero, bensì sarà un   numero decimale sempre più piccolo.

Come risolvere il problema dal punto di vista matematico?

Il buon senso lascia pensare che Achille, ovviamente, prima o poi renderà nulla la sua distanza dalla tartaruga, certo…. ma sapreste dimostrarlo?

Questa situazione, rimasta paradossale per quasi duemila anni, ha preso il nome di “Paradosso di Zenone” ed è stata risolta solo in tempi relativamente recenti.

Dove stava l’errore del matematico e filosofo greco?

Ritorniamo all’esempio.

Dopo il primo minuto Achille avrà ridotto la sua distanza ad 1/2 della distanza iniziale. Il minuto seguente sarà diventata 1/4 di   quella iniziale…poi 1/8… 1/16….1/32 e così via all’infinito… Un   numero sempre più piccolo, quindi, ma mai uguale a 0.

Zenone concludeva, quindi, che la somma di tali grandezze desse un valore   infinito.

1/2+1/4+1/8+1/16…= infinito, quindi?

L’errore sta proprio qui.

Zenone credeva che la somma di infinite grandezze debba per forza   dare una grandezza infinita.

Come ci dimostra il calcolo infinitesimale non è sempre così…infatti:

1/2+1/4+1/8+1/16…= 1

Dimostriamolo:

Data la precedente serie e dato x=1/2, moltiplichiamo la serie ottenuta per (1-x).

(1-x)(x1+x2+x3+x4…) = x-xn+1  

e cioè:

x1+x2+x3+x4…=  (x-xn+1   )/(1-x)

Se x corrisponde ad 1/2 la somma totale degli spazi sarà

(1/2)/(1/2)=1

Questo vuol dire che il tempo impiegato da Achille non sarà   infinito…bensì finito. Quesa conclusione ci porta a trattare il problema   come un semplice problema di cinematica. Mettiamo in fila i nostri dati per   risolvere il problema:

– Distanza iniziale Achille-Tartaruga = 1000 metri.

– Velocità Achille = 10 m/s

– Velocità Tartaruga = 1 m/s

quindi:

Lo spazio percorso da Achille, dato da 10t, deve risultare uguale alla   somma del vantaggio iniziale della tartaruga con lo spazio che essa percorre.   Si ottiene così l’equazione : 10t=1000+t

Proviamo a risolverla….

10t – t = 1000

9t = 1000

t = 1000 / 9

t = 111,(1) sec.

Il buon Achille, riesce a raggiungere la tartaruga e Zenone, dopo duemila   anni, dorme sonni tranquilli.

L’esempio

Nell’esempio seguente proviamo a simulare la gara tra Achille e la   Tartaruga con un piccolo programma ricorsivo scritto in C#. L’esempio mette   in evidenza come, nonostante la corretta implementazione del paradosso, non   sia possibile rappresentarlo realmente su una macchina di qualsiasi genere.

Questo perchè la distanza tra Achille e la Tartaruga deve, per forza di   cose,essere rappresentata in una variabili di grandezza finita. Come   anticipato il valore diventa sempre più piccolo ma non dovrebbe mai diventare   uguale a zero, bensì un valore decimale sempre più piccolo…

Le variabili però, per forza di cose, possono rappresentare solo un   numero finito di valori decimali (più o meno grande)… così quando il valore   diventa troppo piccolo per essere rappresentato…. Achille raggiunge la   tartaruga!!!!

 

NOTA: A scopo puramente didattico provate ad utilizzare variabili diverse   per rappresentare la distanza Achille-Tartaruga…. cosa succederà?

 

Il Linguaggio: C#, Framework.NET 1.1
Il Codice:

using System;
namespace ZenoneInCSharp
{
    class Class1
    {
     [STAThread] 
     static void Main(string[] args)
     { 
       Console.WriteLine("Achille e la Tartaruga: un'implementazione del paradosso di Zenone. n");
       Zenone(ref x);
     } 
     static public int min=0;
     static public decimal x=1000;
     static void Zenone(ref decimal x)
     {
       if(x>0)
       {
          Console.WriteLine("Achille dista " + x + " metri dalla tartaruga dopo " + min + " minuti.");
          Console.Writeline("(Premi Invio)");
          Console.ReadLine();
          x=x/2;
          min++;
          Zenone(ref x);
       }
       else
       {
          Console.WriteLine("Achille prende la tartaruga in" + min + " minuti.");
          Console.WriteLine("abbiamo uno spazio FINITO di memoria per contenere la distanza.");
          Console.Writeline("In caso contrario la tartaruga, in virtù del paradosso vincerebbe la gara.");
          Console.ReadLine();
       }

    }
  }
}

Pubblicato  su www.itvirtualcommunity.net, www.itvc.net il 21/10/2004