Meny

Rekursjon i C ++

recursion c

Prøv Instrumentet Vårt For Å Eliminere Problemer

Utforsk alt om rekursjon i C ++ med klassiske eksempler.

I vår forrige opplæring lærte vi mer om funksjoner i C ++.

Bortsett fra å bruke funksjonene for å bryte ned koden i underenheter og gjøre koden enklere og lesbar, er funksjoner nyttige i forskjellige andre applikasjoner, inkludert sanntidsløsning, matematisk og statistisk beregning.

Når vi utvikler mer komplekse applikasjoner i C ++, kommer vi over mange krav slik at vi trenger å bruke flere spesielle konsepter for C ++. Rekursjon er et slikt konsept.

=> Besøk her for den komplette C ++ opplæringslisten.

REKURSJON I C ++

I denne veiledningen vil vi lære mer om rekursjon, hvor og hvorfor den brukes sammen med noen klassiske C ++ eksempler som implementerer rekursjon.

Hva du vil lære:

Hva er rekursjon?

Rekursjon er en prosess der en funksjon kaller seg. Funksjonen som implementerer rekursjon eller kaller seg selv kalles en rekursiv funksjon. I rekursjon kaller den rekursive funksjonen seg om og om igjen og fortsetter til en sluttbetingelse er oppfylt.

Bildet nedenfor viser hvordan Rekursjon fungerer:

Arbeid av rekursjon

Som vi ser i diagrammet ovenfor, kaller hovedfunksjonen en funksjon, funct (). Funksjon funct () i sin tur kaller seg inne i definisjonen. Slik fungerer rekursjonen. Denne prosessen med funksjonen som kaller seg, vil fortsette til vi gir en avsluttende tilstand som får den til å slutte.

Vanligvis tilbyr vi kodegren mens vi implementerer rekursjon slik at vi gir en betingelse som vil utløse rekursjon og en annen for å utføre normal kjøring.

Rekursjon Basistilstand

Når rekursjon utføres, blir løsningen på basissaken eller avslutningssaken gitt, og løsningene på større problemer bygges basert på løsningene på mindre problemer.

La oss vurdere et klassisk eksempel på Recursion, Faktor-notasjonen.

Vi vet at matematisk er faktoren til et tall n:

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

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

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

Så programmatisk kan vi uttrykke denne beregningen som følger:

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

Således, som vist ovenfor, har vi uttrykt den ovennevnte beregningen av en faktor i et rekursivt funksjonsanrop. Vi ser at hvis tallet n er mindre enn eller lik 1, returnerer vi 1 i stedet for et rekursivt anrop. Dette kalles basistilstanden / saken for fabrikkstedet som gjør det mulig å stoppe rekursjonen.

Derfor bestemmer basistilstanden i utgangspunktet hvor mange ganger en rekursiv funksjon skal kalle seg selv. Dette betyr at vi veldig godt kan beregne faktoren for et større tall ved å uttrykke det i form av mindre tall til basisklassen er nådd.

Nedenfor er et perfekt eksempel for å beregne faktoren for et tall:

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

Produksjon:

Skriv inn nummeret som skal beregnes: 10
10! = 3628800

I eksemplet ovenfor implementerer vi rekursjon. Vi tar nummeret som skal finnes fra standardinngangen, og overfører det til faktorfunksjonen.

I faktorfunksjonen har vi gitt grunnbetingelsen 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.

Minnetildeling for den rekursive samtalen

Vi vet at når en funksjonsanrop blir foretatt, blir tilstanden til anropsfunksjonen lagret på bunken, og når en funksjonsanrop er fullført, blir den tilstanden gjenopprettet slik at programmet kan fortsette å kjøre.

Når det blir foretatt et rekursivt funksjonsanrop, tildeles tilstanden eller minnet for den anropte funksjonen på toppen av tilstanden til anropsfunksjonen, og det lages en annen kopi av lokale variabler for hver rekursive funksjonsanrop.

Når basistilstanden er nådd, går funksjonen tilbake til anropsfunksjonen og minnet tildeles og prosessen fortsetter.

Stack Overflow In Recursion

Når rekursjon fortsetter i ubegrenset tid, kan det resultere i stabeloverløp.

Når kan rekursjon fortsette slik? En situasjon er når vi ikke spesifiserer grunntilstanden. En annen situasjon er når basistilstanden ikke er nådd mens du kjører et program.

For eksempel,vi endrer ovennevnte faktorprogram og endrer basistilstanden.

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

I koden ovenfor har vi endret grunntilstanden til (n == 1000). Nå, hvis vi gir tallet n = 10, kan vi konkludere med at basistilstanden aldri vil nå. På denne måten vil minnet på bunken være utmattet, noe som resulterer i stabeloverløp.

Derfor må vi være forsiktige med grunntilstanden vi gir når vi designer rekursive programmer.

Direkte mot indirekte rekursjon

Så langt i rekursjon har vi sett funksjonen kaller seg selv. Dette er den direkte rekursjonen.

Det er en annen type rekursjon, dvs. indirekte rekursjon. I dette kaller en funksjon en annen funksjon, og deretter kaller denne funksjonen anropsfunksjonen. Hvis f1 og f2 er to funksjoner. Deretter kaller f1 f2 og f2, i sin tur kaller f1. Dette er en indirekte rekursjon.

programvare for å kopiere dvd til datamaskin

L et oss revidere vårt faktorprogram for å demonstrere direkte rekursjon.

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

Produksjon:

Tast inn nummeret som skal beregnes: 5
5! = 120

I eksemplet ovenfor har vi vist indirekte rekursjon. Hovedfunksjonen kaller factorial_a. Faktor_a kaller faktor_b. I sin tur kaller factorial_b factorial_a. Vi ser at produksjonen av programmet ikke påvirkes.

Halet og ikke-halet rekursjon

En tailed rekursiv funksjon er en rekursiv funksjon der den siste samtalen utføres i funksjonen.

For eksempel, vurder følgende funksjon.

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

I eksemplet ovenfor er skjermen en tailed rekursiv funksjon slik at det er den siste funksjonsanropet.

Tailed funksjoner anses å være bedre enn ikke-tailed rekursive funksjoner, da de kan optimaliseres av kompilatoren. Årsaken er at ettersom den tailed rekursive samtalen er den siste setningen i funksjonen, er det ingen kode å utføre etter denne samtalen.

Som et resultat er det ikke nødvendig å lagre den nåværende stabelrammen for funksjonen.

Fordeler / ulemper med rekursjon over Iterativ programmering

Rekursive programmer gir kompakt og ren kode. Et rekursivt program er en enkel måte å skrive programmer på. Det er noen iboende problemer som faktoria, Fibonacci-sekvens, tårnene i Hanoi, treoverganger osv. Som krever rekursjon for å løse.

De løses med andre ord effektivt med rekursjon. De kan også løses med iterativ programmering ved hjelp av stabler eller andre datastrukturer, men det er sjanser for å bli mer komplekse å implementere.

Problemløsende krefter for rekursiv så vel som iterativ programmering er de samme. Rekursive programmer tar imidlertid mer hukommelsesplass, ettersom alle funksjonsanropene må lagres på bunken til basissaken er matchet.

Rekursive funksjoner har også en tidsomkostning på grunn av for mange funksjonsanrop og returverdier.

Eksempler på rekursjon

Deretter vil vi implementere noen av eksemplene på rekursiv programmering.

Fibonacci-serien

Fibonacci-serien er sekvensen som er gitt som

0 1 1 2 3 5 8 13 ……

Som vist ovenfor er de to første tallene i Fibonacci-serien 0 og 1. Det neste tallet i sekvensen er summen av de to foregående tallene.

La oss implementere denne serien ved hjelp av 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 '<

Produksjon:

Angi antall elementer for Fibonacci-serien: 10
Fibonacci-serien for 10 tall: 0 1 1 2 3 5 8 13 21 34

I dette eksemplet har vi brukt en rekursiv samtale for å generere Fibonacci-sekvensen. Vi ser at de to første tallene som er konstante blir skrevet direkte ut, og for de neste tallene i sekvensen bruker vi en rekursiv funksjon.

Palindrom

Et palindromtall er et tall som når det leses i omvendt retning, er det samme som lest i venstre mot høyre retning.

For eksempel, tallet 121 mens du leser fra venstre til høyre og høyre mot venstre leser det samme, dvs. 121. Derfor er 121 et palindrom.

Tallet 291, når du leser fra høyre til venstre, dvs. i omvendt rekkefølge, leser 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 '<

Produksjon:

Skriv inn nummeret du vil sjekke palindrom: 6556
Nummer 6556 er et palindrom

Skjermbilde for det samme er gitt nedenfor.

Rekursjon - Palindrome

I programmet ovenfor leser vi inngangsnummeret fra standardinngangen. Deretter overfører vi dette tallet til en rekursiv funksjon for å reversere sifrene i et tall. Hvis de omvendte sifrene og inngangstallet er det samme, er tallet et palindrom.

Konklusjon

Med dette er vi ferdig med rekursjonen. I denne opplæringen har vi studert rekursiv programmering, rekursiv funksjon, dens fordeler / ulemper, sammen med forskjellige eksempler i detalj.

Bortsett fra disse eksemplene, brukes rekursjon også til å løse noen standardproblemer som traversaler (ordre / forhåndsbestilling / postordre), tårnene i Hanoi, BFS-traversal, etc.

=> Besøk her for å lære C ++ fra grunnen.

Anbefalt lesing

^