C Academy · Lezione

Come funziona la ricorsione

Casi base e stack delle chiamate.

Come funziona la ricorsione è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 1 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'è la ricorsione?

La ricorsione si verifica quando una funzione chiama se stessa per risolvere un problema. Ogni chiamata lavora su una parte più piccola del problema originale.

In C, qualsiasi funzione può chiamare se stessa, purché esista un modo per interrompere prima o poi le chiamate.

Il caso base

Ogni funzione ricorsiva ha bisogno di un caso base: una condizione in cui smette di chiamare se stessa e restituisce direttamente un risultato.

Senza un caso base, la funzione chiamerebbe se stessa all'infinito e il programma andrebbe in crash.

int countdown(int n) {
    if (n == 0) return 0; /* base case */
    return countdown(n - 1);
}

Il caso ricorsivo

Il caso ricorsivo è la parte in cui la funzione chiama se stessa con un argomento modificato.

Questo argomento deve avvicinarsi al caso base, altrimenti la ricorsione non termina mai.

int sum_to(int n) {
    if (n == 0) return 0;       /* base case */
    return n + sum_to(n - 1);   /* recursive case */
}

Un primo programma completo

Eseguiamo un programma completo che somma i numeri da 1 a 5 usando la ricorsione.

Il risultato dovrebbe essere 15.

#include <stdio.h>

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

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

Tracciare le chiamate

È utile tracciare la ricorsione a mano. Per sum_to(3):

sum_to(3) = 3 + sum_to(2)
sum_to(2) = 2 + sum_to(1)
sum_to(1) = 1 + sum_to(0)
sum_to(0) = 0

Le chiamate restituiscono quindi i risultati risalendo: prima 1, poi 3 e infine 6.

Lo stack delle chiamate

Ogni chiamata di funzione riceve il proprio spazio nello stack delle chiamate, che contiene i parametri e le variabili locali.

Durante la discesa, i frame si accumulano. Quando una chiamata restituisce un risultato, il suo frame viene rimosso e il controllo torna al chiamante.

Discesa e risalita

La ricorsione ha due fasi. La discesa si verifica quando le chiamate procedono verso il caso base.

La risalita si verifica quando il caso base restituisce un risultato e ogni chiamata completa il proprio lavoro usando il valore restituito.

#include <stdio.h>

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

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

I valori restituiti risalgono

Il valore restituito da una chiamata più profonda viene usato dalla chiamata che l'ha effettuata.

Per questo l'ordine è importante: la chiamata più profonda termina per prima, poi i risultati si combinano durante la risalita nello stack.

int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

Stampare durante la ricorsione

Può stampare prima o dopo la chiamata ricorsiva. Stampare prima mostra i numeri durante la discesa; stampare dopo li mostra durante la risalita.

#include <stdio.h>

void down(int n) {
    if (n == 0) return;
    printf("%d ", n);
    down(n - 1);
}

int main(void) {
    down(5);
    printf("\n");
    return 0;
}

Stampare durante la risalita

Sposti printf dopo la chiamata ricorsiva e l'ordine si invertirà. La chiamata più profonda stampa per prima.

In questo modo vengono stampati 1 2 3 4 5 invece di 5 4 3 2 1.

#include <stdio.h>

void up(int n) {
    if (n == 0) return;
    up(n - 1);
    printf("%d ", n);
}

int main(void) {
    up(5);
    printf("\n");
    return 0;
}

Due regole da ricordare

Una funzione ricorsiva corretta segue due regole:

1. Ha almeno un caso base che restituisce un risultato senza ricorrere.
2. Ogni chiamata ricorsiva avvicina l'argomento a un caso base.

Se viola una delle due regole, il programma entra in un ciclo infinito.

Verifica rapida

Verifichi la sua comprensione dei concetti di base della ricorsione.

Riepilogo

La ricorsione risolve un problema chiamando se stessa su un input più piccolo. È sempre necessario un caso base che la interrompa e un caso ricorsivo che vi si avvicini.

Ogni chiamata usa un frame dello stack; i risultati risalgono durante la fase di ritorno.

Domande Frequenti

La lezione «Come funziona la ricorsione» è gratuita?

Sì — il testo completo di «Come funziona la ricorsione» è 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 «Come funziona la ricorsione»?

Casi base e stack delle chiamate. 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 1 di 4.

Quanto tempo richiede la lezione «Come funziona la ricorsione»?

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