recursion c
Preskúmajte všetko o rekurzii v C ++ s klasickými príkladmi.
V našom predchádzajúcom tutoriáli sme sa dozvedeli viac o funkciách v C ++.
Okrem použitia funkcií na rozdelenie kódu na podjednotky a zjednodušenia a čitateľnosti kódu sú funkcie užitočné aj v rôznych iných aplikáciách vrátane riešenia problémov v reálnom čase, matematických a štatistických výpočtov.
Keď vyvíjame zložitejšie aplikácie v C ++, narazíme na veľa požiadaviek, takže je potrebné dať do používania niekoľko špeciálnych konceptov C ++. Rekurzia je jedným z takýchto konceptov.
=> Úplný zoznam výukových programov C ++ nájdete tu.
V tomto tutoriále sa dozvieme viac o rekurzii, kde a prečo sa používa spolu s niektorými klasickými príkladmi C ++, ktoré implementujú rekurziu.
Čo sa dozviete:
- Čo je to rekurzia?
- Základná podmienka rekurzie
- Alokácia pamäte pre rekurzívne volanie
- Prepad zásobníka v rekurzii
- Priama vs nepriama rekurzia
- Koncová a bezchybná rekurzia
- Klady / zápory rekurzie nad iteračným programovaním
- Príklady rekurzie
- Záver
- Odporúčané čítanie
Čo je to rekurzia?
Rekurzia je proces, pri ktorom sa funkcia nazýva sama. Funkcia, ktorá implementuje rekurziu alebo sa volá, sa nazýva rekurzívna funkcia. Pri rekurzii sa rekurzívna funkcia volá znova a znova a pokračuje ďalej, kým nie je splnená podmienka konca.
Nasledujúci obrázok zobrazuje, ako funguje rekurzia:
Ako vidíme na vyššie uvedenom diagrame, hlavná funkcia nazýva funkciu, funct (). Funkčná funkcia () sa zase nazýva v rámci svojej definície. Takto funguje rekurzia. Tento proces samotného volania funkcie bude pokračovať, kým nezadáme podmienku ukončenia, ktorá ju ukončí.
Zvyčajne poskytujeme vetvu kódu pri implementácii rekurzie tak, že poskytujeme jednu podmienku, ktorá spustí rekurziu, a druhú na vykonávanie normálneho vykonania.
Základná podmienka rekurzie
Keď sa uskutoční rekurzia, poskytne sa riešenie základného prípadu alebo koncového prípadu a riešenia väčších problémov sa zostavia na základe riešení menších problémov.
Uvažujme o klasickom príklade rekurzie, faktoriálnej notácie.
Vieme, že matematicky je faktoriál čísla n:
n! = nxn-1x ... .x0!
vzhľadom na to, že 0! = 1;
Takže faktoriál pre n = 3 bude 3! = 3 × 2!
3! = 3x2x1!
3! = 3x2x2x0!
3! = 3x2x1x1 = 6
Programovo teda môžeme tento výpočet vyjadriť takto:
Windows 10 Predvolená brána nie je k dispozícii
int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); }
Ako je uvedené vyššie, vyjadrili sme vyššie uvedený výpočet faktoriálu do rekurzívneho volania funkcie. Vidíme, že ak je číslo n menšie alebo rovné 1, namiesto rekurzívneho hovoru vrátime 1. Toto sa nazýva základná podmienka / prípad pre faktoriál, ktorý umožňuje zastaviť rekurziu.
Preto základná podmienka v podstate rozhoduje o tom, koľkokrát by sa mala rekurzívna funkcia nazvať. To znamená, že môžeme veľmi dobre vypočítať faktoriál väčšieho čísla vyjadrením v zmysle menších čísel, kým sa nedosiahne základná trieda.
Ďalej je uvedený perfektný príklad na výpočet faktoriálu čísla:
#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< Výkon:
Zadajte číslo, ktorého faktoriál sa má vypočítať: 10
10! = 3628800
Vo vyššie uvedenom príklade implementujeme rekurziu. Vezmeme číslo, ktorého faktoriál treba nájsť zo štandardného vstupu, a potom ho odovzdáme faktoriálnej funkcii.
Vo faktoriálnej funkcii sme dali základnú podmienku ako (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.
Alokácia pamäte pre rekurzívne volanie
Vieme, že keď sa uskutoční volanie funkcie, stav volajúcej funkcie sa uloží do zásobníka a po dokončení volania funkcie sa tento stav obnoví späť, aby program mohol pokračovať vo vykonávaní.
Keď sa uskutoční rekurzívne volanie funkcie, stav alebo pamäť volanej funkcie sa pridelí nad stav volajúcej funkcie a pre každé rekurzívne volanie funkcie sa vytvorí iná kópia miestnych premenných.
Po dosiahnutí základnej podmienky sa funkcia vráti k volajúcej funkcii, pamäť sa zruší a proces pokračuje.
Prepad zásobníka v rekurzii
Keď rekurzia pokračuje neobmedzene dlho, môže to mať za následok pretečenie zásobníka.
Kedy môže rekurzia takto pokračovať? Jedna situácia je, keď neurčíme základnú podmienku. Iná situácia je, keď sa počas vykonávania programu nedosiahne základná podmienka.
Napríklad,upravíme vyššie uvedený faktoriálny program a zmeníme jeho základnú podmienku.
int factorial(int n){ if(n ==1000) return 1; else return n*factorial(n-1); }
Vo vyššie uvedenom kóde sme zmenili základnú podmienku na (n == 1000). Teraz, keď dáme číslo n = 10, môžeme dospieť k záveru, že základná podmienka nikdy nedosiahne. Týmto spôsobom sa v určitom okamihu vyčerpá pamäť na zásobníku, čo povedie k pretečeniu zásobníka.
Preto pri navrhovaní rekurzívnych programov musíme byť opatrní ohľadom základných podmienok, ktoré poskytujeme.
Priama vs nepriama rekurzia
Zatiaľ sme v rekurzii videli, ako sa funkcia volá sama. Toto je priama rekurzia.
Existuje ďalší typ rekurzie, t. J. Nepriama rekurzia. V tomto prípade funkcia volá inú funkciu a potom táto funkcia volá volajúcu funkciu. Ak sú f1 a f2 dve funkcie. Potom f1 zavolá f2 a f2 zase zavolá f1. Toto je nepriama rekurzia.
Ľ zrevidujeme náš faktoriálny program, aby sme demonštrovali priamu rekurziu.
#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< Výkon:
Zadajte číslo, ktorého faktoriál sa má vypočítať: 5
5! = 120
ako vytvoriť falošný e - mail
Vo vyššie uvedenom príklade sme ukázali nepriamu rekurziu. Hlavná funkcia sa volá factororial_a. Factorial_a volá factororial_b. Na druhej strane faktororial_b volá factororial_a. Vidíme, že výstup programu nie je ovplyvnený.
Koncová a bezchybná rekurzia
Koncová rekurzívna funkcia je rekurzívna funkcia, kde sa vo funkcii vykonáva posledné volanie.
Napríklad, zvážte nasledujúcu funkciu.
void display(int n){ if(n<=1) return; cout<<” ”<Vo vyššie uvedenom príklade je displejom sledovaná rekurzívna funkcia, ktorá je posledným volaním funkcie.
Koncové funkcie sú považované za lepšie ako rekurzívne funkcie bez chvosta, pretože ich môže kompilátor optimalizovať. Dôvod je ten, že keďže sledované rekurzívne volanie je posledným príkazom vo funkcii, po tomto volaní nie je možné vykonať žiadny kód.
Vo výsledku nie je potrebné ukladanie aktuálneho rámca zásobníka pre túto funkciu.
Klady / zápory rekurzie nad iteračným programovaním
Rekurzívne programy poskytujú kompaktný a čistý kód. Rekurzívny program je jednoduchý spôsob písania programov. Existuje niekoľko inherentných problémov, ako je faktoriál, Fibonacciho postupnosť, veže Hanoja, prechody stromov atď., Ktoré si na riešenie vyžadujú rekurziu.
Inými slovami, sú efektívne riešené rekurziou. Môžu byť tiež riešené iteračným programovaním pomocou komínov alebo iných dátových štruktúr, ale existuje šanca, že sa ich implementácia stane zložitejšou.
Schopnosti riešenia problémov rekurzívneho aj iteratívneho programovania sú rovnaké. Rekurzívne programy však zaberajú viac miesta v pamäti, pretože všetky volania funkcií musia byť uložené v zásobníku, kým sa nezhoduje základný prípad.
Rekurzívne funkcie majú tiež časovú réžiu kvôli príliš veľkému počtu volaní funkcií a návratových hodnôt.
Príklady rekurzie
Ďalej implementujeme niektoré z príkladov rekurzívneho programovania.
Séria Fibonacci
Fibonacciho séria je postupnosť, ktorá je uvedená ako
0 1 1 2 3 5 8 13 ……
Ako je uvedené vyššie, prvé dve čísla Fibonacciho série sú 0 a 1. Ďalšie číslo v poradí je súčtom predchádzajúcich dvoch čísel.
Implementujme túto sériu pomocou rekurzie.
#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 '< Výkon:
Zadajte počet prvkov pre sériu Fibonacci: 10
Séria Fibonacci pre 10 čísel: 0 1 1 2 3 5 8 13 21 34
V tomto príklade sme použili rekurzívne volanie na vygenerovanie Fibonacciho sekvencie. Vidíme, že prvé dve čísla, ktoré sú konštantné, sú priamo vytlačené a pre ďalšie čísla v poradí používame rekurzívnu funkciu.
Palindróm
Palindrómové číslo je číslo, ktoré je pri čítaní v opačnom smere rovnaké ako pri čítaní zľava doprava.
Napríklad, číslo 121 pri čítaní zľava doprava a sprava doľava číta to isté, t. j. 121. Preto 121 je palindróm.
Číslo 291 má pri čítaní sprava doľava, tj. V opačnom poradí, hodnotu 192. Preto číslo 291 nie je palindróm.
#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 '< Výkon:
Zadajte číslo na kontrolu palindrómu: 6556
Číslo 6556 je palindróm
Screenshot toho istého je uvedený nižšie.
Vo vyššie uvedenom programe načítame vstupné číslo zo štandardného vstupu. Potom odovzdáme toto číslo rekurzívnej funkcii na obrátenie číslic čísla. Ak sú obrátené číslice a vstupné číslo rovnaké, potom je číslom palindróm.
Záver
Týmto sme skončili s rekurziou. V tomto tutoriáli sme sa podrobne zaoberali rekurzívnym programovaním, rekurzívnou funkciou, jej výhodami / nevýhodami a rôznymi príkladmi.
Okrem týchto príkladov sa rekurzia používa aj pri riešení niektorých štandardných problémov, ako sú priechody (inorder / preorder / postorder), veže Hanoja, priechod BFS atď.
=> Navštívte tu a naučte sa C ++ od nuly.
Odporúčané čítanie
- Funkcie priateľov v C ++
- Polymorfizmus v C ++
- Kompletný prehľad jazyka C ++
- Výukový program pre hlavné funkcie Pythonu s praktickými príkladmi
- Výukový program pre Unix Pipes: Rúry v programovaní v Unixe
- Funkcie knižnice v C ++
- 70+ NAJLEPŠÍCH tutoriálov pre C ++ Naučte sa programovanie v C ++ ZADARMO
- Výukový program QTP # 21 - Ako vytvoriť modulárne a opakovane použiteľné testy QTP pomocou knižníc akcií a funkcií