Ricorsione in C++

La ricorsione è una tecnica fondamentale nella programmazione che consiste nel risolvere un problema dividendo il problema stesso in sottoproblemi più semplici dello stesso tipo. In C++, la ricorsione è utilizzata in molteplici scenari, come la risoluzione di algoritmi complessi, la gestione di strutture dati come alberi, e la realizzazione di soluzioni eleganti e concise. In questo articolo, esploreremo il concetto di ricorsione, come funziona in C++, e i casi d’uso comuni con esempi pratici.

Cos’è la Ricorsione?

La ricorsione avviene quando una funzione chiama sé stessa direttamente o indirettamente come parte della sua esecuzione. Ogni chiamata ricorsiva lavora su una versione ridotta o semplificata del problema originale, avvicinandosi passo dopo passo a una soluzione.

Elementi Fondamentali della Ricorsione

Per una funzione ricorsiva ben strutturata, è essenziale che contenga due elementi principali:

1. Caso Base: La condizione che ferma la ricorsione, impedendo che la funzione continui a chiamare sé stessa all’infinito.
2. Chiamata Ricorsiva: La parte della funzione che chiama sé stessa con un input modificato, riducendo progressivamente il problema.

Esempio Semplice: Fattoriale

Uno degli esempi più comuni per introdurre la ricorsione è il calcolo del fattoriale di un numero n, definito come n! = n * (n-1)! con 0! = 1 come caso base.

#include <iostream>

int fattoriale(int n) {
    if (n <= 1)  // Caso Base
        return 1;
    else
        return n * fattoriale(n - 1);  // Chiamata Ricorsiva
}

int main() {
    int numero = 5;
    std::cout << "Fattoriale di " << numero << " è: " << fattoriale(numero) << std::endl;  // Output: 120
    return 0;
}

In questo esempio, la funzione fattoriale chiama sé stessa fino a raggiungere il caso base (quando n è 1 o meno), dopodiché risolve le chiamate ricorsive accumulando il risultato.

Casi d’Uso Comuni della Ricorsione

1. Ricerca Binaria

La ricerca binaria è un algoritmo efficiente per trovare un elemento in un array ordinato, dividendo ripetutamente l’array a metà fino a trovare l’elemento o esaurire le possibilità.

#include <iostream>

int ricerca_binaria(int arr[], int sinistra, int destra, int chiave) {
    if (destra >= sinistra) {
        int medio = sinistra + (destra - sinistra) / 2;

        // Caso base: la chiave è al centro
        if (arr[medio] == chiave)
            return medio;

        // Chiamata ricorsiva: cerca nella metà sinistra
        if (arr[medio] > chiave)
            return ricerca_binaria(arr, sinistra, medio - 1, chiave);

        // Chiamata ricorsiva: cerca nella metà destra
        return ricerca_binaria(arr, medio + 1, destra, chiave);
    }

    // La chiave non è presente nell'array
    return -1;
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int chiave = 10;
    int risultato = ricerca_binaria(arr, 0, n - 1, chiave);
    (risultato == -1)
        ? std::cout << "Elemento non presente nell'array" << std::endl
        : std::cout << "Elemento trovato all'indice " << risultato << std::endl;
    return 0;
}

2. Fibonacci

La sequenza di Fibonacci è un classico esempio di problema risolvibile tramite ricorsione, dove ogni numero della sequenza è la somma dei due precedenti.

#include <iostream>

int fibonacci(int n) {
    if (n <= 1)  // Caso Base
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);  // Chiamata Ricorsiva
}

int main() {
    int n = 9;
    std::cout << "Il " << n << "° numero di Fibonacci è: " << fibonacci(n) << std::endl;  // Output: 34
    return 0;
}

3. Traversal di Alberi

La ricorsione è ampiamente utilizzata per attraversare strutture dati gerarchiche come gli alberi.

Traversal In-Order di un Albero Binario

#include <iostream>

struct Nodo {
    int dato;
    Nodo* sinistra;
    Nodo* destra;
    Nodo(int val) : dato(val), sinistra(nullptr), destra(nullptr) {}
};

void inOrder(Nodo* radice) {
    if (radice != nullptr) {
        inOrder(radice->sinistra);
        std::cout << radice->dato << " ";
        inOrder(radice->destra);
    }
}

int main() {
    Nodo* radice = new Nodo(1);
    radice->sinistra = new Nodo(2);
    radice->destra = new Nodo(3);
    radice->sinistra->sinistra = new Nodo(4);
    radice->sinistra->destra = new Nodo(5);

    std::cout << "Traversal in-order: ";
    inOrder(radice);  // Output: 4 2 5 1 3
    std::cout << std::endl;

    return 0;
}

Vantaggi e Svantaggi della Ricorsione

Vantaggi

• Semplicità e Eleganza: La ricorsione spesso fornisce una soluzione più semplice e intuitiva a problemi complessi.
• Facilità di Implementazione: Molte strutture dati e algoritmi sono naturalmente ricorsivi, rendendo la ricorsione una scelta naturale.

Svantaggi

• Efficienza: Le funzioni ricorsive possono essere meno efficienti a causa dell’overhead delle chiamate di funzione ripetute e del consumo di memoria per lo stack.
• Rischio di Stack Overflow: Se la ricorsione è troppo profonda, può causare un’eccezione di stack overflow a causa dell’esaurimento dello stack.

Ottimizzazioni della Ricorsione

Ricorsione di Coda

La ricorsione di coda è una forma di ricorsione in cui la chiamata ricorsiva è l’ultima operazione della funzione. Alcuni compilatori ottimizzano automaticamente la ricorsione di coda, riducendo l’overhead.

int fattoriale_tail(int n, int accumulatore = 1) {
    if (n <= 1)
        return accumulatore;
    return fattoriale_tail(n - 1, n * accumulatore);
}

Memoizzazione

La memoizzazione è una tecnica che memorizza i risultati delle chiamate ricorsive per evitare ricalcoli ridondanti, migliorando l’efficienza.

#include <iostream>
#include <vector>

int fibonacci_memo(int n, std::vector<int>& memo) {
    if (n <= 1)
        return n;
    if (memo[n] == -1)
        memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo);
    return memo[n];
}

int main() {
    int n = 9;
    std::vector<int> memo(n + 1, -1);
    std::cout << "Il " << n << "° numero di Fibonacci (memoization) è: " << fibonacci_memo(n, memo) << std::endl;
    return 0;
}

Best Practices

• Evitare Ricorsione Profonda: Usa iterazioni invece della ricorsione quando il numero di chiamate ricorsive potrebbe essere molto elevato.
• Verifica del Caso Base: Assicurati sempre che ci sia un caso base chiaro e che verrà sicuramente raggiunto.
• Considera l’Ottimizzazione: Quando possibile, utilizza la ricorsione di coda e la memoizzazione per migliorare l’efficienza.

Conclusione

La ricorsione è una tecnica potente e versatile in C++ che consente di risolvere problemi complessi in modo elegante e intuitivo. Tuttavia, è importante essere consapevoli dei suoi limiti e delle best practices per evitare inefficienze e potenziali problemi come lo stack overflow. Con una comprensione solida della ricorsione e

delle sue ottimizzazioni, puoi sfruttare al massimo questa tecnica per scrivere codice C++ pulito, efficiente e robusto.