Massimiliano Peluso

Microsoft .NET MCAD

Benvenuto nel mio Blog
posts - 6, comments - 139, trackbacks - 6

Strutture Ricorsive

Strutture Ricorsive 

Massimiliano Peluso 

 

A volte abbiamo la necessita di operare sui dati in modo ripetitivo. Quando ci troviamo in questa situazione, generalmente si pensa ad utilizzare delle strutture cicliche come  For each..., Do while ... ecc. in modo da iterare sui dati per ottenere un risultato finale. La struttura ricorsiva non è altro che una funzione o una procedura che richiama se stessa un numero non definito di volte, generalmente fin quando è soddisfatta una determinata condizione. Per comprendere le strutture ricorsive bisogna abbandonare l'idea di iterare sui dati e immagginare di iterare sul codice. Pensiamo, per esempio, ad una funzione che calcoli il fattoriale di un numero...

Function Fattoriale(ByVal numero As Double) As Double
  Dim risultato As Double = numero 
  Dim i as Integer
    If numero = 0 Then
       risultato = 1
    Else
      For i = numero - 1 To 1 Step -1
        risultato = risultato * i
      Next 
   End If
  Return risultato
End Function

Questa è la soluzione più intuitiva e simile al nostro modo di pensare, ma la struttura ricorsiva permette di ottenere lo stesso risultato con un codice più compatto e leggibile: 

Function Fattoriale(ByVal numero As Double) As Double 
  If numero = 0 Then
     Return 1
  Else
     Return numero * (Fattoriale(numero - 1))
 End If
End Function

Come avrete notato nell'esempio con la " For..Next " non facciamo altro che iterare sui dati un numero di volte definitito dal valore che viene passato alla funzione. Con la struttura ricorsiva, non iteriamo sui dati bensì sul codice. N ell'esempio la funzione chiama se stessa fin quando il valore passato non è 1. Quando questo accade la ricorsione termina e la funzione restituisce 1; ma a chi lo restituisce?
La risposta è : a se stessa,
o meglio alla chiamata precedente, che a sua volta risolve l'operazione lasciata in sospeso e passa il risultato alla chiamata ancora precedente fin quando non si arriva alla prima chiamata e il risultato viene restituito. Quindi e come se tra chiamate consecutive, venissero passete " porzioni di codice " da eseguire. Per capir meglio cosa accade basta osservare lo schema sottostante.

Supponiamo di chiamare la funzione fattoriale passando il numero 3

...
dim risultato as double=Fattoriale(3)
...

1^ Chiamata
                 return 3 * fattoriale(2)

2^Chiamata
                 return 2 * fattoriale (1)

3^ chiamata
                 return 1  * fattoriale (0)

4^ chiamata

                return 1 \'fine della ricorsione

Arrivati alla quarta chiamata la ricorsione termina restituendo il valore "1" risultato dalla chiamata " fattoriale(0) ".
Quindi il runTime è in grado di risolvere la terza chiamata che diventa: " 1 * 1 = 1 ". Questo è il risultato di  "fattoriale(1) " che viene restituito a sua volta alla seconda chiamata che diventa          " 2 * 1=2  "  che è il risultato di "fattoriale(2) ". Questo viene infine restituito alla prima chiamata che diventa  " 3 * 2=6  " che è il risultato di fattoriale(3) che viene restituito. So che il discorso può apparire contorto e verrebbe voglia di non utilizzare mai le funzioni ricorsive, ma ci sono casi in cui il loro impiego è insostituibile.
Per esempio, se volessimo creare una funzione che " navigasse " all'interno di una struttura ad albero, come per esempio può essere la struttuta delle directory di un Hard-Disk, con le normali funzioni iterative il compito potrebbe essere arduo ed il codice molto complesso. Con le funzioni ricorsive il tutto diventa semplice e immediato.
Supponiamo di voler creare una procedura che data una directory restituisca le propie subDirectory:

L'esempio assume l'inserimento della seguente istruzione: Imports System.IO


Per essere allineati con l'esempio creiamo una struttura di directory in C:\ come la sottostante

 

Sub getSubdir(ByVal dir As String)
 Dim d As New DirectoryInfo(dir) 
 Dim subDir As DirectoryInfo
 If Not (d.GetDirectories Is Nothing) Then
   For Each subDir In d.GetDirectories
      Console.WriteLine(subDir.Name.ToString)
      getSubdir(subDir.FullName)
   Next
 End If
End Sub

Prima di analizzare la procedura è bene fare un piccolo accenno alla classe DirectoryInfo.
La classe DirectoryInfo espone numerosi metodi che permettono di effettuare varie operazioni sulle directory. Nell'esempio viene utilizzato il metodo DirectoryInfo.GetDirectories() che restituisce una matrice di oggetti DirectoryInfo che rappresentano le subDirectory di primo livello della directory passata al costruttore. 

Nell'esempio viene instanziato un oggetto directoryInfo passando al costruttore il percorso della directory di cui si vuole analizzare la struttura. Se esistono subDirectory, si entra nel ciclo e per ogni elemento della matrice la procedura chiama se stessa passando come parametro il percorso completo della subDirectory trovata. Questo si ripete fin quando non è stato attraversato tutto l'albero della directory iniziale. Per capir meglio cosa accade in memoria durante l'esecuzione della procedura si può osservare lo schema sottostante


Anche se la procedura precedente è stata studiata per scopi didattici, in quanto restituisce i dati in modo non strutturato ma semplicemente stampandoli a video, con poche modifiche potremo "riciclarla" per popolare automaticamente un controllo TreeView con la struttura di una directory, un pò come fà esplora risorse di Windows.

Prima di tutto bisogna creare un nuovo progetto Window Forms e inserire un controllo TreeView.

--Aggiungere un controllo TreeView al form e rinominarlo con "Tree"
Ora bisogna creare il nodo principale che poi verrà passato al sub "Ricorsiva"
--nell'evento load del form...

Tree.Nodes.Add("C:\A")
Ricorsiva("C:\A", Tree.Nodes(0))

Sub Ricorsiva(ByVal d As String, ByVal nodo As TreeNode)
  Dim dCiclo As DirectoryInfo
  Dim dir As New DirectoryInfo(d)
  For Each dCiclo In dir.GetDirectories
    Ricorsiva(dCiclo.FullName, nodo.Nodes.Add(dCiclo.Name))
  Next
End Sub

Questo è il risultato:

Il trucco sta nella chiamata " Ricorsiva(dCiclo.FullName, nodo.Nodes.Add(dCiclo.Name)) ".

La prima volta che viene eseguita la procedura gli viene passato un nodo del treeView che può contenere a sua volta una collezione di nodi. Quindi la Sub non fà altro che aggiungere il nodo che gli viene passato e richiamare se stessa passando di volta in volta  il riferimento al nodo appena aggiunto. Le differenze dalla procedura precedente sono minime : invece di stampare a video le directory, vengono aggiunti dei nodi al TreeView. La procedura funziona correttamente, ma per directory che hanno diversi livelli di "annidamento", come può essere la directory "Root" di un Hard-Disk , non è molto performante in quanto verrebbe analizzato l'intero albero prima di produrre il risultato. Volendo ottimizzare il tutto, si potrebbe inizializzare l'albero con il nodo rappresentante la directory di partenza. Poi tramite un evento, intercettare il click sui nodi dell'albero, e passare il percorso della direcrory " cliccata " ad una procedura che espanda le subDirectory di primo livello. 

 Conclusioni

Penso che dopo questi esempi abbiate cambiato idea sulle funzioni e procedure ricorsive, che per quanto siano ostili nella compresione, ci aiutano nel risolvere compiti altrimenti difficili da realizzare, soprattutto nell'elaborazione dei dati con strutture gerarchiche.

Print | posted on lunedì 30 agosto 2004 10.22 |

Comments have been closed on this topic.

Powered by:
Powered By Subtext Powered By ASP.NET