In questo tutorial imparerai a scrivere funzioni ricorsive nella programmazione C con l'aiuto di un esempio.
Una funzione che chiama se stessa è nota come funzione ricorsiva. E questa tecnica è nota come ricorsione.
Come funziona la ricorsione?
void recurse () (… recurse ();…) int main () (… recurse ();…)
La ricorsione continua fino a quando non viene soddisfatta una condizione per impedirla.
Per prevenire la ricorsione infinita, è possibile utilizzare l'istruzione if… else (o un approccio simile) dove un ramo effettua la chiamata ricorsiva e l'altro no.
Esempio: somma di numeri naturali utilizzando la ricorsione
#include int sum(int n); int main() ( int number, result; printf("Enter a positive integer: "); scanf("%d", &number); result = sum(number); printf("sum = %d", result); return 0; ) int sum(int n) ( if (n != 0) // sum() function calls itself return n + sum(n-1); else return n; )
Produzione
Immettere un numero intero positivo: 3 sum = 6
Inizialmente, sum()
viene chiamato dalla main()
funzione con numero passato come argomento.
Supponiamo che il valore di n all'interno sum()
sia inizialmente 3. Durante la successiva chiamata di funzione, 2 viene passato alla sum()
funzione. Questo processo continua finché n è uguale a 0.
Quando n è uguale a 0, la if
condizione fallisce e la else
parte viene eseguita restituendo la somma degli interi alla main()
funzione.
Vantaggi e svantaggi della ricorsione
La ricorsione rende il programma elegante. Tuttavia, se le prestazioni sono vitali, utilizzare invece i cicli poiché la ricorsione è solitamente molto più lenta.
Detto questo, la ricorsione è un concetto importante. Viene spesso utilizzato nella struttura dei dati e negli algoritmi. Ad esempio, è comune utilizzare la ricorsione in problemi come l'attraversamento di alberi.