Esercitazione sulla programmazione C Linux Parte 18:Funzioni ricorsive

Indipendentemente dal linguaggio di programmazione che usi, man mano che inizi a programmare sempre di più, impari concetti che rendono il tuo codice nitido e facile da leggere/comprendere. Ci sono molti di questi concetti anche nella C. Uno di questi sono le "funzioni ricorsive", di cui parleremo qui in questo articolo.

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

Di seguito è riportato un esempio di ricorsione diretta:

int func (int a)
{
    //statements

    func(a-1);

    // statements

    return 0;
}

Ed ecco un esempio di ricorsione indiretta:

int func (int a)
{
    //statements

    func_new(a);

    // statements

    return 0;
}

int func_new(int b)
{
    //statements

    func(b-1);

    //statementsur

    return 0;
}

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

Sono sicuro che tutti voi avrete sentito parlare del concetto di fattoriale. Per chi non lo sapesse, fattoriale è il risultato che si ottiene moltiplicando un intero con tutti gli interi positivi minori di esso. Ad esempio, il fattoriale di 5 è 5x4x3x2x1, che è uguale a 120.

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

#include <stdio.h>

int main()
{
 int a = 0, i = 0, fact = 1;
 printf("Enter a number: ");

 scanf("%d", &a);
 
 for(i=1; i<=a; i++)
 {
 fact = fact * i;
 
 }
 printf("Factorial of the number is: %d ", fact);
 return 0;
}

Nota che questo codice serve solo per farti sapere come il fattoriale di un numero può essere calcolato tramite un programma C. Il programma non si prende cura di casi d'angolo che possono influire sull'accuratezza del risultato che produce.

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

#include <stdio.h>

int factorial (int b)
{
 if(!b)
 return 1;
 
 return (b * factorial(b-1));
}

int main()
{
 int a = 0, fact = 1;
 printf("Enter a number: ");

 scanf("%d", &a);
 
 fact = factorial(a);
 
 printf("Factorial of the number is: %d ", fact);
 return 0;
}

Quindi puoi vedere, la funzione "fattoriale" che calcola effettivamente il fattoriale è molto compatta. E se presti molta 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 "fattoriale" quando viene chiamato per la prima volta dall'interno della funzione "principale". All'interno della funzione 'fattoriale', 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'.

Quindi, l'istruzione return contiene un'espressione che moltiplica 5 con il valore restituito di 'factorial(4)'. Quindi ora, la funzione 'fattoriale' viene eseguita ancora una volta e raggiungiamo la seguente espressione:return (4 * fattoriale(3)). E poi di nuovo questi passaggi si ripetono.

Quindi, se guardi in modo ampio, ecco come vengono impilate queste chiamate di funzione:

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

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

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

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

Ecco come funzionano le funzioni ricorsive. Sebbene non ci siano dubbi sui vantaggi della funzione ricorsiva che abbiamo elencato finora, ci sono anche alcuni svantaggi.

Ad esempio, nel nostro esempio sopra, fino al completamento della chiamata 'factorial(0)', tutte le precedenti chiamate 'factorial' erano in attesa del completamento dell'elaborazione della funzione. 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 si utilizza la ricorsione. Inoltre, non c'è alcuna garanzia che il tuo codice sia più veloce nell'esecuzione. Il vero vantaggio di una funzione ricorsiva è quando si tratta di strutture dati, di cui parleremo più avanti come parte di questa serie di tutorial C in corso.

Conclusione

Per concludere, anche se potresti non usare frequentemente la funzione ricorsiva nelle tue attività di codifica quotidiane, è un concetto importante di cui devi essere consapevole. Prova l'esempio che abbiamo citato qui e modificalo per comprendere ancora meglio il concetto di funzioni ricorsive.