recursion c
Prozkoumejte vše o rekurzi v C ++ s klasickými příklady.
V našem předchozím tutoriálu jsme se dozvěděli více o funkcích v C ++.
Kromě použití funkcí pro rozdělení kódu na podjednotky a zjednodušení a přečtení kódu jsou funkce užitečné v různých dalších aplikacích, včetně řešení problémů v reálném čase, matematických a statistických výpočtů.
Jak vyvíjíme složitější aplikace v C ++, narazíme na mnoho požadavků, takže musíme použít několik speciálních konceptů C ++. Rekurze je jeden takový koncept.
=> Úplný seznam výukových programů C ++ naleznete zde.
V tomto kurzu se dozvíme více o rekurzi, kde a proč se používá spolu s některými klasickými příklady C ++, které implementují rekurzi.
Co se naučíte:
- Co je rekurze?
- Rekurzivní základní podmínka
- Přidělení paměti pro rekurzivní volání
- Přetečení zásobníku v rekurzi
- Direct Vs nepřímá rekurze
- Ocasní a bezocasá rekurze
- Klady / zápory rekurze nad iteračním programováním
- Příklady rekurze
- Závěr
- Doporučené čtení
Co je rekurze?
Rekurze je proces, při kterém se funkce sama volá. Funkce, která implementuje rekurzi nebo se sama volá, se nazývá rekurzivní funkce. V rekurzi se rekurzivní funkce volá znovu a znovu a pokračuje, dokud není splněna koncová podmínka.
Níže uvedený obrázek ukazuje, jak funguje rekurze:
Jak vidíme ve výše uvedeném diagramu, hlavní funkce volá funkci, funct (). Funkce funct () se zase nazývá uvnitř své definice. Takto funguje rekurze. Tento proces samotného volání funkce bude pokračovat, dokud nezadáme podmínku ukončení, která ji ukončí.
Obvykle poskytujeme větev kódu při implementaci rekurze tak, že poskytneme jednu podmínku, která aktivuje rekurzi, a další k provedení normálního provedení.
Rekurzivní základní podmínka
Když je provedena rekurze, je poskytnuto řešení základního případu nebo koncového případu a řešení větších problémů je postaveno na základě řešení menších problémů.
Uvažujme klasický příklad rekurze, faktoriální notace.
Víme, že matematicky je faktoriál čísla n:
n! = nxn-1x ... .x0!
vzhledem k tomu, že 0! = 1;
Takže faktoriál pro n = 3 bude 3! = 3 × 2!
3! = 3x2x1!
3! = 3x2x2x0!
3! = 3x2x1x1 = 6
Takže programově můžeme tento výpočet vyjádřit takto:
int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); }
Tak, jak je uvedeno výše, jsme vyjádřili výše uvedený výpočet faktoriálu do rekurzivního volání funkce. Vidíme, že pokud je číslo n menší nebo rovno 1, vrátíme 1 místo rekurzivního volání. Tomu se říká základní podmínka / případ pro faktoriál, který umožňuje zastavení rekurze.
Základní podmínka tedy v zásadě rozhoduje o tom, kolikrát by se rekurzivní funkce měla sama nazývat. To znamená, že můžeme velmi dobře vypočítat faktoriál většího čísla jeho vyjádřením v podobě menších čísel, dokud není dosaženo základní třídy.
Níže je uveden dokonalý příklad pro 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ýstup:
Zadejte číslo, jehož faktoriál se má vypočítat: 10
10! = 3628800
Ve výše uvedeném příkladu implementujeme rekurzi. Vezmeme číslo, jehož faktoriál se nachází ze standardního vstupu, a poté ho předáme faktorové funkci.
Ve faktoriální funkci jsme dali základní podmínku jako (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.
Přidělení paměti pro rekurzivní volání
Víme, že když se provede volání funkce, stav volající funkce se uloží do zásobníku a po dokončení volání funkce se tento stav obnoví zpět, aby program mohl pokračovat v provádění.
Když je provedeno volání rekurzivní funkce, stav nebo paměť volané funkce je přidělena nad stav volající funkce a pro každé rekurzivní volání funkce je vytvořena jiná kopie místních proměnných.
Když je dosaženo základní podmínky, funkce se vrátí do volající funkce a paměť je uvolněna a proces pokračuje.
Přetečení zásobníku v rekurzi
Když rekurze pokračuje po neomezenou dobu, může to vést k přetečení zásobníku.
Kdy může rekurze takto pokračovat? Jedna situace je, když nezadáme základní podmínku. Další situace je, když není při provádění programu dosaženo základní podmínky.
Například,upravíme výše uvedený faktoriální program a změníme jeho základní podmínku.
int factorial(int n){ if(n ==1000) return 1; else return n*factorial(n-1); }
Ve výše uvedeném kódu jsme změnili základní podmínku na (n == 1000). Nyní, když dáme číslo n = 10, můžeme dojít k závěru, že základní podmínka nikdy nedosáhne. Tímto způsobem se v určitém okamžiku vyčerpá paměť na zásobníku, což povede k přetečení zásobníku.
Proto při navrhování rekurzivních programů musíme dávat pozor na základní podmínku, kterou poskytujeme.
Direct Vs nepřímá rekurze
Zatím v rekurzi jsme viděli, jak se funkce volá sama. Toto je přímá rekurze.
Existuje další typ rekurze, tj. Nepřímá rekurze. V tomto případě funkce volá jinou funkci a poté tato funkce volá funkci volání. Pokud jsou f1 a f2 dvě funkce. Potom f1 volá f2 a f2 zase volá f1. Toto je nepřímá rekurze.
L přezkoumáme náš faktoriální program, abychom demonstrovali přímou rekurzi.
#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ýstup:
Zadejte číslo, jehož faktoriál se má vypočítat: 5
5! = 120
Ve výše uvedeném příkladu jsme ukázali nepřímou rekurzi. Hlavní funkce volá factororial_a. Factorial_a volá factororial_b. Na druhé straně faktororial_b volá factororial_a. Vidíme, že výstup programu není ovlivněn.
Ocasní a bezocasá rekurze
Ocasní rekurzivní funkce je rekurzivní funkce, kde je poslední volání provedeno ve funkci.
Například, zvažte následující funkci.
void display(int n){ if(n<=1) return; cout<<” ”<Ve výše uvedeném příkladu je na displeji ocasní rekurzivní funkce, takže se jedná o poslední volání funkce.
Koncové funkce jsou považovány za lepší než rekurzivní funkce bez ocasu, protože je lze optimalizovat kompilátorem. Důvodem je to, že vzhledem k tomu, že ocasové rekurzivní volání je posledním příkazem ve funkci, není po tomto volání třeba provádět žádný kód.
Výsledkem je, že uložení aktuálního rámce zásobníku pro funkci není nutné.
Klady / zápory rekurze nad iteračním programováním
Rekurzivní programy poskytují kompaktní a čistý kód. Rekurzivní program je jednoduchý způsob psaní programů. Existují některé inherentní problémy, jako je faktoriál, Fibonacciho posloupnost, věže Hanoje, procházení stromů atd., Které pro řešení vyžadují rekurzi.
Jinými slovy, jsou efektivně řešeny rekurzí. Mohou být také vyřešeny iterativním programováním pomocí zásobníků nebo jiných datových struktur, ale existuje šance, že se jejich implementace stane složitější.
Pravomoc řešit problémy rekurzivního i iterativního programování je stejná. Rekurzivní programy však zabírají více místa v paměti, protože všechna volání funkcí musí být uložena v zásobníku, dokud se neshoduje základní případ.
Rekurzivní funkce mají také časovou režii z důvodu příliš mnoha volání funkcí a návratových hodnot.
Příklady rekurze
Dále implementujeme některé z příkladů rekurzivního programování.
Fibonacciho série
Fibonacciho řada je sekvence, která je uvedena jako
0 1 1 2 3 5 8 13 ……
Jak je uvedeno výše, první dvě čísla Fibonacciho řady jsou 0 a 1. Další číslo v pořadí je součtem předchozích dvou čísel.
Implementujme tuto sérii pomocí rekurze.
#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ýstup:
Zadejte počet prvků pro sérii Fibonacci: 10
Série Fibonacci pro 10 čísel: 0 1 1 2 3 5 8 13 21 34
V tomto příkladu jsme použili rekurzivní volání ke generování Fibonacciho sekvence. Vidíme, že první dvě čísla, která jsou konstantní, jsou přímo vytištěna a pro další čísla v pořadí používáme rekurzivní funkci.
Palindrom
Palindromové číslo je číslo, které při čtení v opačném směru je stejné jako při čtení zleva doprava.
Například, číslo 121 při čtení zleva doprava a zprava doleva čte totéž, tj. 121. Proto 121 je palindrom.
Číslo 291 při čtení zprava doleva, tj. V opačném pořadí, zní jako 192. Proto 291 není palindrom.
bezplatné anime stránky ke sledování online
#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ýstup:
Zadejte číslo pro kontrolu palindromu: 6556
Číslo 6556 je palindrom
Screenshot pro stejný je uveden níže.
Ve výše uvedeném programu čteme číslo vstupu ze standardního vstupu. Poté předáme toto číslo rekurzivní funkci, abychom obrátili číslice čísla. Pokud jsou obrácené číslice a vstupní číslo stejné, pak je číslo palindrom.
Závěr
Tím jsme rekurzi skončili. V tomto tutoriálu jsme studovali rekurzivní programování, rekurzivní funkci, její výhody / nevýhody, spolu s různými příklady podrobně.
Kromě těchto příkladů se rekurze používá také při řešení některých standardních problémů, jako jsou traversals (inorder / preorder / postorder), věže Hanoje, BFS traversal atd.
=> Navštivte zde a dozvíte se C ++ od nuly.
Doporučené čtení
- Funkce přátel v C ++
- Polymorfismus v C ++
- Kompletní přehled C ++
- Výukový program pro hlavní funkce Pythonu s praktickými příklady
- Výukový program pro Unix Pipes: Pipes v programování Unixu
- Funkce knihovny v C ++
- 70+ NEJLEPŠÍCH C ++ návodů, jak se naučit programování v C ++ ZDARMA
- Výukový program QTP č. 21 - Jak vytvořit modulární a opakovaně použitelné testy QTP pomocí knihoven akcí a funkcí