Totem's Lair: Guida al Vb.Net, La ricorsione

A20. La ricorsione

Si ha una situazione di ricorsione quando un metodo richiama sè stesso all'interno del proprio corpo, e tale metodo viene detto ricorsivo. L'algoritmo per cercare i file, ad esempio, è ricorsivo e ve ne dò una dimostrazione, assumendo di avere già un'arraylist in cui piazzare i nomi dei file:

Public Sub Search(ByVal Dir As String)
    'Pone tutte le sottodirectory in un array
    Dim Dirs() As String = IO.Directory.GetDirectories(Dir)
    'Pone tutti i file nella cartella in un array
    Dim Files() As String = IO.Directory.GetFiles(Dir)

    'Ogni file viene poi posto nella lista (percorso completo)
    For Each S As String In Files
        lstFiles.Add(S)
        Application.DoEvents()
    Next
    
    'Mentre ogni altra sottocartella viene analizzata ulteriormente
    For Each S As String In Dirs
        Search(S) 'Qui la procedura richiama sè stessa
    Next
End Sub

Come avete visto, nel secondo ciclo For, viene richiamata la stessa procedura di cui si sta definendo il corpo: questo implica che l'algoritmo si ripeta e vada sempre più in profondità, fino a 'toccarè il fondo e quindi risalire, con un procedimento simile a questo:

Analizza la cartella: trova 12 files e 2 sottocartelle
|--Analizza sottocartella 1: trova 2 files e 1 sottocartella
|  |--Analizza sottocartella 1: trova 45 files
|--Analizza sottocartella 2: trova 0 files e 3 sottocartelle
|  |--Analizza sottocartella 1: trova 10 files
|  |--Analizza sottocartella 2: trova 9 files
|  |--Analizza sottocartella 3: trova 11 files
-Fine

Un altro esempio famoso è quello del calcolo del fattoriale: un numero n fattoriale si indica con n! ed è uguale al prodotto di tutti i numeri interi positivi da 1 a n (compreso). Quindi 3! sarà 1*2*3=6. L'esempio dell'algoritmo è questo:

Function Fattoriale(ByVal N As Byte) As Int64
  If N = 1 Then
    Return 1
  Else
    Return N * Fattoriale(N - 1)
  End If
End Function

Il procedimento è simile a questo (con 5!):

5 <> 1 --> 5! = 5 * 4!
|--4 <> 1 --> 4! = 4 * 3!
|  |--3 <> 1 --> 3! = 3 * 2!
|  |  |--2 <> 1 --> 2! = 2 * 1!
|  |  |  |--1 = 1 --> 1! = 1
|  |  |--2! = 2 * 1 = 2
|  |--3! = 3 * 2 = 6
|--4! = 4 * 6 = 24
5! = 5 * 24 = 120

Semplice, no?

The Totem's Lair - Copyright (C) 2009
È vietata la riproduzione sia totale che parziale del sito.