Introduzione alla funzione ricorsiva in C
Il processo di ripetizione degli articoli in un modo simile a quello precedente era noto come ricorsione. Si dice che una funzione sia ricorsiva se è chiamata in se stessa. La ricorsione è supportata dal linguaggio di programmazione C. Di seguito sono riportate due condizioni fondamentali per implementare la ricorsione in C:
- Una condizione di uscita: questa condizione aiuta la funzione a identificare quando uscire da quella funzione. Nel caso in cui non specifichiamo la condizione di uscita, il codice entrerà in un ciclo infinito.
- Modifica del contatore: modifica del contatore in ogni chiamata a quella funzione.
In questo modo, possiamo implementare una funzione ricorsiva nel linguaggio di programmazione C. Queste funzioni sono utili per risolvere problemi matematici in denaro che richiedono che un processo simile sia chiamato più volte. Esempi di tali problemi sono il calcolo del fattoriale di una serie di generazioni di Fibonacci.
Sintassi:
int fun(a1)
(
If(base_condition) return val;
fun(a2);
)
Come funziona la funzione ricorsiva in C?
Le funzioni ricorsive sono il modo di implementare l'equazione nel linguaggio di programmazione C. Una funzione ricorsiva viene chiamata con un argomento passato in essa diciamo n, la memoria nello stack viene allocata alle variabili locali e alle funzioni. Tutte le operazioni presenti nella funzione vengono eseguite utilizzando quella memoria. La condizione per l'uscita viene verificata se soddisfa. Quando il compilatore rileva una chiamata a un'altra funzione, alloca immediatamente nuova memoria nella parte superiore dello stack in cui viene creata una copia diversa delle stesse variabili locali e la funzione. Immettere lo stesso processo continua.
Quando la condizione di base restituisce true, il valore particolare passa alla funzione chiamante. La memoria allocata a quella funzione viene cancellata. allo stesso modo, il nuovo valore viene calcolato nella funzione di chiamata e l'IT ritorna alla funzione di super chiamata. In questo modo vengono effettuate chiamate ricorsive alla funzione di eliminazione raggiunge la prima funzione e l'intera memoria dello stack viene cancellata e viene restituito l'output. La condizione di base incassa o di uscita non è specificata nella funzione, quindi le chiamate ricorsive alla funzione possono portare a un ciclo infinito.
Esempio di funzione ricorsiva
Ora vedremo gli esempi di Funzione ricorsiva in C
Codice:
#include
int fun(int n)
(
if(n==1) return 1 ; //exit or base condition which gives an idea when to exit this loop.
return n*fun(n-1); //function is called with n-1 as it's argument .
//The value returned is multiplied with the argument passed in calling function.
)
int main()(
int test=4;
int result =0;
result =fun(test);
printf("%d", result);//prints the output result.
)
Produzione:
Spiegazione del codice precedente
L'esempio sopra riportato è di trovare il fattoriale di un numero. Quando la funzione principale chiama fun (4), prima viene verificata la condizione di uscita (4 == 1), quindi viene chiamato 4 * fun (3). Ancora una volta viene verificata la condizione di base (3 == 1). Allo stesso modo, restituirà 3 * fun (2) viene chiamato e continua fino a 2 * fun (1) viene chiamato e dove soddisfa la condizione di base e restituisce 1 quindi la funzione di chiamata restituisce 2 * 1 quindi, 3 * 2 * 1 e dalla prima chiamata viene restituito 4 * 3 * 2 * 1. Pertanto, la funzione principale memorizza 24 e lo stampa sull'output.
Allocazione di memoria della funzione ricorsiva
Ogni chiamata a una funzione in linguaggio c comporta l'allocazione della memoria nella parte superiore di uno stack. Quando viene chiamata una funzione ricorsiva, la memoria viene allocata nella parte superiore della memoria che è stata allocata alla funzione chiamante con tutte le diverse copie delle variabili locali che vengono create per ogni chiamata alla funzione.
Qual è la condizione di base raggiunta, la memoria allocata alla funzione viene distrutta e il puntatore ritorna alla funzione chiamante? questo processo viene ripetuto quindi la prima funzione di chiamata e, infine, la memoria dello stack si svuota.
Nell'esempio sopra riportato per calcolare il fattoriale di un numero di seguito è lo scenario per l'allocazione della memoria.
Passo 1
Passo 2
Step - 3
Step - 4
Step - 5
Step - 6
Step - 7
Passaggio 8
Passaggio - 9
Tipi di ricorsione
Esistono due tipi di ricorsione nella programmazione C che sono indicati di seguito:
1. Ricorsione di coda e non di coda
Il tipo di ricorsione sopra indicato è spiegato di seguito:
- Ricorsione della coda
È un tipo di chiamata di ricorsione della funzione ricorsiva nella funzione che è l'ultima azione da eseguire nella definizione della funzione. Significa che la chiamata ricorsiva si verifica dopo l'implementazione di qualsiasi altra logica nella funzione.
L'uso di una ricorsione di coda nel nostro programma in hansis le prestazioni del programma e riduce anche l'utilizzo della memoria di tale funzione. È così perché come altra logica nella funzione è stata implementata nella memoria allocata alla funzione chiamante può essere rimossa dallo stack e riutilizzata.
Codice:
int fun1(n)(
printf(“the result is “);
return fun1(n-1);
)
void main()
(
fun1(4);
)
- Ricorsione senza coda
Questo tipo di collage ricorsivo ricorsivo realizzato nel mezzo della definizione della funzione. La ricorsione dei pantaloni da uomo è completata e i valori restituiti alla funzione di chiamata ci sono più passaggi da eseguire, quindi la memoria non può essere cancellata.
Codice:
int fun1(n)(
printf(“the result is “);
return n* fun1(n-1);
)
void main()(
fun1(4);
)
2. Ricorsione diretta e indiretta
Il tipo di ricorsione sopra indicato è spiegato di seguito:
- Ricorsione indiretta
Si dice che la ricorsione indiretta si verifichi quando una particolare funzione viene chiamata in modo ricorsivo come mezzo di un'altra funzione.
Codice:
int fun1()(
fun2();
)
int fun2()(
fun1(); // calling the procedure recursively using another function.
)
void main()(
fun1();
)
- Ricorsione diretta
Si dice che la ricorsione diretta si verifica quando la chiamata ricorsiva alla funzione viene effettuata all'interno della propria definizione. "
Codice:
int fun1()(
fun1();
)
void main()(
fun1();
)
Conclusione
Si può facilmente concludere che le funzioni ricorsive sono al massimo importanti per risolvere problemi matematici che richiedono un metodo simile per implementare ripetutamente tutta la logica fino a quando non viene soddisfatta una condizione di uscita. Molti problemi come torri di Hanoi, traversate di alberi, calcolo della profondità dei grafici.
È importante menzionare una condizione di base per la funzione ricorsiva. I requisiti di memoria e tempo sono maggiori per il programma ricorsivo rispetto a quelli iterativi, quindi devono essere usati con attenzione.
Articoli consigliati
Questa è una guida all'esempio della funzione ricorsiva in C. Qui discutiamo di funzionamento, tipi, allocazione della memoria ed esempi di funzione ricorsiva in C. Puoi anche leggere i seguenti articoli per saperne di più-
- Matrici in programmazione C.
- Programma Palindrome in C.
- Pattern nella programmazione C.
- C vs C ++
- Palindrome in JavaScript
- Guida alla serie Fibonacci in JavaScript