Meny

Rekursion i C ++

recursion c

Prova Vårt Instrument För Att Eliminera Problem

Utforska allt om rekursion i C ++ med klassiska exempel.

I vår tidigare handledning lärde vi oss mer om funktioner i C ++.

Förutom att använda funktionerna för att bryta ner koden i underenheter och göra koden enklare och läsbar, är funktioner användbara i olika andra applikationer inklusive realtidslösning, matematisk och statistisk beräkning.

När vi utvecklar mer komplexa applikationer i C ++, stöter vi på många krav så att vi måste använda flera speciella koncept för C ++. Rekursion är ett sådant koncept.

=> Besök här för en komplett lista över C ++ -studier.

ÅTERKOMST I C ++

I den här handledningen lär vi oss mer om rekursion, var och varför den används tillsammans med några klassiska C ++ - exempel som implementerar rekursion.

Vad du kommer att lära dig:

Vad är rekursion?

Rekursion är en process där en funktion kallar sig själv. Funktionen som implementerar rekursion eller kallar sig själv kallas en rekursiv funktion. I rekursion kallar den rekursiva funktionen sig om och om igen och fortsätter tills ett slutvillkor är uppfyllt.

Bilden nedan visar hur Rekursion fungerar:

Arbeta med rekursion

Som vi ser i ovanstående diagram kallar huvudfunktionen en funktion, funct (). Funktion funkt () i sin tur kallar sig inuti sin definition. Så här fungerar rekursionen. Denna process med funktionen som anropar sig kommer att fortsätta tills vi tillhandahåller ett avslutande tillstånd som gör att det slutar.

Vanligtvis tillhandahåller vi kodgren medan vi implementerar rekursion så att vi tillhandahåller ett villkor som kommer att utlösa rekursion och ett annat för att utföra normal körning.

Rekursions basförhållande

När rekursion utförs tillhandahålls lösningen på basfallet eller avslutningsfallet och lösningarna på större problem byggs utifrån lösningarna på mindre problem.

Låt oss överväga ett klassiskt exempel på Recursion, Faktor-notationen.

Vi vet att matematiskt är faktorn för ett nummer n:

n! = nxn-1x ... .x0!
med tanke på att 0! = 1;

Så faktiskt för n = 3 blir 3! = 3 × 2!

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

Så programmatiskt kan vi uttrycka denna beräkning på följande sätt:

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

Således, som visat ovan, har vi uttryckt ovanstående beräkning av en faktor i ett rekursivt funktionsanrop. Vi ser att om antalet n är mindre än eller lika med 1, returnerar vi 1 istället för ett rekursivt samtal. Detta kallas basvillkor / fall för fabriken som gör det möjligt att stoppa rekursionen.

Därför bestämmer grundvillkoret i princip hur många gånger en rekursiv funktion ska kalla sig. Detta innebär att vi mycket väl kan beräkna faktorn för ett större antal genom att uttrycka det i form av mindre antal tills basklassen nås.

Nedan är ett perfekt exempel för att beräkna ett tals faktoria:

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

Ange numret vars faktoria ska beräknas: 10
10! = 3628800

I exemplet ovan implementerar vi rekursion. Vi tar numret vars faktoria ska hittas från standardingången och skickar det sedan till faktorfunktionen.

I faktorfunktionen har vi gett basvillkoret 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.

Minnesallokering för det rekursiva samtalet

Vi vet att när ett funktionsanrop görs lagras anropsfunktionens tillstånd på stacken och när ett funktionsanrop är avslutat återställs det tillståndet så att programmet kan fortsätta körningen.

När ett rekursivt funktionsanrop görs, tilldelas tillståndet eller minnet för den anropade funktionen ovanpå tillståndet för den anropande funktionen och en annan kopia av lokala variabler görs för varje rekursivt funktionsanrop.

När basvillkoret har uppnåtts återgår funktionen till den anropande funktionen och minnet allokeras och processen fortsätter.

Stacköverflöde i rekursion

När rekursion fortsätter under obegränsad tid kan det resultera i stacköverflöde.

När kan rekursion fortsätta så här? En situation är när vi inte anger basvillkoret. En annan situation är när basvillkoren inte uppnås när ett program körs.

Till exempel,vi modifierar ovanstående faktorprogram och ändrar dess grundförhållande.

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

I ovanstående kod har vi ändrat basvillkoret till (n == 1000). Om vi ​​nu anger siffran n = 10 kan vi dra slutsatsen att grundvillkoret aldrig kommer att nå. På detta sätt kommer minnet på stacken att förbrukas någon gång, vilket resulterar i ett stacköverflöde.

Därför, när vi utformar rekursiva program, måste vi vara försiktiga med det grundläggande tillstånd vi tillhandahåller.

Direkt mot indirekt rekursion

Hittills i rekursion har vi sett att funktionen kallar sig själv. Detta är den direkta rekursionen.

Det finns en annan typ av rekursion, dvs. indirekt rekursion. I detta kallar en funktion en annan funktion och sedan kallar den här funktionen den anropande funktionen. Om f1 och f2 är två funktioner. Sedan ringer f1 f2 och f2, i sin tur, samtal f1. Detta är en indirekt rekursion.

c ++ praktiska frågor och svar pdf

L och vi reviderar vårt faktorprogram för att visa direkt 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:

Ange numret vars faktoria ska beräknas: 5
5! = 120

I exemplet ovan har vi visat indirekt rekursion. Huvudfunktionen kallar factorial_a. Fakta_a kallar faktor_b. I sin tur kallar factorial_b factorial_a. Vi ser att resultatet av programmet inte påverkas.

Tailed och Icke-Tailed rekursion

En svansad rekursiv funktion är en rekursiv funktion där det senaste samtalet utförs i funktionen.

Till exempel, överväga följande funktion.

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

I exemplet ovan är displayen en svansad rekursiv funktion så att den är det senaste funktionsanropet.

Tailed funktioner anses vara bättre än icke-tailed rekursiva funktioner eftersom de kan optimeras av kompilatorn. Anledningen är att eftersom det svansade rekursiva samtalet är det sista uttalandet i funktionen finns det ingen kod att exekvera efter det här samtalet.

Som ett resultat är det inte nödvändigt att spara den aktuella stapelramen för funktionen.

Fördelar / nackdelar med rekursion över Iterativ programmering

Rekursiva program ger kompakt och ren kod. Ett rekursivt program är ett enkelt sätt att skriva program. Det finns några inneboende problem som faktoria, Fibonacci-sekvens, torn i Hanoi, trädkorsningar etc. som kräver rekursion för att lösa.

Med andra ord löses de effektivt med rekursion. De kan också lösas med iterativ programmering med stackar eller andra datastrukturer men det finns chanser att bli mer komplexa att implementera.

Problemlösningskrafter för både rekursiv och iterativ programmering är desamma. Rekursiva program tar dock mer minnesutrymme eftersom alla funktionssamtal behöver lagras på stacken tills basfodralet matchas.

Rekursiva funktioner har också en tidsoverhead på grund av för många funktionsanrop och returvärden.

Exempel på rekursion

Därefter implementerar vi några av exemplen på rekursiv programmering.

Fibonacci-serien

Fibonacci-serien är den sekvens som ges som

0 1 1 2 3 5 8 13 ……

Som visas ovan är de första två siffrorna i Fibonacci-serien 0 och 1. Nästa nummer i sekvensen är summan av de två föregående siffrorna.

Låt oss implementera den här serien med 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:

Ange antalet element för Fibonacci-serien: 10
Fibonacci-serien för 10 nummer: 0 1 1 2 3 5 8 13 21 34

I det här exemplet har vi använt ett rekursivt samtal för att generera Fibonacci-sekvensen. Vi ser att de två första siffrorna som är konstanta skrivs ut direkt och för nästa nummer i sekvensen använder vi en rekursiv funktion.

Palindrom

Ett palindromnummer är ett tal som när det läses i omvänd riktning är detsamma som läst i vänster till höger riktning.

Till exempel, siffran 121 medan man läser från vänster till höger och höger till vänster läser densamma d.v.s. 121. Därför är 121 en palindrom.

Siffran 291, när man läser från höger till vänster, dvs. i omvänd ordning, läser som 192. Därför är 291 inte en 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:

Ange det nummer som ska kontrolleras palindrom: 6556
Nummer 6556 är ett palindrom

Skärmdump för detsamma ges nedan.

Rekursion - Palindrom

I ovanstående program läser vi inmatningsnumret från standardingången. Sedan skickar vi detta nummer till en rekursiv funktion för att vända siffrorna i ett nummer. Om de omvända siffrorna och inmatningsnumret är desamma är numret ett palindrom.

Slutsats

Med detta har vi avslutat rekursionen. I denna handledning har vi studerat rekursiv programmering, rekursiv funktion, dess fördelar / nackdelar, tillsammans med olika exempel i detalj.

Bortsett från dessa exempel används rekursion också för att lösa vissa standardproblem som traversaler (inorder / preorder / postorder), torn i Hanoi, BFS-traversal etc.

=> Besök här för att lära dig C ++ från Scratch.

Rekommenderad läsning

^