Introduzione alla funzione ricorsiva in C ++
Per iniziare con la funzione ricorsiva in C ++, abbiamo già conosciuto l'idea di base dietro le funzioni C ++ che include la definizione di funzione per chiamare anche altre funzioni. E questo articolo copre il concetto alla base della definizione ricorsiva, un concetto di strumento di gioco in matematica e logica di programmazione. Un esempio familiare include fattoriale di un numero, somma di 'n' numeri naturali, ecc. Una funzione che chiama da sola è nota come funzione ricorsiva. Sono solo una funzione che viene invocata ripetutamente. La ricorsione ha uno strumento di risoluzione dei problemi, in cui divide i problemi più grandi in compiti semplici e si allena individualmente per seguire una sequenza individuale.
I concetti di strutture di dati come la ricerca, l'ordinamento, l'attraversamento di un albero fanno uso della funzione ricorsiva per le sue soluzioni. Questa tecnica di programmazione semplifica il codice. Sia l'iterazione che la ricorsione eseguono lo stesso processo di una ripetizione del codice, ma la differenza nella ricorsione è che eseguono una parte specifica con la funzione di base stessa. In questo articolo discuteremo dell'importanza della ricorsione e del loro processo di lavoro con un esempio in dettaglio.
Sintassi della funzione ricorsiva in C ++
La sintassi generale della funzione ricorsiva in c ++ è data come:
return type function name((arguments))
(
Body of the statements;
function name ((actual arguments)) // recursive function
)
Come funziona la funzione ricorsiva in C ++?
La ricorsione esegue la ripetizione sulle chiamate di funzione e interrompe l'esecuzione quando il caso base diventa vero. È necessario definire una condizione del caso base nella funzione ricorsiva per evitare il messaggio di errore di overflow dello stack. Se non viene definito alcun caso base, si ha una ricorsione infinita. Quando viene chiamata una funzione, li spinge in una pila ogni volta per riservare le risorse per ogni chiamata ripetuta. Dà il meglio in traversata di alberi. Esistono due diversi tipi di ricorsione: ricorsione diretta e indiretta.
Ricorsivo diretto: illustrazione
int fibn(n)
(
fib(n);
)
void main ()
(
fib(n);
)
Il formato sopra è la chiamata ricorsiva diretta dove chiama immediatamente / chiama da sola. Considera un secondo tipo chiamato ricorsione indiretta che comporta un'altra chiamata di funzione. Può essere visualizzato nell'illustrazione seguente:
Ricorsivo indiretto: illustrazione
void f(int n) (
f1();
return;
)
void f2( int n) (
f();
return;
)
void f1() (
f2();
return;
)
Esempi di funzione ricorsiva in C ++
Nel programma seguente puoi vedere l'esecuzione del programma che ho fornito con la condizione di base predefinita. A volte l'uso della condizione if-else nella ricorsione aiuta a prevenire la ricorsione infinita. Il processo del codice viene eseguito con la soluzione parziale all'intermedio e questi vengono combinati in una soluzione finale in una ricorsione della coda.
Esempio 1
Ecco un semplice esempio di una serie di un numero di Fibonacci. Il programma seguente include una chiamata alla funzione ricorsiva definita come fib (int n) che accetta input dall'utente e lo memorizza in 'n'. Il passaggio successivo include prendere in ciclo for per generare il termine che viene passato alla funzione fib () e restituisce la serie Fibonacci. Il caso base viene impostato con l'istruzione if controllando il numero = 1 o 2 per stampare i primi due valori. infine, questa funzione ricorsiva continua con il ciclo per stampare la serie 1, 1, 2.
Codice:
#include
using namespace std;
int fib_r (int s)
(
if(s==1||s==2)
return 1;
else
return (fib_r(s-1) +fib_r(s-2)); // fib(n-1) + fib(n-2) for adding successive terms
)
int main ()
(
int k, n;
cout<<"Enter no.of n terms: ";
cin>>n;
cout<<" calculated fibonacci numbers are"< for (k=1; k<=n; k++)
cout< return 0;
)#include
using namespace std;
int fib_r (int s)
(
if(s==1||s==2)
return 1;
else
return (fib_r(s-1) +fib_r(s-2)); // fib(n-1) + fib(n-2) for adding successive terms
)
int main ()
(
int k, n;
cout<<"Enter no.of n terms: ";
cin>>n;
cout<<" calculated fibonacci numbers are"< for (k=1; k<=n; k++)
cout< return 0;
)#include
using namespace std;
int fib_r (int s)
(
if(s==1||s==2)
return 1;
else
return (fib_r(s-1) +fib_r(s-2)); // fib(n-1) + fib(n-2) for adding successive terms
)
int main ()
(
int k, n;
cout<<"Enter no.of n terms: ";
cin>>n;
cout<<" calculated fibonacci numbers are"< for (k=1; k<=n; k++)
cout< return 0;
)
Produzione:
Esempio n. 2
Verifica del numero del palindromo utilizzando una funzione ricorsiva.
Codice:
#include
using namespace std;
int palim(int a, int t)
(
if (a == 0)
return t;
t = (t * 10) + (a % 10);
return palim(a / 10, t);
)
int main()
(
int n;
cout<>n;
int result = palim(n, 0);
if (result == n)
cout << "Number "< else
cout << "Number "< return 0;
)#include
using namespace std;
int palim(int a, int t)
(
if (a == 0)
return t;
t = (t * 10) + (a % 10);
return palim(a / 10, t);
)
int main()
(
int n;
cout<>n;
int result = palim(n, 0);
if (result == n)
cout << "Number "< else
cout << "Number "< return 0;
)#include
using namespace std;
int palim(int a, int t)
(
if (a == 0)
return t;
t = (t * 10) + (a % 10);
return palim(a / 10, t);
)
int main()
(
int n;
cout<>n;
int result = palim(n, 0);
if (result == n)
cout << "Number "< else
cout << "Number "< return 0;
)
Produzione:
Esempio n. 3
Programma con un generatore di numeri casuali.
Codice:
#include
#include
#include
#include
using namespace std;
int rand1(int n);
int main () (
int n, j;
int r;
srand(time (NULL));
cout << "Enter number of dice: ";
cin >> n;
for (j = 1; j <= n; j++) (
r = rand1(5) + 1;
cout << r << " ";
)
system("PAUSE");
return 0;
)
int rand1(int n) (
return rand () % n;
)
Il programma sopra illustra un generatore di numeri casuali quando un dado viene lanciato casualmente. Viene eseguito chiamando una funzione rand1 (int n) e genera numeri da 0 a n-1. e impostando il valore seed con null (nessun indirizzo). Ad esempio, se immettiamo come 4 si lancia una possibilità di dadi come 5, 4, 1, 2.
Produzione:
Ci sono anche alcuni concetti come la ricerca lineare, il divisore comune e il fattoriale più importante di un dato numero che usa l'implementazione ricorsiva.
Pro della ricorsione
- Il codice fornito da loro è pulito e compatto semplificando il programma complesso più grande. Utilizza meno variabili nel codice del programma.
- Qui vengono evitati codici complessi e nidificati per loop.
- Alcune parti del codice richiedono il backtracking che viene risolto in modo ricorsivo.
Contro di ricorsione
- Richiede più allocazione di memoria a causa dell'operazione dello stack di tutte le chiamate di funzione.
- A volte si comporta più lentamente durante l'esecuzione del processo di iterazione. Pertanto, l'efficienza è inferiore.
- È difficile per i principianti capire il funzionamento poiché a volte il codice è approfondito. se porta a spazio insufficiente e alla fine provoca arresti anomali del programma.
Conclusione
Con questo, abbiamo discusso di come funzionano le funzioni di c ++ e definito in modo ricorsivo. E abbiamo esaminato la corrispondenza e i loro pro e contro della funzione ricorsiva nel mondo della programmazione. Quindi abbiamo continuato mostrando come può essere implementato in C ++ usando una definizione di funzione ricorsiva. Inoltre, concludiamo che la ricorsione aiuta in C ++ a risolvere problemi nei concetti di struttura dei dati come attraversamenti, ordinamento e ricerca e che possono essere utilizzati in modo efficace ovunque sia necessario.
Articoli consigliati
Questa è una guida alla funzione ricorsiva in C ++. Qui discutiamo di come funziona la funzione ricorsiva in C ++, la sintassi insieme a diversi esempi e implementazione del codice. Puoi anche consultare i seguenti articoli per saperne di più -
- Che cosa sono le funzioni di array C ++?
- Panoramica delle funzioni di stringa C ++
- Miglior compilatore C ++ (esempi)
- Introduzione ai comandi C ++
- Serie Fibonacci in Java
- Generatore di numeri casuali in Matlab
- Generatore di numeri casuali in C #
- Palindrome in C ++
- Generatore di numeri casuali in JavaScript
- Principali 11 caratteristiche e vantaggi di C ++
- Scopri i tipi di funzioni di array in PHP