recursion c
Exploreu tot sobre la recursivitat en C ++ amb exemples clàssics.
com obrir fitxers .jar
Al nostre tutorial anterior, vam aprendre més sobre les funcions en C ++.
A part d'utilitzar les funcions per desglossar el codi en subunitats i fer que el codi sigui més senzill i llegible, les funcions són útils en diverses altres aplicacions, incloses la resolució de problemes en temps real, càlcul matemàtic i estadístic.
A mesura que desenvolupem aplicacions més complexes a C ++, trobem molts requisits, de manera que hem d’utilitzar diversos conceptes especials de C ++. La recursió és un d’aquests conceptes.
=> Visiteu aquí la llista completa de tutorials de C ++.
En aquest tutorial, aprendrem més sobre la recursió, on i per què s’utilitza juntament amb alguns exemples clàssics de C ++ que implementen la recursió.
Què aprendreu:
- Què és la recursió?
- Estat de la base de recursió
- Assignació de memòria per a la trucada recursiva
- Desbordament de pila en recursió
- Recursió indirecta directa i indirecta
- Recursió amb cues i sense cues
- Avantatges / inconvenients de la recursivitat durant la programació iterativa
- Exemples de recursivitat
- Conclusió
- Lectura recomanada
Què és la recursió?
La recursió és un procés en què una funció s'anomena a si mateixa. La funció que implementa la recursió o s'anomena a si mateixa s'anomena funció recursiva. En recursió, la funció recursiva es crida una i altra vegada i continua fins que es compleix una condició final.
La imatge següent mostra com funciona la recursió:
Com veiem al diagrama anterior, la funció principal crida una funció, funct (). La funció funct () al seu torn s'anomena dins de la seva definició. Així funciona la recursió. Aquest procés de crida de la funció continuarà fins que proporcionem una condició final que farà que finalitzi.
Normalment, proporcionem una branca de codi mentre implementem la recursió de manera que proporcionem una condició que activarà la recursió i una altra per dur a terme una execució normal.
Estat de la base de recursió
Quan es duu a terme la recursió, es proporciona la solució al cas base o al cas final i les solucions a problemes més grans es basen en les solucions a problemes més petits.
Considerem un exemple clàssic de recursió, la notació factorial.
Sabem que matemàticament el factorial d’un nombre n és:
n! = nxn-1x ... .x0!
donat aquest 0! = 1;
Així que el factorial per a n = 3 serà 3! = 3 × 2
3! = 3x2x1!
3! = 3x2x2x0!
3! = 3x2x1x1 = 6
De manera programàtica, podem expressar aquest càlcul de la següent manera:
int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); }
Així, tal com es mostra més amunt, hem expressat el càlcul anterior d’un factorial en una trucada a funció recursiva. Veiem que si el nombre n és menor o igual a 1, retornem 1 en lloc d’una trucada recursiva. Això s’anomena condició / cas base per al factorial que permet aturar la recursió.
Per tant, la condició base bàsicament decideix quantes vegades una funció recursiva s’ha de cridar a si mateixa. Això significa que podem calcular molt bé el factorial d’un nombre més gran expressant-lo en termes de nombres més petits fins que s’arribi a la classe base.
A continuació es mostra un exemple perfecte per calcular la factorial d’un nombre:
#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< Sortida:
Introduïu el número que s'ha de calcular el factorial: 10
10! = 3628800
A l'exemple anterior, implementem la recursió. Prenem el nombre del factorial que es troba a partir de l'entrada estàndard i després el passem a la funció factorial.
A la funció factorial, hem donat la condició base com (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.
Assignació de memòria per a la trucada recursiva
Sabem que quan es fa una trucada de funció, l'estat de la funció de trucada s'emmagatzema a la pila i quan es completa una trucada de funció, es restableix aquest estat perquè el programa pugui continuar l'execució.
com crear un correu electrònic fals
Quan es fa una trucada a funció recursiva, l'estat o la memòria de la funció cridada s'assigna a sobre de l'estat de la funció de trucada i es fa una còpia diferent de variables locals per a cada trucada de funció recursiva.
Quan s’arriba a la condició base, la funció torna a la funció de trucada i la memòria es desassigna i el procés continua.
Desbordament de pila en recursió
Quan la recursivitat continua durant un temps il·limitat, pot provocar un desbordament de la pila.
Quan pot continuar la recursivitat així? Una situació és quan no especifiquem la condició base. Una altra situació és quan no s’assoleix la condició base mentre s’executa un programa.
Per exemple,modifiquem el programa factorial anterior i en canviem la condició base.
int factorial(int n){ if(n ==1000) return 1; else return n*factorial(n-1); }
Al codi anterior, hem canviat la condició base a (n == 1000). Ara, si donem el nombre n = 10, podem concloure que la condició base mai no arribarà. D'aquesta manera, en algun moment, la memòria de la pila s'esgotarà, donant lloc a un desbordament de la pila.
Per tant, mentre dissenyem programes recursius, hem de tenir precaució en la condició base que proporcionem.
Recursió indirecta directa i indirecta
Fins ara, en recursivitat, hem vist que la funció s’anomena a si mateixa. Aquesta és la recursió directa.
Hi ha un altre tipus de recursió, és a dir, recursiva indirecta. En això, una funció crida a una altra funció i després aquesta funció crida a la funció de trucada. Si f1 i f2 són dues funcions. Llavors f1 crida a f2 i f2, al seu torn, crida a f1. Es tracta d’una recursió indirecta.
L revisem el nostre programa factorial per demostrar una recursivitat directa.
#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< Sortida:
Introduïu el número el factorial del qual s'ha de calcular: 5
5! = 120
A l'exemple anterior, hem mostrat recursivitat indirecta. La funció principal es diu factorial_a. Factorial_a crida factorial_b. Al seu torn, factorial_b crida factorial_a. Veiem que la sortida del programa no es veu afectada.
Recursió amb cues i sense cues
Una funció recursiva amb cua és una funció recursiva en què s'executa l'última trucada a la funció.
Per exemple, consideri la següent funció.
void display(int n){ if(n<=1) return; cout<<” ”<A l'exemple anterior, la pantalla és una funció recursiva de cua de tal manera que és l'última trucada de funció.
Les funcions en cua es consideren millors que les funcions recursives sense cues, ja que poden ser optimitzades pel compilador. El motiu és que, com que la trucada recursiva amb cua és l'última sentència de la funció, no hi ha cap codi que s'executi després d'aquesta trucada.
Com a resultat, no cal guardar el marc de pila actual per a la funció.
Avantatges / inconvenients de la recursivitat durant la programació iterativa
Els programes recursius proporcionen codi compacte i net. Un programa recursiu és una forma senzilla d’escriure programes. Hi ha alguns problemes inherents com el factorial, la seqüència de Fibonacci, les torres de Hanoi, les travessies d'arbres, etc., que requereixen recursivitat per resoldre-les.
En altres paraules, es resolen de manera eficient amb recursivitat. També es poden resoldre amb programacions iteratives mitjançant piles o altres estructures de dades, però hi ha possibilitats de ser més complexes d’implementar.
Els poders de resolució de problemes de programació recursiva i iterativa són els mateixos. Tanmateix, els programes recursius ocupen més espai de memòria, ja que cal emmagatzemar totes les trucades de funcions a la pila fins que coincideixi amb la casella base.
Les funcions recursives també tenen una sobrecàrrega de temps a causa de massa trucades a funcions i valors de retorn.
Exemples de recursivitat
A continuació, implementarem alguns exemples de programació recursiva.
Sèrie Fibonacci
La sèrie de Fibonacci és la seqüència que es dóna com a
0 1 1 2 3 5 8 13 ......
Com es mostra més amunt, els dos primers números de les sèries de Fibonacci són 0 i 1. El següent número de la seqüència és la suma dels dos números anteriors.
Implantem aquesta sèrie mitjançant Recursion.
programari de conversió de vídeo gratuït per a PC
#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 '< Sortida:
Introduïu el nombre d'elements de la sèrie de Fibonacci: 10
Sèrie Fibonacci per a 10 números: 0 1 1 2 3 5 8 13 21 34
En aquest exemple, hem utilitzat una trucada recursiva per generar la seqüència de Fibonacci. Veiem que els dos primers números que són constants s’imprimeixen directament i per als següents números de la seqüència fem servir una funció recursiva.
Palíndrom
Un número de palíndrom és un número que, quan es llegeix en sentit invers, és el mateix que es llegeix en una direcció d’esquerra a dreta.
Per exemple, el número 121 mentre es llegeix d’esquerra a dreta i de dreta a esquerra diu el mateix, és a dir, 121. Per tant, 121 és un palíndrom.
El número 291, quan es llegeix de dreta a esquerra, és a dir, en ordre invers, es diu com 192. Per tant, el 291 no és un palíndrom.
#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 '< Sortida:
Introduïu el número per comprovar el palíndrom: 6556
El número 6556 és un palíndrom
A continuació es mostra la captura de pantalla del mateix.

Al programa anterior, llegim el número d'entrada de l'entrada estàndard. A continuació, passem aquest número a una funció recursiva per invertir els dígits d’un número. Si els dígits invertits i el número d'entrada són els mateixos, el número és un palíndrom.
Conclusió
Amb això, hem acabat amb la recursió. En aquest tutorial, hem estudiat la programació recursiva, la funció recursiva, els seus avantatges / desavantatges, juntament amb diversos exemples en detall.
A part d’aquests exemples, la recursió també s’utilitza per resoldre alguns problemes estàndard com ara travessies (inorder / preorder / postorder), torres de Hanoi, BFS traversal, etc.
=> Visiteu aquí per aprendre C ++ des de zero.
Lectura recomanada
- Funcions d'amistat a C ++
- Polimorfisme en C ++
- Una visió general completa de C ++
- Tutorial de funcions principals de Python amb exemples pràctics
- Tutorial Unix Pipes: Pipes a la programació Unix
- Funcions de biblioteca a C ++
- 70+ BEST Tutorials C ++ per aprendre programació C ++ GRATIS
- Tutorial QTP # 21 - Com fer que les proves QTP siguin modulars i reutilitzables mitjançant accions i biblioteques de funcions