Meni

Rekurzija u C ++

recursion c

Isprobajte Naš Instrument Za Uklanjanje Problema

Istražite sve o rekurziji na jeziku C ++ s klasičnim primjerima.

U našem prethodnom vodiču saznali smo više o funkcijama na C ++.

Osim što koriste funkcije za razgradnju koda na podjedinice i čine ga jednostavnijim i čitljivijim, funkcije su korisne i u raznim drugim aplikacijama, uključujući rješavanje problema u stvarnom vremenu, matematičko i statističko računanje.

Kako razvijamo složenije aplikacije na C ++-u, susrećemo se s mnogim zahtjevima tako da moramo koristiti nekoliko posebnih koncepata C ++-a. Rekurzija je jedan takav koncept.

što mogu učiniti s c ++-om

=> Posjetite ovdje za cjelovit popis tutorijala za C ++.

RECURZIJA U C ++

U ovom uputstvu naučit ćemo više o rekurziji, gdje i zašto se koristi zajedno s nekim klasičnim primjerima C ++ koji implementiraju rekurziju.

Što ćete naučiti:

Što je rekurzija?

Rekurzija je proces u kojem se funkcija poziva. Funkcija koja provodi rekurziju ili se sama naziva naziva se rekurzivna funkcija. U rekurziji se rekurzivna funkcija iznova i iznova poziva i nastavlja sve dok se ne ispuni krajnji uvjet.

Slika dolje prikazuje kako funkcionira rekurzija:

Rad rekurzije

Kao što vidimo na gornjem dijagramu, glavna funkcija poziva funkciju, funct (). Funkcija funct () zauzvrat se naziva unutar svoje definicije. Ovako funkcionira rekurzija. Ovaj postupak poziva same funkcije nastavit će se dok ne pružimo završni uvjet zbog kojeg će završiti.

Obično pružamo granu koda dok implementiramo rekurziju, tako da pružamo jedan uvjet koji će pokrenuti rekurziju, a drugi za normalno izvršavanje.

Osnovno stanje rekurzije

Kada se izvrši rekurzija, pruža se rješenje osnovnog slučaja ili završnog slučaja i rješenja većih problema grade se na temelju rješenja manjih problema.

Razmotrimo klasični primjer rekurzije, faktorijev zapis.

Znamo da je matematički faktor broja n:

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

Dakle, faktorijel za n = 3 bit će 3! = 3 × 2!

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

Dakle, programski ovaj izračun možemo izraziti na sljedeći način:

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

Dakle, kao što je gore prikazano, izrazili smo gornji izračun faktora u rekurzivni poziv funkcije. Vidimo da ako je broj n manji ili jednak 1, vratit ćemo 1 umjesto rekurzivnog poziva. To se naziva osnovni uvjet / slučaj za faktorijel koji omogućuje zaustavljanje rekurzije.

Stoga osnovni uvjet u osnovi odlučuje koliko će se puta rekurzivna funkcija sama pozvati. To znači da možemo vrlo dobro izračunati faktorijel većeg broja izražavajući ga manjim brojevima dok se ne postigne osnovna klasa.

Dolje je dat savršen primjer za izračunavanje faktorijela broja:

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

Izlaz:

Unesite broj čiji faktorijel treba izračunati: 10
10! = 3628800

U gornjem primjeru implementiramo rekurziju. Broj čiji faktorijel nalazimo uzimamo iz standardnog ulaza, a zatim ga prosljeđujemo faktorističkoj funkciji.

U faktorijelnoj funkciji dali smo osnovni uvjet kao (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.

Dodjela memorije za rekurzivni poziv

Znamo da se, kada se uputi poziv funkcije, stanje funkcije pozivanja pohranjuje u stog, a kada se poziv funkcije završi, to se stanje vraća natrag, tako da program može nastaviti izvršavanje.

gdje besplatno gledati anime

Kada se izvrši rekurzivni poziv funkcije, stanje ili memorija za pozvanu funkciju dodjeljuju se povrh stanja pozivajuće funkcije i za svaki rekurzivni poziv funkcije izrađuje se različita kopija lokalnih varijabli.

Kada se postigne osnovni uvjet, funkcija se vraća pozivajućoj funkciji, a memorija se razdvaja i postupak se nastavlja.

Preljev stoga u rekurziji

Kada se rekurzija nastavi neograničeno vrijeme, to može rezultirati preljevom stoga.

Kada se rekurzija može nastaviti ovako? Jedna je situacija kada ne odredimo osnovni uvjet. Druga je situacija kada se tijekom izvršavanja programa ne postigne osnovni uvjet.

Na primjer,modificiramo gornji faktorski program i mijenjamo njegovo osnovno stanje.

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

U gornjem kodu promijenili smo osnovni uvjet u (n == 1000). Sada, ako damo broj n = 10, možemo zaključiti da osnovni uvjet nikada neće doseći. Na taj će se način u jednom trenutku iscrpiti memorija na stogu, što će rezultirati preljevom stoga.

Stoga, dok dizajniramo rekurzivne programe, moramo biti oprezni oko osnovnog stanja koje pružamo.

Izravna vs neizravna rekurzija

Do sada smo u rekurziji vidjeli kako se funkcija poziva. Ovo je izravna rekurzija.

Postoji još jedna vrsta rekurzije, tj. Neizravna rekurzija. U ovom slučaju funkcija poziva drugu funkciju, a zatim ova funkcija poziva funkciju pozivanja. Ako su f1 i f2 dvije funkcije. Tada f1 poziva f2, a f2, zauzvrat, poziva f1. Ovo je neizravna rekurzija.

L i mi revidiramo svoj faktorcijski program kako bismo pokazali izravnu rekurziju.

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

Izlaz:

Unesite broj čiji faktorijel treba izračunati: 5
5! = 120

U gornjem primjeru pokazali smo neizravnu rekurziju. Glavna funkcija poziva factorial_a. Factorial_a poziva factorial_b. Zauzvrat factorial_b naziva factorial_a. Vidimo da na izlaz programa to ne utječe.

Reakcija s repom i nerepom

Rekurzivna funkcija s repom je rekurzivna funkcija u kojoj se u funkciji izvršava posljednji poziv.

Na primjer, razmotrite sljedeću funkciju.

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

U gornjem primjeru, zaslon je repna rekurzivna funkcija takva da je zadnji poziv funkcije.

Repne funkcije smatraju se boljima od nerepanih rekurzivnih funkcija, jer ih prevodilac može optimizirati. Razlog je taj što je, budući da je repni rekurzivni poziv posljednji izraz u funkciji, nakon ovog poziva nema koda koji će se izvršiti.

Kao rezultat, spremanje trenutnog okvira steka za funkciju nije potrebno.

Prednosti / slabosti rekurzije zbog iterativnog programiranja

Rekurzivni programi pružaju kompaktan i čist kod. Rekurzivni program jednostavan je način pisanja programa. Postoje neki svojstveni problemi poput faktorijela, Fibonaccijeve sekvence, hanojskih kula, prelaza stabala itd. Koji zahtijevaju rekurziju za rješavanje.

Drugim riječima, oni se učinkovito rješavaju rekurzijom. Oni se također mogu riješiti iterativnim programiranjem pomoću stogova ili drugih struktura podataka, ali postoje šanse da postanu složeniji za implementaciju.

Moći rješavanja problema rekurzivnog i iterativnog programiranja su iste. Međutim, rekurzivni programi zauzimaju više memorijskog prostora jer svi pozivi funkcija trebaju biti pohranjeni u stog dok se ne podudara osnovni slučaj.

Rekurzivne funkcije također imaju vremenske troškove zbog previše poziva funkcija i povratnih vrijednosti.

Primjeri rekurzije

Zatim ćemo implementirati neke od primjera rekurzivnog programiranja.

Fibonaccijeva serija

Fibonaccijev niz je niz koji je dan kao

0 1 1 2 3 5 8 13 ……

Kao što je gore prikazano, prva dva broja Fibonaccijeve serije su 0 i 1. Sljedeći broj u nizu je zbroj prethodna dva broja.

Primijenimo ovu seriju pomoću 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 '<

Izlaz:

Unesite broj elemenata za Fibonaccijevu seriju: 10
Fibonaccijeva serija za 10 brojeva: 0 1 1 2 3 5 8 13 21 34

U ovom primjeru koristili smo rekurzivni poziv za generiranje Fibonaccijeve sekvence. Vidimo da se prva dva broja koja su konstantna izravno ispisuju i za slijedeće brojeve u nizu koristimo rekurzivnu funkciju.

što je tip bin datoteke

Palindrom

Palindromski broj je broj koji je kada se čita u obrnutom smjeru jednak onome koji se čita u smjeru slijeva u desno.

Na primjer, broj 121 dok čita slijeva udesno i zdesna ulijevo čita isto tj. 121. Stoga je 121 palindrom.

Broj 291, kada čita s desna na lijevo, tj. Obrnutim redoslijedom, čita se kao 192. Stoga 291 nije 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 '<

Izlaz:

Unesite broj za provjeru palindrom: 6556
Broj 6556 je palindrom

Snimak zaslona za isti dat je u nastavku.

Rekurzija - Palindrom

U gornjem programu čitamo ulazni broj sa standardnog ulaza. Zatim taj broj prosljeđujemo rekurzivnoj funkciji za preokretanje znamenki broja. Ako su obrnute znamenke i ulazni broj jednaki, onda je broj palindrom.

Zaključak

S ovim smo završili s rekurzijom. U ovom uputstvu proučavali smo rekurzivno programiranje, rekurzivnu funkciju, njene prednosti / nedostatke, zajedno s raznim detaljnim primjerima.

Osim ovih primjera, rekurzija se koristi i u rješavanju nekih standardnih problema poput prijelaza (inorder / preorder / postorder), tornjeva Hanoi, BFS prelaska itd.

=> Posjetite ovdje da biste C ++ naučili od nule.

Preporučena literatura

^