Meni

Rekurzija v C ++

recursion c

Preizkusite Naš Instrument Za Odpravo Težav

Raziščite vse o rekurziji v jeziku C ++ s klasičnimi primeri.

V prejšnji vadnici smo izvedeli več o funkcijah v C ++.

Funkcije so poleg uporabe funkcij za razčlenitev kode na podenote in enostavnejše in berljivejše kode uporabne v različnih drugih aplikacijah, vključno z reševanjem problemov v realnem času, matematičnimi in statističnimi izračuni.

Ko razvijamo bolj zapletene aplikacije v jeziku C ++, naletimo na številne zahteve, tako da moramo uporabiti več posebnih konceptov jezika C ++. Rekurzija je en tak koncept.

=> Obiščite tukaj za celoten seznam vadnic za C ++.

RECURZIJA V C ++

V tej vadnici bomo izvedeli več o rekurziji, kje in zakaj se uporablja skupaj z nekaterimi klasičnimi primeri C ++, ki izvajajo rekurzijo.

Kaj se boste naučili:

Kaj je rekurzija?

Rekurzija je proces, v katerem se funkcija pokliče sama. Funkcija, ki izvaja rekurzijo ali se sama pokliče, se imenuje rekurzivna funkcija. V rekurziji se rekurzivna funkcija vedno znova pokliče in nadaljuje, dokler ni izpolnjen končni pogoj.

Spodnja slika prikazuje delovanje Rekurzije:

Delovanje rekurzije

Kot vidimo na zgornjem diagramu, glavna funkcija pokliče funkcijo, funct (). Funkcija funct () pa se pokliče znotraj svoje definicije. Tako deluje rekurzija. Ta postopek samega klica funkcije se bo nadaljeval, dokler ne zagotovimo zaključnega pogoja, zaradi katerega se bo končala.

Običajno med izvajanjem rekurzije zagotovimo vejo kode, tako da zagotovimo en pogoj, ki bo sprožil rekurzijo, drugi pa za normalno izvajanje.

Osnovno stanje rekurzije

Ko je izvedena rekurzija, je na voljo rešitev osnovnega primera ali končnega primera in rešitve za večje probleme se gradijo na podlagi rešitev manjših problemov.

Razmislimo o klasičnem primeru rekurzije, faktorijevem zapisu.

najboljša aplikacija za prenos youtube videoposnetkov

Vemo, da je matematično faktorijelo števila n:

n! = nxn-1x ... .x0!
glede na to 0! = 1;

Torej faktorijel za n = 3 bo 3! = 3 × 2!

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

Tako lahko programsko izrazimo ta izračun na naslednji način:

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

Tako smo, kot je prikazano zgoraj, zgornji izračun faktorja izrazili v rekurzivni klic funkcije. Vidimo, da če je število n manjše ali enako 1, vrnemo 1 namesto rekurzivnega klica. To se imenuje osnovni pogoj / primer za faktorijel, ki omogoča zaustavitev rekurzije.

Zato osnovni pogoj v bistvu določa, kolikokrat naj se rekurzivna funkcija pokliče. To pomeni, da lahko zelo dobro izračunamo faktorje večjega števila, tako da ga izrazimo z manjšimi števili, dokler ne dosežemo osnovnega razreda.

Spodaj je odličen primer za izračun faktorja števila:

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

Izhod:

Vnesite število, katerega faktorijel je treba izračunati: 10
10! = 3628800

V zgornjem primeru izvedemo rekurzijo. Število, katerega faktorijel najdemo, vzamemo iz standardnega vhoda in ga nato posredujemo faktorionski funkciji.

V faktorijelski funkciji smo podali osnovni pogoj kot (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.

Dodelitev pomnilnika za rekurzivni klic

Vemo, da se pri klicu funkcije stanje klicne funkcije shrani v sklad in ko je klic funkcije končan, se stanje obnovi nazaj, tako da lahko program nadaljuje izvajanje.

Vprašanja in odgovori za intervju za html5

Ko se izvede rekurzivni klic funkcije, se stanje ali pomnilnik za poklicano funkcijo dodeli povrhu stanja klicne funkcije in za vsak rekurzivni klic funkcije se naredi drugačna kopija lokalnih spremenljivk.

Ko je dosežen osnovni pogoj, se funkcija vrne v klicno funkcijo, pomnilnik se razdeli in postopek se nadaljuje.

Prelivanje skladov v rekurziji

Če se rekurzija nadaljuje neomejeno dolgo, lahko povzroči prelivanje sklada.

Kdaj se lahko rekurzija nadaljuje tako? Ena od situacij je, ko ne določimo osnovnega pogoja. Druga situacija je, ko osnovni pogoj med izvajanjem programa ni dosežen.

Na primer,spremenimo zgornji faktorjski program in spremenimo njegovo osnovno stanje.

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

V zgornji kodi smo osnovni pogoj spremenili v (n == 1000). Če damo število n = 10, lahko sklepamo, da osnovni pogoj ne bo nikoli dosegel. Tako se bo v določenem trenutku izpraznil pomnilnik na kupu, kar bo povzročilo prelivanje sklada.

Zato moramo pri oblikovanju rekurzivnih programov biti previdni glede osnovnega stanja, ki ga zagotavljamo.

Neposredna vsredna rekurzija

Doslej smo v rekurziji videli, da se funkcija sama kliče. To je neposredna rekurzija.

Obstaja še ena vrsta rekurzije, to je posredna rekurzija. Pri tem funkcija pokliče drugo funkcijo, nato pa ta funkcija pokliče klicno funkcijo. Če sta f1 in f2 dve funkciji. Nato f1 pokliče f2, f2 pa f1. To je posredna rekurzija.

L in revidirali bomo svoj faktorski program, da bomo pokazali neposredno rekurzijo.

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

Izhod:

Vnesite število, katerega faktorijel je treba izračunati: 5
5! = 120

V zgornjem primeru smo pokazali posredno rekurzijo. Glavna funkcija pokliče factorial_a. Factorial_a kliče factorial_b. V zameno factorial_b pokliče factorial_a. Vidimo, da na rezultat programa to ne vpliva.

Repasta in nerepa

Repna rekurzivna funkcija je rekurzivna funkcija, pri kateri se v funkciji izvede zadnji klic.

Na primer, upoštevajte naslednjo funkcijo.

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

V zgornjem primeru je zaslon repna rekurzivna funkcija, ki je zadnji klic funkcije.

Repane funkcije veljajo za boljše od nerepanih rekurzivnih funkcij, saj jih lahko prevajalnik optimizira. Razlog je v tem, ker je zadnji rekurzivni klic zadnji stavek v funkciji, po njem ni nobene kode.

Kot rezultat, shranjevanje trenutnega okvira sklada za funkcijo ni potrebno.

kako najti varnostni ključ omrežja v računalniku

Prednosti / slabosti rekurzije zaradi iterativnega programiranja

Rekurzivni programi zagotavljajo kompaktno in čisto kodo. Rekurzivni program je preprost način pisanja programov. Obstajajo nekatere značilne težave, kot so faktorije, Fibonaccijevo zaporedje, stolpi v Hanoju, drevesni prehovi itd., Ki za rešitev potrebujejo rekurzijo.

Z drugimi besedami, učinkovito jih rešimo z rekurzijo. Prav tako jih je mogoče rešiti z iterativnim programiranjem z uporabo skladov ali drugih podatkovnih struktur, vendar obstaja verjetnost, da postanejo bolj zapleteni za izvedbo.

Moči reševanja problemov rekurzivnega in iterativnega programiranja sta enaki. Vendar rekurzivni programi zavzamejo več pomnilniškega prostora, saj je treba vse klice funkcij shraniti v sklad, dokler se ne ujema osnovni primer.

Rekurzivne funkcije imajo tudi časovno obremenitev zaradi preveč klicev funkcij in vrnjenih vrednosti.

Primeri rekurzije

Nato bomo izvedli nekaj primerov rekurzivnega programiranja.

Fibonaccijeva serija

Fibonaccijeva serija je zaporedje, ki je podano kot

0 1 1 2 3 5 8 13 ……

Kot je prikazano zgoraj, sta prvi dve številki Fibonaccijeve serije 0 in 1. Naslednja številka v zaporedju je vsota prejšnjih dveh števil.

Izvedimo to serijo z uporabo Rekurzije.

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

Izhod:

Vnesite število elementov za Fibonaccijevo serijo: 10
Fibonaccijeva serija za 10 številk: 0 1 1 2 3 5 8 13 21 34

V tem primeru smo uporabili rekurzivni klic za generiranje Fibonaccijevega zaporedja. Vidimo, da sta prvi dve številki konstantni neposredno natisnjeni, za naslednja števila v zaporedju pa uporabimo rekurzivno funkcijo.

Palindrom

Število palindromov je število, ki je pri branju v obratni smeri enako branju v smeri od leve proti desni.

Na primer, število 121 med branjem od leve proti desni in od desne proti levi bere enako, torej 121. Torej je 121 palindrom.

Število 291 se pri branju od desne proti levi, torej v obratnem vrstnem redu, bere kot 192. Zato 291 ni 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 '<

Izhod:

Vnesite številko za preverjanje palindrom: 6556
Številka 6556 je palindrom

Posnetek zaslona za isto je podan spodaj.

Rekurzija - Palindrom

V zgornjem programu beremo vhodno številko s standardnega vhoda. Nato to številko posredujemo rekurzivni funkciji, da obrnemo števke števila. Če sta obrnjeni števki in vhodna številka enaki, je številka palindrom.

Zaključek

S tem smo zaključili z rekurzijo. V tej vadnici smo podrobno preučili rekurzivno programiranje, rekurzivno funkcijo, njene prednosti / slabosti, skupaj z različnimi primeri.

Poleg teh primerov se rekurzija uporablja tudi pri reševanju nekaterih standardnih problemov, kot so prečkanje (inorder / preorder / postorder), stolpi v Hanoju, BFS prehod itd.

=> Obiščite tukaj, če se želite naučiti C ++ iz nič.

Priporočeno branje

^