Risposta.

Storia della questione:

La ricorsione è supportata in C sin dalla sua creazione — si integra naturalmente nella par dìgma del linguaggio, consentendo soluzioni compatte, specialmente per problemi di strutture ad albero, liste, algoritmi complessi di scomposizione.

Problema:

I principali rischi dell'uso della ricorsione sono l'eccessivo consumo dello stack, la possibilità di overflow dello stack (stack overflow) e l'impatto non evidente sulle prestazioni (rispetto a una realizzazione ciclica). In C non esiste un modo standard per controllare automaticamente la profondità dei livelli di chiamata.

Soluzione:

Prima di utilizzare la ricorsione, valutare il massimo livello possibile di nidificazione, utilizzare la ricorsione terminale, se possibile (per ottimizzazione da parte del compilatore) e aggiungere una protezione dall'overflow, ad esempio un contatore esplicito della profondità della ricorsione. Un metodo alternativo è sostituire le chiamate ricorsive con cicli per problemi semplici.

Esempio di codice:

#include <stdio.h>
#define MAX_DEPTH 1000

int factorial(int n, int depth) {
    if (depth > MAX_DEPTH) {
        printf("Errore: profondità massima della ricorsione superata!
");
        return -1;
    }
    if (n == 0) return 1;
    return n * factorial(n - 1, depth + 1);
}

int main() {
    printf("%d
", factorial(5, 0)); // 120
    return 0;
}

Caratteristiche chiave:

Non c'è garanzia di limitazione automatica della profondità della ricorsione
La ricorsione consuma stack, che può essere limitato
La ricorsione terminale può essere ottimizzata dal compilatore, ma non sempre

Domande insidiose.

Lo stack verrà liberato se all'interno di una funzione ricorsiva si esegue return prima della fine di tutte le chiamate?

Sì, lo stack viene liberato quando si esce dalla funzione attuale. Non ci saranno dati "sospesi" nello stack se non si è verificato un overflow dello stack.

È possibile dichiarare all'interno del corpo di una funzione ricorsiva variabili locali statiche e come si comporteranno?

Sì. Tali variabili saranno condivise da tutte le chiamate ricorsive, il loro valore verrà mantenuto tra le chiamate, il che porta spesso a errori se non si tiene conto di questo comportamento.

Influenza il compilatore C sulla profondità della ricorsione ed è in grado di limitarla?

Il compilatore non limita direttamente la ricorsione. La profondità della ricorsione è limitata dalla dimensione dello stack del sistema operativo o da fattori esterni.

Errori tipici e anti-pattern

Ricorsione illimitata senza controllo della profondità
Variabili locali non inizializzate o statiche nel corpo di una funzione ricorsiva
Utilizzo della ricorsione dove un ciclo sarebbe più semplice ed efficiente

Esempio dalla vita reale

È stato implementato un attraversamento ricorsivo di un albero di ricerca senza limitazione della profondità:

Pro:

Il codice è conciso, facilmente leggibile.

Contro:

Con profondità elevate dell'albero, il programma è terminato con un errore di overflow dello stack.

Nella versione migliorata è stato introdotto un contatore della profondità e una transizione a un attraversamento basato sullo stack in caso di dimensioni elevate dell'albero: