Menu

Rekursion i C ++

recursion c

Prøv Vores Instrument Til At Fjerne Problemer

Udforsk alt om rekursion i C ++ med klassiske eksempler.

I vores tidligere tutorial lærte vi mere om funktioner i C ++.

Bortset fra at bruge funktionerne til at nedbryde koden i underenheder og gøre koden enklere og læsbar, er funktioner nyttige i forskellige andre applikationer, herunder realtidsopgaver, matematisk og statistisk beregning.

Efterhånden som vi udvikler mere komplekse applikationer i C ++, støder vi på mange krav, så vi skal bruge flere specielle koncepter for C ++. Rekursion er et sådant koncept.

=> Besøg her for den komplette C ++ tutorials liste.

RECURSION I C ++

I denne vejledning lærer vi mere om rekursion, hvor og hvorfor det bruges sammen med nogle klassiske C ++ eksempler, der implementerer rekursion.

Hvad du vil lære:

Hvad er rekursion?

Rekursion er en proces, hvor en funktion kalder sig selv. Funktionen, der implementerer rekursion eller kalder sig selv, kaldes en rekursiv funktion. I rekursion kalder den rekursive funktion sig igen og igen og fortsætter, indtil en slutbetingelse er opfyldt.

Billedet nedenfor viser, hvordan Rekursion fungerer:

Arbejde med rekursion

Som vi ser i ovenstående diagram, kalder hovedfunktionen en funktion, funct (). Funktion funct () kalder igen sig inde i sin definition. Sådan fungerer rekursionen. Denne proces med den funktion, der kalder sig selv, fortsætter, indtil vi giver en afsluttende tilstand, der får den til at ende.

Normalt leverer vi kodefil, mens vi implementerer rekursion, så vi leverer en betingelse, der vil udløse rekursion, og en anden til at udføre normal udførelse.

Rekursions basistilstand

Når rekursion udføres, leveres løsningen på basissagen eller den afsluttende sag, og løsningerne på større problemer bygges baseret på løsningerne på mindre problemer.

Lad os overveje et klassisk eksempel på rekursion, den faktuelle notation.

Vi ved, at matematisk er faktoren for et tal n:

n! = nxn-1x… .x0!
givet at 0! = 1;

Så faktorielt for n = 3 vil være 3! = 3 × 2!

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

Så programmatisk kan vi udtrykke denne beregning som følger:

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

Som vist ovenfor har vi således udtrykt ovennævnte beregning af en faktor i et rekursivt funktionsopkald. Vi ser, at hvis tallet n er mindre end eller lig med 1, returnerer vi 1 i stedet for et rekursivt opkald. Dette kaldes basistilstanden / sagen for det faktuelle, som gør det muligt at stoppe rekursionen.

Derfor bestemmer basistilstanden grundlæggende, hvor mange gange en rekursiv funktion skal kalde sig selv. Det betyder, at vi meget godt kan beregne et større tal ved at udtrykke det i form af mindre tal, indtil basisklassen er nået.

Nedenfor er et perfekt eksempel til beregning af et tals faktura:

#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<

Produktion:

Indtast nummeret, hvis fabrik skal beregnes: 10
10! = 3628800

I ovenstående eksempel implementerer vi rekursion. Vi tager nummeret, hvis fabriksnummer skal findes fra standardindgangen, og sender det derefter til faktorfunktionen.

I faktorfunktionen har vi givet basisbetingelsen som (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.

Hukommelsesallokering til det rekursive opkald

Vi ved, at når et funktionsopkald foretages, gemmes opkaldsfunktionens tilstand på stakken, og når et funktionsopkald er afsluttet, gendannes tilstanden tilbage, så programmet kan fortsætte udførelsen.

Når der foretages et rekursivt funktionsopkald, tildeles tilstanden eller hukommelsen til den kaldte funktion oven på tilstanden for opkaldsfunktionen, og der laves en anden kopi af lokale variabler for hvert rekursive funktionsopkald.

Når basistilstanden er nået, vender funktionen tilbage til opkaldsfunktionen, og hukommelsen allokeres, og processen fortsætter.

Stakoverløb i rekursion

Når rekursion fortsætter i et ubegrænset tidsrum, kan det resultere i en stackoverløb.

Hvornår kan rekursion fortsætte sådan? En situation er, når vi ikke angiver basistilstanden. En anden situation er, at basistilstanden ikke er nået under udførelse af et program.

For eksempel,vi ændrer ovenstående faktorprogram og ændrer dets basistilstand.

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

I ovenstående kode har vi ændret basistilstanden til (n == 1000). Hvis vi nu angiver tallet n = 10, kan vi konkludere, at basisbetingelsen aldrig når. På denne måde vil hukommelsen på stakken på et tidspunkt blive opbrugt, hvilket resulterer i et stackoverløb.

Derfor skal vi være forsigtige med den basistilstand, vi leverer, mens vi designer rekursive programmer.

Direkte mod indirekte rekursion

Indtil videre i rekursion har vi set funktionen kalde sig selv. Dette er den direkte rekursion.

Der er en anden type rekursion, dvs. indirekte rekursion. I dette kalder en funktion en anden funktion, og derefter kalder denne funktion opkaldsfunktionen. Hvis f1 og f2 er to funktioner. Derefter kalder f1 f2 og f2 til gengæld f1. Dette er en indirekte rekursion.

softwarekvalitetssikring inden for softwareteknik

L et os revidere vores faktorprogram for at demonstrere direkte rekursion.

#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<

Produktion:

Indtast det nummer, hvis fabrik skal beregnes: 5
5! = 120

I ovenstående eksempel har vi vist indirekte rekursion. Hovedfunktionen kalder factorial_a. Factorial_a kalder factorial_b. Til gengæld kalder factorial_b factorial_a. Vi ser, at output fra programmet ikke påvirkes.

Halet og ikke-halet rekursion

En tailed rekursiv funktion er en rekursiv funktion, hvor det sidste opkald udføres i funktionen.

For eksempel, overvej følgende funktion.

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

I ovenstående eksempel er displayet en tailed rekursiv funktion, således at det er det sidste funktionsopkald.

Tailed funktioner betragtes som bedre end ikke-tailed rekursive funktioner, da de kan optimeres af compileren. Årsagen er, at da det tailed rekursive opkald er det sidste udsagn i funktionen, er der ingen kode, der skal udføres efter dette opkald.

Som et resultat er det ikke nødvendigt at gemme den aktuelle stabelramme til funktionen.

Fordele / ulemper ved rekursion over Iterativ programmering

Rekursive programmer giver kompakt og ren kode. Et rekursivt program er en enkel måde at skrive programmer på. Der er nogle iboende problemer som faktor, Fibonacci-sekvens, tårne ​​i Hanoi, træpasninger osv., Der kræver rekursion for at løse.

Med andre ord løses de effektivt med rekursion. De kan også løses med iterativ programmering ved hjælp af stakke eller andre datastrukturer, men der er chancer for at blive mere komplekse at implementere.

Problemløsningskræfter ved rekursiv såvel som iterativ programmering er de samme. Rekursive programmer tager dog mere hukommelsesplads, da alle funktionsopkald skal lagres på stakken, indtil basissagen matches.

Rekursive funktioner har også en tidsomkostning på grund af for mange funktionsopkald og returværdier.

Eksempler på rekursion

Dernæst implementerer vi nogle af eksemplerne på rekursiv programmering.

Fibonacci-serien

Fibonacci-serien er den rækkefølge, der gives som

0 1 1 2 3 5 8 13 ……

Som vist ovenfor er de første to tal i Fibonacci-serien 0 og 1. Det næste tal i sekvensen er summen af ​​de foregående to tal.

Lad os implementere denne serie ved hjælp af Recursion.

#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 '<

Produktion:

Indtast antallet af elementer for Fibonacci-serien: 10
Fibonacci-serien til 10 numre: 0 1 1 2 3 5 8 13 21 34

I dette eksempel har vi brugt et rekursivt opkald til at generere Fibonacci-sekvensen. Vi ser, at de første to tal, der er konstante, udskrives direkte, og for de næste tal i sekvensen bruger vi en rekursiv funktion.

Palindrom

Et palindromtal er et tal, som når det læses i omvendt retning, er det samme som det læses i venstre mod højre retning.

For eksempel, tallet 121 under læsning fra venstre til højre og højre mod venstre læser det samme, dvs. 121. Derfor er 121 et palindrom.

Nummeret 291, når man læser fra højre til venstre, dvs. i omvendt rækkefølge, læser som 192. Derfor er 291 ikke et palindrom.

#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 '<

Produktion:

Indtast det nummer, der skal kontrolleres palindrom: 6556
Nummer 6556 er et palindrom

Skærmbillede af det samme er angivet nedenfor.

Rekursion - Palindrom

I ovenstående program læser vi inputnummeret fra standardindgangen. Derefter overfører vi dette tal til en rekursiv funktion for at vende cifrene i et tal. Hvis de omvendte cifre og inputnummeret er de samme, er tallet et palindrom.

Konklusion

Med dette er vi færdige med rekursionen. I denne vejledning har vi studeret rekursiv programmering, rekursiv funktion, dens fordele / ulemper sammen med forskellige eksempler i detaljer.

Bortset fra disse eksempler bruges rekursion også til at løse nogle standardproblemer som traversaler (inorder / preorder / postorder), tårne ​​i Hanoi, BFS traversal osv.

=> Besøg her for at lære C ++ fra bunden.

Anbefalet læsning

^