Ricorsione in C

La ricorsione è una tecnica in cui una funzione chiama sé stessa per risolvere un problema.

In questa lezione imparerà:

• Che cos'è la ricorsione e come funziona.
• Come implementare funzioni ricorsive.
• La differenza tra ricorsione e iterazione.

Che cos'è la ricorsione?

Si parla di ricorsione quando una funzione chiama sé stessa per risolvere una parte più piccola di un problema.

Sintassi di esempio:

void function() { function(); // Recursive call }

Ogni funzione ricorsiva deve avere un caso base per impedire una ricorsione infinita.

Esempio: ricorsione

Questo programma illustra la ricorsione stampando i numeri da 5 a 1.

#include <stdio.h>

void countDown(int n) {
    if (n <= 0) return; // Base case
    printf("%d\n", n);
    countDown(n - 1); // Recursive call
}

int main() {
    countDown(5);
    return 0;
}

Caso base nella ricorsione

Una funzione ricorsiva deve includere un caso base per interrompere la ricorsione.

Esempio:

if (n == 0) return;

Senza un caso base, la funzione chiamerà sé stessa all'infinito, causando un overflow dello stack.

Esempio: fattoriale con la ricorsione

Questo programma calcola il fattoriale di un numero utilizzando la ricorsione.

#include <stdio.h>

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

int main() {
    printf("Factorial of 5: %d\n", factorial(5));
    return 0;
}

Ricorsione e iterazione

La ricorsione e l'iterazione (tramite cicli) possono produrre gli stessi risultati, ma funzionano in modo diverso.

Differenze:

• La ricorsione utilizza chiamate di funzione e richiede più memoria.
• L'iterazione utilizza cicli ed è generalmente più efficiente.
• La ricorsione rende più semplice il codice per problemi come l'attraversamento di alberi.

Esempio: sequenza di Fibonacci (ricorsiva)

Questo programma calcola la sequenza di Fibonacci usando la ricorsione.

#include <stdio.h>

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

int main() {
    printf("Fibonacci(5): %d\n", fibonacci(5));
    return 0;
}

Quando usare la ricorsione?

La ricorsione è utile per i problemi che richiedono:

• Attraversamento di alberi.
• Backtracking (ad es., per risolvere labirinti).
• Problemi matematici come il calcolo del fattoriale e della sequenza di Fibonacci.

Riepilogo

In questa lezione ha imparato:

• Che cos'è la ricorsione e come funziona.
• L'importanza del caso base.
• La differenza tra ricorsione e iterazione.

Successivamente, esplorerà gli array e le stringhe in C!