C Academy · Lezione

Problemi ricorsivi classici

Fattoriale e Fibonacci.

Problemi ricorsivi classici è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 2 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.

Problemi classici

Alcuni problemi si prestano naturalmente alla ricorsione. Imparare i casi classici fornisce schemi riutilizzabili.

In questa lezione tratteremo il fattoriale, i numeri di Fibonacci, la somma delle cifre, il massimo comune divisore e l'inversione dell'output.

Fattoriale

Il fattoriale di n è n moltiplicato per il fattoriale di n meno 1, con 1! uguale a 1.

Questa è la ricorsione da manuale: un caso base chiaro e una sola chiamata ricorsiva.

#include <stdio.h>

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

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

Numeri di Fibonacci

Ogni numero di Fibonacci è la somma dei due numeri che lo precedono. La definizione ricorsiva richiede due casi base: fib(0)=0 e fib(1)=1.

Questa versione effettua due chiamate a ogni passaggio.

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

Eseguire Fibonacci

Ecco il programma completo. fib(10) dovrebbe stampare 55.

Noti che questa versione ingenua ripete alcune operazioni, quindi è lenta per valori grandi di n.

#include <stdio.h>

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

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

Somma delle cifre

Per sommare le cifre di un numero, estragga l'ultima cifra con n % 10 e richiami la funzione ricorsivamente sul resto con n / 10.

Il caso base si verifica quando n raggiunge 0.

int digit_sum(int n) {
    if (n == 0) return 0;
    return (n % 10) + digit_sum(n / 10);
}

La somma delle cifre in azione

Per 1234 la somma è 1+2+3+4 = 10. Verifichiamolo con un programma completo.

#include <stdio.h>

int digit_sum(int n) {
    if (n == 0) return 0;
    return (n % 10) + digit_sum(n / 10);
}

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

Massimo comune divisore

L'algoritmo di Euclide si presta naturalmente alla ricorsione. Il MCD di a e b equivale al MCD di b e a % b.

Quando b diventa 0, a è il risultato.

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

Programma completo per il MCD

Il MCD di 48 e 18 è 6. Questo programma lo stampa.

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main(void) {
    printf("%d\n", gcd(48, 18));
    return 0;
}

Invertire un numero

La ricorsione può anche guidare l'output. Stampando l'ultima cifra dopo la chiamata ricorsiva, si inverte naturalmente l'ordine di elaborazione.

Questo helper stampa ogni cifra di un numero su una riga separata usando la ricorsione.

#include <stdio.h>

void print_digits(int n) {
    if (n == 0) return;
    print_digits(n / 10);
    printf("%d ", n % 10);
}

int main(void) {
    print_digits(729);
    printf("\n");
    return 0;
}

Funzione di potenza

Elevare una base a un esponente è anch'esso un processo ricorsivo: base^exp equivale a base moltiplicata per base^(exp-1).

Il caso base è l'esponente 0, che restituisce 1.

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

Schemi da riutilizzare

Noti la struttura comune: verificare un caso base, poi combinare il passaggio corrente con il risultato di una chiamata più piccola.

Una volta riconosciuto questo schema, molti problemi diventano brevi funzioni ricorsive.

Verifica rapida

Scelga i casi base corretti.

Riepilogo

Fattoriale, Fibonacci, somma delle cifre, MCD e potenza condividono uno schema ricorsivo: gestire il caso base, poi combinare il valore corrente con un sottoproblema più piccolo.

Questi modelli si applicano a molte altre attività.

Domande Frequenti

La lezione «Problemi ricorsivi classici» è gratuita?

Sì — il testo completo di «Problemi ricorsivi classici» è 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 «Problemi ricorsivi classici»?

Fattoriale e Fibonacci. 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 2 di 4.

Quanto tempo richiede la lezione «Problemi ricorsivi classici»?

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