Tutorial di programmazione C su Linux Parte 18: Funzioni ricorsive

Indipendentemente dal linguaggio di programmazione che utilizzi, man mano che inizi a scrivere sempre di più, impari concetti che rendono il tuo codice conciso e facile da leggere/comprendere. Ci sono diversi di questi concetti anche in C. Uno di essi è ‘funzioni ricorsive’, di cui discuteremo qui in questo articolo.

Una funzione ricorsiva è una funzione che chiama se stessa. La chiamata può essere effettuata direttamente all’interno del corpo della funzione, o indirettamente da un’altra funzione che viene chiamata dalla funzione in questione.

Di seguito è riportato un esempio di ricorsione diretta:

int func (int a)  
{  
    //istruzioni  
  
    func(a-1);  
  
    // istruzioni  
  
    return 0;  
}

Ecco un esempio di ricorsione indiretta:

int func (int a)  
{  
    //istruzioni  
  
    func_new(a);  
  
    // istruzioni  
  
    return 0;  
}  
  
int func_new(int b)  
{  
    //istruzioni  
  
    func(b-1);  
  
    //istruzioni  
  
    return 0;  
}

Come già accennato all’inizio, la ricorsione ti aiuta a ottenere un codice compatto, che non è solo facile da scrivere ma anche facile da comprendere e rivedere. Prendiamo un esempio per rendere questo vantaggio più chiaro.

Sono sicuro che tutti voi avrete sentito parlare del concetto di fattoriale. Per coloro che non ne sono a conoscenza, il fattoriale è il risultato che ottieni quando moltiplichi un intero con tutti gli interi positivi inferiori ad esso. Ad esempio, il fattoriale di 5 è 5x4x3x2x1, che è uguale a 120.

Ecco un semplice codice per trovare il fattoriale di un numero:

#include   
  
int main()  
{  
 int a = 0, i = 0, fact = 1;  
 printf("Inserisci un numero: ");  
  
 scanf("%d", &a);  
   
 for(i=1; i<=a; i++)  
 {  
 fact = fact * i;  
   
 }  
 printf("Il fattoriale del numero è: %d ", fact);  
 return 0;  
}

Nota che questo codice serve solo a farti sapere come può essere calcolato il fattoriale di un numero tramite un programma C. Il programma non tiene conto dei casi limite che possono influenzare l’accuratezza del risultato che produce.

Quindi questo è uno dei tanti modi in cui puoi calcolare il fattoriale di un numero senza utilizzare una funzione ricorsiva. Ora vediamo un pezzo di codice che utilizza la ricorsione per calcolare un fattoriale.

#include   
  
int factorial (int b)  
{  
 if(!b)  
 return 1;  
   
 return (b * factorial(b-1));  
}  
  
int main()  
{  
 int a = 0, fact = 1;  
 printf("Inserisci un numero: ");  
  
 scanf("%d", &a);  
   
 fact = factorial(a);  
   
 printf("Il fattoriale del numero è: %d ", fact);  
 return 0;  
}

Quindi puoi vedere, la funzione ‘factorial’ che calcola effettivamente il fattoriale è molto compatta. E se presti attenzione, è anche molto facile da capire.

Per coloro che non sanno cosa sta succedendo, il valore che l’utente ha inserito, diciamo 5, viene passato alla funzione ‘factorial’ quando viene chiamata per la prima volta dalla funzione ‘main’. All’interno della funzione ‘factorial’, c’è un controllo per vedere se il valore di input è zero, il che non è vero quando la funzione viene chiamata per la prima volta con il valore di input ‘5’.

Poi, l’istruzione di ritorno contiene un’espressione che moltiplica 5 per il valore di ritorno di ‘factorial(4)’. Quindi ora, la funzione ‘factorial’ viene eseguita di nuovo, e arriviamo alla seguente espressione: return (4 * factorial(3)). E poi di nuovo questi passaggi si ripetono.

Quindi se guardi in modo ampio, ecco come queste chiamate di funzione si accumulano:

• 5 * factorial(4)
• 4 * factorial(3)
• 3 * factorial(2)
• 2 * factorial (1)
• 1 * factorial (0)

Ora quando factorial(0) viene eseguito, la condizione ‘if’ nella funzione ‘factorial’ diventa vera, e il valore ‘1’ viene restituito. Quindi ora, ecco come si completano le chiamate elencate sopra (confronta l’ultima voce nell’elenco precedente con la prima voce in questo elenco, e così via):

• 1 * 1
• 2 (11)
• 3 (2(1*1))
• 4 (3(2(11)))
• 5 (4 (3(2(1*1))))

Che è effettivamente 5 4 3 2 1, che a sua volta è 120, il fattoriale di 5.

Quindi questo è come funzionano le funzioni ricorsive. Anche se non ci sono dubbi sui vantaggi delle funzioni ricorsive che abbiamo elencato finora, ci sono anche alcuni svantaggi.

Ad esempio, nel nostro esempio sopra, fino a quando la chiamata ‘factorial(0)’ non è completata, tutte le chiamate ‘factorial’ precedenti stavano aspettando che l’elaborazione della funzione fosse completata. Per non parlare del fatto che le variabili automatiche o locali occupano memoria per ogni chiamata ricorsiva effettuata.

Quindi non c’è effettivamente alcun risparmio di spazio di archiviazione quando utilizzi la ricorsione. Inoltre, non c’è nemmeno alcuna garanzia che il tuo codice sarà più veloce nell’esecuzione. Il vero vantaggio di una funzione ricorsiva è quando si tratta di strutture dati, di cui discuteremo più avanti come parte di questa serie di tutorial C in corso.

Conclusione

Per concludere, anche se potresti non utilizzare frequentemente le funzioni ricorsive nei tuoi compiti di codifica quotidiani, è un concetto importante di cui devi essere a conoscenza. Prova l’esempio che abbiamo menzionato qui e modificalo per comprendere ancora meglio il concetto di funzioni ricorsive.