La ricorsione è uno degli strumenti più eleganti della programmazione: una funzione che richiama se stessa per risolvere istanze progressivamente più piccole di un problema. Per visitare strutture ad albero — come il filesystem, alberi di categorie o strutture XML — è spesso la soluzione più naturale ed efficiente. Questo articolo spiega il concetto e lo illustra con un esempio concreto in C#.

Come funziona la ricorsione

L’idea alla base è semplice: una funzione riceve un nodo come parametro, lo elabora, e si richiama tante volte quante sono le ramificazioni figlio del nodo corrente. Le chiamate progressive terminano quando si raggiungono i nodi “foglia” — quelli senza figli.

Senza una condizione di uscita ben definita, la ricorsione genera un loop infinito che porta allo stack overflow. La funzione deve quindi richiamare se stessa solo se esistono ancora dati da elaborare.

Vantaggi e limiti

• Vantaggio principale: codice compatto ed espressivo per navigare strutture gerarchiche di profondità arbitraria.
• Limite 1: senza gestione corretta della condizione di uscita, genera loop infiniti.
• Limite 2: ogni chiamata aggiunge un frame allo stack. Su strutture molto profonde si rischia stack overflow anche con logica corretta.
• Best practice: minimizzare i dati passati come parametro — meglio passare riferimenti o indici che copiare oggetti interi.

Esempio: scansione ricorsiva del filesystem in C#

L’esempio implementa una scansione ricorsiva delle cartelle di un filesystem. La funzione LeggiFileCartella riceve una cartella, la percorre, e per ogni sottocartella trovata si richiama passando la sottocartella come nuovo parametro. L’algoritmo termina quando non vi sono più sottocartelle da visitare.

using System;
using System.IO;

namespace RicorsioneSuFS
{
    class Class1
    {
        [STAThread]
        static void Main(string[] args)
        {
            DirectoryInfo d = new DirectoryInfo(@"C:\DirectoryIniziale");
            LeggiFileCartella(d);
        }

        static void LeggiFileCartella(DirectoryInfo pDir)
        {
            DirectoryInfo[] subd = pDir.GetDirectories();
            foreach (DirectoryInfo dd in subd)
            {
                if (dd.Attributes == FileAttributes.Directory)
                {
                    // Chiamata ricorsiva: scende nella sottocartella
                    LeggiFileCartella(dd);
                }
                else
                {
                    Console.WriteLine(dd.FullName);
                }
            }
        }
    }
}

Lo stesso pattern si applica a qualsiasi struttura gerarchica: alberi di categorie in un database, nodi XML, strutture JSON annidate, o grafi aciclici. La chiave è sempre la stessa — identificare la condizione di uscita e ridurre il problema ad ogni iterazione.

Articolo originalmente pubblicato su itvirtualcommunity.net (2004), riscritto e aggiornato nel 2012.