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.