C Academy · Lezione

Evitare lo stack overflow

Mantenga limitata la ricorsione.

Evitare lo stack overflow è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C Academy include 4 lezioni in totale.

Che cos'è un overflow dello stack

Lo stack delle chiamate ha una dimensione limitata. Ogni chiamata di funzione ne utilizza una parte per i parametri e le variabili locali.

Se la ricorsione diventa troppo profonda, lo stack si riempie e il programma si arresta con un overflow dello stack.

Caso base mancante

La causa più comune è un caso base che non viene mai raggiunto. La funzione continua così all'infinito e provoca un overflow dello stack.

Non esegua questo tipo di funzione; studi il motivo per cui non funziona.

int broken(int n) {
    /* no base case: never stops */
    return broken(n + 1);
}

L'argomento non si riduce

Anche in presenza di un caso base, l'argomento deve avvicinarsi a esso. Qui n aumenta, quindi non raggiunge mai 0.

Verifichi sempre che ogni chiamata si avvicini alla condizione di arresto.

int oops(int n) {
    if (n == 0) return 0;
    return oops(n + 1); /* wrong direction */
}

Una versione corretta

Correggere la direzione fa terminare la funzione. Ora n diminuisce verso il caso base 0.

#include <stdio.h>

int good(int n) {
    if (n == 0) return 0;
    return n + good(n - 1);
}

int main(void) {
    printf("%d\n", good(10));
    return 0;
}

I limiti della profondità sono reali

Anche una ricorsione corretta può provocare un overflow se è molto profonda. Chiamare una funzione a una profondità di milioni di livelli può superare la capacità dello stack, che spesso è di soli pochi megabyte.

Per profondità enormi, preferisca l'iterazione.

Convertire la ricorsione profonda in un ciclo

Se la profondità della ricorsione cresce con la dimensione dell'input, passi a un ciclo. In questo modo evita di accumulare migliaia di record di attivazione.

Il ciclo seguente somma da 1 a un n grande in modo sicuro, usando memoria costante.

#include <stdio.h>

int main(void) {
    long total = 0;
    for (int i = 1; i <= 1000000; i++)
        total += i;
    printf("%ld\n", total);
    return 0;
}

Ridurre la profondità con divide et impera

Dividere il lavoro a metà mantiene ridotta la profondità. Sommare un intervallo dimezzandolo fa crescere la profondità come il logaritmo della dimensione, invece che linearmente.

long range_sum(int lo, int hi) {
    if (lo == hi) return lo;
    int mid = (lo + hi) / 2;
    return range_sum(lo, mid) + range_sum(mid + 1, hi);
}

Attenzione ai grandi array locali

Le variabili locali grandi rendono pesante ogni record di attivazione, quindi lo stack si riempie più velocemente.

Eviti di dichiarare grandi array all'interno di una funzione ricorsiva; passi invece dei puntatori o usi l'heap.

void heavy(int n) {
    int buffer[10000]; /* big frame each call */
    if (n == 0) return;
    heavy(n - 1);
}

Usare un accumulatore

Passare un totale parziale come accumulatore mantiene ridotte le dimensioni di ogni record di attivazione e dà alla ricorsione una struttura in coda.

Alcuni compilatori possono quindi riutilizzare un singolo record di attivazione.

#include <stdio.h>

long sum_acc(int n, long acc) {
    if (n == 0) return acc;
    return sum_acc(n - 1, acc + n);
}

int main(void) {
    printf("%ld\n", sum_acc(100, 0));
    return 0;
}

Una lista di controllo per la sicurezza

Prima di affidarsi a una funzione ricorsiva, verifichi:

1. Esiste un caso base?
2. Ogni chiamata si avvicina a esso?
3. La profondità potrebbe diventare enorme con un input grande?

Se la profondità può aumentare senza controllo, usi invece un ciclo.

Testare con input piccoli

Testi sempre prima la ricorsione con input minimi, che può verificare manualmente.

Se i casi piccoli funzionano e la profondità rimane limitata, può aumentare le dimensioni con maggiore sicurezza.

Verifica rapida

Individui la correzione più sicura.

Riepilogo

L'overflow dello stack si verifica quando la ricorsione diventa troppo profonda o non termina mai. Fornisca sempre un caso base raggiungibile, riduca l'argomento a ogni chiamata, mantenga leggeri i record di attivazione e passi all'iterazione quando la profondità può crescere con la dimensione dell'input.

Domande Frequenti

La lezione «Evitare lo stack overflow» è gratuita?

Sì — il testo completo di «Evitare lo stack overflow» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C Academy, passa a CoddyKit PRO. Il corso C Academy include 4 lezioni in totale.

Cosa imparerò in «Evitare lo stack overflow»?

Mantenga limitata la ricorsione. Eserciti C Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare C Academy?

Non è richiesta alcuna esperienza precedente. C Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.

Quanto tempo richiede la lezione «Evitare lo stack overflow»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione C Academy?

Sì. Ogni lezione C Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

← Torna a C Academy