Menu

Ricorsione in C ++

recursion c

Prova Il Nostro Strumento Per Eliminare I Problemi

Esplora tutto sulla ricorsione in C ++ con esempi classici.

Nel nostro tutorial precedente, abbiamo imparato di più sulle funzioni in C ++.

Oltre a utilizzare le funzioni per scomporre il codice in sottounità e renderlo più semplice e leggibile, le funzioni sono utili in varie altre applicazioni, inclusa la risoluzione di problemi in tempo reale, il calcolo matematico e statistico.

Man mano che sviluppiamo applicazioni più complesse in C ++, incontriamo molti requisiti, quindi dobbiamo utilizzare diversi concetti speciali di C ++. La ricorsione è uno di questi concetti.

=> Visita qui per l'elenco completo dei tutorial C ++.

RICURSIONE IN C ++

In questo tutorial, impareremo di più sulla ricorsione, dove e perché viene utilizzata insieme ad alcuni classici esempi C ++ che implementano la ricorsione.

Cosa imparerai:

Cos'è la ricorsione?

La ricorsione è un processo in cui una funzione chiama se stessa. La funzione che implementa la ricorsione o chiama se stessa è chiamata funzione ricorsiva. Nella ricorsione, la funzione ricorsiva chiama se stessa più e più volte e continua finché non viene soddisfatta una condizione finale.

L'immagine sotto mostra come funziona la ricorsione:

Lavorare sulla ricorsione

Come vediamo nel diagramma sopra, la funzione principale chiama una funzione, funct (). La funzione funct () a sua volta chiama se stessa all'interno della sua definizione. Ecco come funziona la ricorsione. Questo processo della funzione che chiama se stessa continuerà fino a quando non forniremo una condizione di terminazione che lo farà terminare.

Di solito, durante l'implementazione della ricorsione forniamo un ramo di codice in modo tale da fornire una condizione che attiverà la ricorsione e un'altra per eseguire la normale esecuzione.

Condizione di base della ricorsione

Quando viene eseguita la ricorsione, viene fornita la soluzione al caso base o al caso finale e le soluzioni a problemi più grandi vengono costruite in base alle soluzioni a problemi più piccoli.

Consideriamo un classico esempio di ricorsione, la notazione fattoriale.

Sappiamo che matematicamente il fattoriale di un numero n è:

n! = nxn-1x… .x0!
dato che 0! = 1;

Quindi fattoriale per n = 3 sarà 3! = 3 × 2!

3! = 3x2x1!
3! = 3x2x2x0!
3! = 3x2x1x1 = 6

Quindi a livello di codice possiamo esprimere questo calcolo come segue:

int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); }

Pertanto, come mostrato sopra, abbiamo espresso il calcolo precedente di un fattoriale in una chiamata di funzione ricorsiva. Vediamo che se il numero n è minore o uguale a 1, restituiamo 1 invece di una chiamata ricorsiva. Questa è chiamata condizione / caso di base per il fattoriale che consente di fermare la ricorsione.

Quindi, la condizione di base fondamentalmente decide quante volte una funzione ricorsiva deve chiamare se stessa. Ciò significa che possiamo calcolare molto bene il fattoriale di un numero maggiore esprimendolo in termini di numeri più piccoli fino a raggiungere la classe base.

Di seguito è riportato un esempio perfetto per calcolare il fattoriale di un numero:

#include #include using namespace std; int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); } int main() { int num,result; cout<>num; result = factorial(num); cout<

Produzione:

Immettere il numero di cui calcolare il fattoriale: 10
10! = 3628800

Nell'esempio sopra, implementiamo la ricorsione. Prendiamo il numero il cui fattoriale deve essere trovato dallo standard input e poi lo passiamo alla funzione fattoriale.

Nella funzione fattoriale, abbiamo dato la condizione di base come (n<=1). So, when the base case is reached, the function returns. Using this base case, we can calculate factorial of any number greater than 1.

Allocazione della memoria per la chiamata ricorsiva

Sappiamo che quando viene effettuata una chiamata di funzione, lo stato della funzione chiamante viene memorizzato nello stack e quando una chiamata di funzione viene completata, tale stato viene ripristinato in modo che il programma possa continuare l'esecuzione.

Quando viene effettuata una chiamata di funzione ricorsiva, lo stato o la memoria per la funzione chiamata viene allocata sopra lo stato della funzione chiamante e viene creata una copia diversa delle variabili locali per ogni chiamata di funzione ricorsiva.

Quando viene raggiunta la condizione di base, la funzione ritorna alla funzione chiamante e la memoria viene de-allocata e il processo continua.

Overflow dello stack in ricorsione

Quando la ricorsione continua per un periodo di tempo illimitato, può provocare un overflow dello stack.

Quando può continuare la ricorsione in questo modo? Una situazione è quando non specifichiamo la condizione di base. Un'altra situazione è quando la condizione di base non viene raggiunta durante l'esecuzione di un programma.

Per esempio,modifichiamo il suddetto programma fattoriale e cambiamo la sua condizione di base.

int factorial(int n){ if(n ==1000) return 1; else return n*factorial(n-1); }

Nel codice precedente, abbiamo modificato la condizione di base in (n == 1000). Ora, se diamo il numero n = 10, possiamo concludere che la condizione di base non raggiungerà mai. In questo modo, a un certo punto, la memoria nello stack verrà esaurita con conseguente overflow dello stack.

Quindi, durante la progettazione di programmi ricorsivi, dobbiamo stare attenti alla condizione di base che forniamo.

Ricorsione diretta vs indiretta

Finora nella ricorsione, abbiamo visto la funzione che chiama se stessa. Questa è la ricorsione diretta.

C'è un altro tipo di ricorsione, cioè la ricorsione indiretta. In questo, una funzione chiama un'altra funzione e quindi questa funzione chiama la funzione chiamante. Se f1 e f2 sono due funzioni. Quindi f1 chiama f2 e f2, a sua volta, chiama f1. Questa è una ricorsione indiretta.

qual è il miglior software di ottimizzazione per PC

L E rivediamo il nostro programma fattoriale per dimostrare la ricorsione diretta.

#include #include using namespace std; int factorial_b(int); int factorial_a(int n){ if(n <=1) return 1; else return n*factorial_b(n-1); } int factorial_b(int n){ if(n <=1) return 1; else return n*factorial_a(n-1); } int main() { int num, result; cout<>num; result = factorial_a(num); cout<

Produzione:

Immettere il numero di cui calcolare il fattoriale: 5
5! = 120

Nell'esempio sopra, abbiamo mostrato la ricorsione indiretta. La funzione principale chiama factorial_a. Factorial_a chiama factorial_b. A sua volta factorial_b chiama factorial_a. Vediamo che l'output del programma non è influenzato.

Ricorsione a coda e senza coda

Una funzione ricorsiva con coda è una funzione ricorsiva in cui l'ultima chiamata viene eseguita nella funzione.

Per esempio, considera la seguente funzione.

void display(int n){ if(n<=1) return; cout<<” ”<

Nell'esempio sopra, la visualizzazione è una funzione ricorsiva con coda tale che è l'ultima chiamata di funzione.

Le funzioni con coda sono considerate migliori delle funzioni ricorsive senza coda poiché possono essere ottimizzate dal compilatore. Il motivo è che poiché la chiamata ricorsiva con coda è l'ultima istruzione nella funzione, non c'è codice da eseguire dopo questa chiamata.

Di conseguenza, non è necessario salvare lo stack frame corrente per la funzione.

Pro / contro della ricorsione sulla programmazione iterativa

I programmi ricorsivi forniscono codice compatto e pulito. Un programma ricorsivo è un modo semplice di scrivere programmi. Ci sono alcuni problemi inerenti come fattoriale, sequenza di Fibonacci, torri di Hanoi, attraversamenti di alberi, ecc. Che richiedono la ricorsione per essere risolti.

In altre parole, vengono risolti in modo efficiente con la ricorsione. Possono anche essere risolti con la programmazione iterativa utilizzando stack o altre strutture di dati, ma ci sono possibilità che diventino più complessi da implementare.

I poteri di risoluzione dei problemi della programmazione ricorsiva e iterativa sono gli stessi. Tuttavia, i programmi ricorsivi occupano più spazio di memoria poiché tutte le chiamate di funzione devono essere memorizzate nello stack fino a quando il caso base non viene trovato.

Le funzioni ricorsive hanno anche un sovraccarico di tempo a causa di troppe chiamate di funzione e valori restituiti.

Esempi di ricorsione

Successivamente, implementeremo alcuni degli esempi di programmazione ricorsiva.

Serie di Fibonacci

La serie di Fibonacci è la sequenza data come

0 1 1 2 3 5 8 13 ……

Come mostrato sopra, i primi due numeri della serie di Fibonacci sono 0 e 1. Il numero successivo nella sequenza è la somma dei due numeri precedenti.

Implementiamo questa serie usando la ricorsione.

#include using namespace std; void fibSeries(int n){ static int n1=0, n2=1, n3; if(n>0){ n3 = n1 + n2; n1 = n2; n2 = n3; cout<num; cout<<'Fibonacci Series for '<

Produzione:

Immettere il numero di elementi per la serie di Fibonacci: 10
Serie di Fibonacci per 10 numeri: 0 1 1 2 3 5 8 13 21 34

In questo esempio, abbiamo utilizzato una chiamata ricorsiva per generare la sequenza di Fibonacci. Vediamo che i primi due numeri costanti vengono stampati direttamente e per i numeri successivi nella sequenza utilizziamo una funzione ricorsiva.

Palindromo

Un numero palindromo è un numero che, se letto in direzione inversa, è uguale a quello letto da sinistra a destra.

Per esempio, il numero 121 durante la lettura da sinistra a destra e da destra a sinistra legge lo stesso, cioè 121. Quindi 121 è un palindromo.

Il numero 291, quando si legge da destra a sinistra, cioè in ordine inverso, si legge come 192. Quindi 291 non è un palindromo.

#include using namespace std; int reverse_digits(int n, int temp) { if (n == 0) return temp; temp = (temp * 10) + (n % 10); return reverse_digits(n / 10, temp); } int main() { int num; cout<>num; int result = reverse_digits(num, 0); if (result == num) cout << 'Number '<

Produzione:

Immettere il numero per controllare il palindromo: 6556
Il numero 6556 è un palindromo

Lo screenshot per lo stesso è fornito di seguito.

Ricorsione - Palindromo

Nel programma sopra, leggiamo il numero di input dallo standard input. Quindi passiamo questo numero a una funzione ricorsiva per invertire le cifre di un numero. Se le cifre invertite e il numero inserito sono gli stessi, il numero è un palindromo.

Conclusione

Con questo, abbiamo finito con la ricorsione. In questo tutorial, abbiamo studiato la programmazione ricorsiva, la funzione ricorsiva, i suoi vantaggi / svantaggi, insieme a vari esempi in dettaglio.

Oltre a questi esempi, la ricorsione viene utilizzata anche per risolvere alcuni problemi standard come attraversamenti (inorder / preorder / postorder), torri di Hanoi, attraversamento BFS, ecc.

=> Visita qui per imparare C ++ da zero.

Lettura consigliata

^