Čo je to rekurzia?
Proces, v ktorom sa funkcia volá priamo alebo nepriamo, sa nazýva rekurzia a zodpovedajúca funkcia sa nazýva rekurzívna funkcia. Pomocou rekurzívneho algoritmu je možné niektoré problémy vyriešiť pomerne jednoducho. Príklady takýchto problémov sú Hanojské veže (TOH) , Inorder/Preorder/Postorder Tree Traversals , DFS of Graph , atď. Rekurzívna funkcia rieši konkrétny problém volaním svojej kópie a riešením menších čiastkových problémov pôvodných problémov. Podľa potreby je možné generovať oveľa viac rekurzívnych hovorov. Je dôležité vedieť, že by sme mali poskytnúť určitý prípad, aby sme ukončili tento proces rekurzie. Môžeme teda povedať, že zakaždým, keď sa funkcia zavolá sama s jednoduchšou verziou pôvodného problému.
Potreba rekurzie
Rekurzia je úžasná technika, pomocou ktorej môžeme skrátiť dĺžku nášho kódu a uľahčiť čítanie a písanie. Má určité výhody oproti technike iterácie, o ktorej sa bude diskutovať neskôr. Úloha, ktorú možno definovať s podobnou podúlohou, rekurzia je pre ňu jedným z najlepších riešení. Napríklad; Faktor čísla.
Vlastnosti rekurzie:
- Vykonávanie rovnakých operácií viackrát s rôznymi vstupmi.
- V každom kroku skúšame menšie vstupy, aby sa problém zmenšil.
- Na zastavenie rekurzie je potrebná základná podmienka, inak dôjde k nekonečnej slučke.
Algoritmus: Kroky
The algorithmic steps for implementing recursion in a function are as follows: Step1 - Define a base case: Identify the simplest case for which the solution is known or trivial. This is the stopping condition for the recursion, as it prevents the function from infinitely calling itself. Step2 - Define a recursive case: Define the problem in terms of smaller subproblems. Break the problem down into smaller versions of itself, and call the function recursively to solve each subproblem. Step3 - Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop. step4 - Combine the solutions: Combine the solutions of the subproblems to solve the original problem.>
Matematická interpretácia
Zoberme si problém, ktorý musí programátor určiť súčet prvých n prirodzených čísel, existuje niekoľko spôsobov, ako to urobiť, ale najjednoduchší prístup je jednoducho sčítať čísla začínajúce od 1 do n. Takže funkcia jednoducho vyzerá takto,
prístup(1) – Jednoduché pridávanie jedného po druhom
f(n) = 1 + 2 + 3 +……..+ n
ale existuje iný matematický prístup, ako to reprezentovať,
prístup(2) – Rekurzívne sčítanie
f(n) = 1 n = 1
f(n) = n + f(n-1) n>1
Medzi prístupom (1) a prístupom (2) je jednoduchý rozdiel a to je in prístup (2) funkcia f( ) sám sa volá vo vnútri funkcie, takže tento jav sa nazýva rekurzia a funkcia obsahujúca rekurziu sa nazýva rekurzívna funkcia, na konci je to skvelý nástroj v rukách programátorov na kódovanie niektorých problémov oveľa jednoduchšie a efektívnejšie spôsobom.
Ako sú rekurzívne funkcie uložené v pamäti?
Rekurzia využíva viac pamäte, pretože rekurzívna funkcia sa pridáva do zásobníka pri každom rekurzívnom volaní a uchováva tam hodnoty, kým sa hovor neskončí. Rekurzívna funkcia využíva štruktúru LIFO (LAST IN FIRST OUT) rovnako ako dátovú štruktúru zásobníka. stack-data-structure/
Aká je základná podmienka v rekurzii?
V rekurzívnom programe sa poskytuje riešenie základného prípadu a riešenie väčšieho problému je vyjadrené v podobe menších problémov.
int fact(int n) { if (n <= 1) // base case return 1; else return n*fact(n-1); }> Vo vyššie uvedenom príklade je definovaný základný prípad pre n <= 1 a väčšiu hodnotu čísla možno vyriešiť prevodom na menšie, kým sa nedosiahne základný prípad.
Ako sa konkrétny problém rieši pomocou rekurzie?
Myšlienkou je reprezentovať problém z hľadiska jedného alebo viacerých menších problémov a pridať jednu alebo viac základných podmienok, ktoré zastavia rekurziu. Napríklad faktoriál n vypočítame, ak poznáme faktoriál (n-1). Základný prípad pre faktoriál by bol n = 0. Vrátime 1, keď n = 0.
Prečo sa pri rekurzii vyskytuje chyba Stack Overflow?
Ak sa nedosiahne základný prípad alebo nie je definovaný, môže nastať problém s pretečením zásobníka. Zoberme si príklad, aby sme to pochopili.
int fact(int n) { // wrong base case (it may cause // stack overflow). if (n == 100) return 1; else return n*fact(n-1); }> Ak sa zavolá fact(10), zavolá fact(9), fact(8), fact(7) a tak ďalej, ale číslo nikdy nedosiahne 100. Základný prípad sa teda nedosiahne. Ak je pamäť vyčerpaná týmito funkciami v zásobníku, spôsobí to chybu pretečenia zásobníka.
Aký je rozdiel medzi priamou a nepriamou rekurziou?
Funkčná zábava sa nazýva priama rekurzívna, ak rovnakú funkciu nazýva zábavou. Funkcia fun sa nazýva nepriama rekurzíva, ak volá inú funkciu, povedzme fun_new a fun_new volá zábavu priamo alebo nepriamo. Rozdiel medzi priamou a nepriamou rekurziou je znázornený v tabuľke 1.
// An example of direct recursion void directRecFun() { // Some code.... directRecFun(); // Some code... } // An example of indirect recursion void indirectRecFun1() { // Some code... indirectRecFun2(); // Some code... } void indirectRecFun2() { // Some code... indirectRecFun1(); // Some code... }> Aký je rozdiel medzi chvostovou a neohraničenou rekurziou?
Rekurzívna funkcia je koncová rekurzívna, keď je rekurzívne volanie poslednou vecou vykonanou funkciou. Prosím odkáž článok o rekurzii chvosta pre podrobnosti.
Ako je pamäť pridelená rôznym volaniam funkcií v rekurzii?
Keď sa z main() volá akákoľvek funkcia, pamäť sa jej pridelí v zásobníku. Rekurzívna funkcia volá sama seba, pamäť pre volanú funkciu je pridelená nad pamäť pridelenú volajúcej funkcii a pre každé volanie funkcie sa vytvorí iná kópia lokálnych premenných. Keď sa dosiahne základný prípad, funkcia vráti svoju hodnotu funkcii, ktorá ju zavolala a pamäť sa de-alokuje a proces pokračuje.
Zoberme si príklad toho, ako funguje rekurzia pomocou jednoduchej funkcie.
CPP
// A C++ program to demonstrate working of> // recursion> #include> using> namespace> std;> > void> printFun(>int> test)> {> >if> (test <1)> >return>;> >else> {> >cout << test <<>' '>;> >printFun(test - 1);>// statement 2> >cout << test <<>' '>;> >return>;> >}> }> > // Driver Code> int> main()> {> >int> test = 3;> >printFun(test);> }> |
>
>
Java
reťazec java zreťaziť
// A Java program to demonstrate working of> // recursion> class> GFG {> >static> void> printFun(>int> test)> >{> >if> (test <>1>)> >return>;> >else> {> >System.out.printf(>'%d '>, test);> >printFun(test ->1>);>// statement 2> >System.out.printf(>'%d '>, test);> >return>;> >}> >}> > >// Driver Code> >public> static> void> main(String[] args)> >{> >int> test =>3>;> >printFun(test);> >}> }> > // This code is contributed by> // Smitha Dinesh Semwal> |
>
>
Python3
# A Python 3 program to> # demonstrate working of> # recursion> > > def> printFun(test):> > >if> (test <>1>):> >return> >else>:> > >print>(test, end>=>' '>)> >printFun(test>->1>)># statement 2> >print>(test, end>=>' '>)> >return> > # Driver Code> test>=> 3> printFun(test)> > # This code is contributed by> # Smitha Dinesh Semwal> |
>
>
C#
// A C# program to demonstrate> // working of recursion> using> System;> > class> GFG {> > >// function to demonstrate> >// working of recursion> >static> void> printFun(>int> test)> >{> >if> (test <1)> >return>;> >else> {> >Console.Write(test +>' '>);> > >// statement 2> >printFun(test - 1);> > >Console.Write(test +>' '>);> >return>;> >}> >}> > >// Driver Code> >public> static> void> Main(String[] args)> >{> >int> test = 3;> >printFun(test);> >}> }> > // This code is contributed by Anshul Aggarwal.> |
>
>
PHP
// PHP program to demonstrate // working of recursion // function to demonstrate // working of recursion function printFun($test) { if ($test <1) return; else { echo('$test '); // statement 2 printFun($test-1); echo('$test '); return; } } // Driver Code $test = 3; printFun($test); // This code is contributed by // Smitha Dinesh Semwal. ?>> |
>
>
Javascript
> > // JavaScript program to demonstrate working of> // recursion> > function> printFun(test)> >{> >if> (test <1)> >return>;> >else> {> >document.write(test +>' '>);> >printFun(test - 1);>// statement 2> >document.write(test +>' '>);> >return>;> >}> >}> > // Driver code> >let test = 3;> >printFun(test);> > > |
>
>Výkon
3 2 1 1 2 3>
Časová zložitosť: O(1)
Pomocný priestor: O(1)
Kedy printFun(3) sa volá z main(), pamäť je pridelená printFun(3) a test lokálnej premennej sa inicializuje na 3 a príkazy 1 až 4 sa vložia do zásobníka, ako je znázornené na obrázku nižšie. Najprv vytlačí „3“. Vo vyhlásení 2 printFun(2) sa volá a pamäť je pridelená printFun(2) a test lokálnej premennej sa inicializuje na 2 a príkazy 1 až 4 sa vložia do zásobníka. podobne, printFun(2) hovory printFun(1) a printFun(1) hovory printFun(0) . printFun(0) prejde na príkaz if a vráti sa do printFun(1) . Zostávajúce vyjadrenia z printFun(1) sú vykonané a vráti sa do printFun(2) a tak ďalej. Vo výstupe sa vytlačia hodnoty od 3 do 1 a potom sa vytlačia 1 až 3. Pamäťový zásobník je znázornený na obrázku nižšie.
Rekurzia VS iterácia
| SR č. | Rekurzia | Iterácia |
| 1) | Ukončí sa, keď sa základný prípad stane pravdou. | Ukončí sa, keď sa podmienka stane nepravdivou. |
| 2) | Používa sa s funkciami. | Používa sa so slučkami. |
| 3) | Každé rekurzívne volanie potrebuje ďalšie miesto v pamäti zásobníka. | Každá iterácia nevyžaduje žiadny ďalší priestor. |
| 4) | Menšia veľkosť kódu. | Väčšia veľkosť kódu. |
Teraz poďme diskutovať o niekoľkých praktických problémoch, ktoré možno vyriešiť pomocou rekurzie a pochopiť jej základné fungovanie. Pre základné pochopenie si prečítajte nasledujúce články.
Základné pochopenie rekurzie.
Problém 1: Napíšte program a rekurentný vzťah na nájdenie Fibonacciho radu n, kde n>2 .
Matematická rovnica:
n if n == 0, n == 1; fib(n) = fib(n-1) + fib(n-2) otherwise;>
Vzťah opakovania:
T(n) = T(n-1) + T(n-2) + O(1)>
Rekurzívny program:
aktualizácia z join sql
Input: n = 5 Output: Fibonacci series of 5 numbers is : 0 1 1 2 3>
Implementácia:
C++
// C++ code to implement Fibonacci series> #include> using> namespace> std;> > // Function for fibonacci> > int> fib(>int> n)> > > // Driver Code> int> main()> {> >// Initialize variable n.> >int> n = 5;> >cout<<>'Fibonacci series of 5 numbers is: '>;> > >// for loop to print the fibonacci series.> >for> (>int> i = 0; i { cout<' '; } return 0; }> |
>
>
C
// C code to implement Fibonacci series> #include> > // Function for fibonacci> int> fib(>int> n)> > >// Stop condition> >if> (n == 0)> >return> 0;> > >// Stop condition> >if> (n == 1> > // Driver Code> int> main()> {> >// Initialize variable n.> >int> n = 5;> >printf>(>'Fibonacci series '> >'of %d numbers is: '>,> >n);> > >// for loop to print the fibonacci series.> >for> (>int> i = 0; i printf('%d ', fib(i)); } return 0; }> |
>
>
Java
// Java code to implement Fibonacci series> import> java.util.*;> > class> GFG> {> > // Function for fibonacci> static> int> fib(>int> n)> > > // Driver Code> public> static> void> main(String []args)> {> > >// Initialize variable n.> >int> n =>5>;> >System.out.print(>'Fibonacci series of 5 numbers is: '>);> > >// for loop to print the fibonacci series.> >for> (>int> i =>0>; i { System.out.print(fib(i)+' '); } } } // This code is contributed by rutvik_56.> |
>
>
Python3
# Python code to implement Fibonacci series> > # Function for fibonacci> def> fib(n):> > ># Stop condition> >if> (n>=>=> 0>):> >return> 0> > ># Stop condition> >if> (n>=>=> 1> or> n>=>=> 2>):> >return> 1> > ># Recursion function> >else>:> >return> (fib(n>-> 1>)>+> fib(n>-> 2>))> > > # Driver Code> > # Initialize variable n.> n>=> 5>;> print>(>'Fibonacci series of 5 numbers is :'>,end>=>' '>)> > # for loop to print the fibonacci series.> for> i>in> range>(>0>,n):> >print>(fib(i),end>=>' '>)> |
>
>
C#
using> System;> > public> class> GFG> {> > >// Function for fibonacci> >static> int> fib(>int> n)> > n == 2)> >return> 1;> > >// Recursion function> >else> >return> (fib(n - 1) + fib(n - 2));> >> > >// Driver Code> >static> public> void> Main ()> >{> > >// Initialize variable n.> >int> n = 5;> >Console.Write(>'Fibonacci series of 5 numbers is: '>);> > >// for loop to print the fibonacci series.> >for> (>int> i = 0; i { Console.Write(fib(i) + ' '); } } } // This code is contributed by avanitrachhadiya2155> |
>
>
Javascript
> // JavaScript code to implement Fibonacci series> > // Function for fibonacci> function> fib(n)> n == 2)> >return> 1;> >// Recursion function> >else> >return> fib(n-1) + fib(n-2);> > > // Initialize variable n.> let n = 5;> > document.write(>'Fibonacci series of 5 numbers is: '>);> > // for loop to print the fibonacci series.> for>(let i = 0; i { document.write(fib(i) + ' '); }> |
>
>Výkon
Fibonacci series of 5 numbers is: 0 1 1 2 3>
Časová zložitosť: O(2n)
Pomocný priestor: O(n)
Tu je rekurzívny strom pre vstup 5, ktorý ukazuje jasný obraz toho, ako možno veľký problém vyriešiť na menšie.
fib(n) je Fibonacciho funkcia. Časová náročnosť daného programu môže závisieť od volania funkcie.
fib(n) -> úroveň CBT (UB) -> 2^n-1 uzlov -> 2^n volanie funkcie -> 2^n*O(1) -> T(n) = O(2^n)
Pre najlepší prípad.
T(n) = ?(2^n2)>
pracuje:
Problém 2: Napíšte program a rekurentný vzťah na nájdenie faktoriálu n, kde n>2.
Matematická rovnica:
1 if n == 0 or n == 1; f(n) = n*f(n-1) if n>1;>
Vzťah opakovania:
T(n) = 1 for n = 0 T(n) = 1 + T(n-1) for n>0>
Rekurzívny program:
Vstup: n = 5
Výkon:
faktoriál 5 je: 120
Implementácia:
C++
// C++ code to implement factorial> #include> using> namespace> std;> > // Factorial function> int> f(>int> n)> n == 1)> >return> 1;> > >// Recursive condition> >else> >return> n * f(n - 1);> > > // Driver code> int> main()> {> >int> n = 5;> >cout<<>'factorial of '><' is: '< return 0; }> |
>
pridanie java do poľa
>
C
// C code to implement factorial> #include> > // Factorial function> int> f(>int> n)> > >// Stop condition> >if> (n == 0> > // Driver code> int> main()> {> >int> n = 5;> >printf>(>'factorial of %d is: %d'>, n, f(n));> >return> 0;> }> |
>
>
Java
// Java code to implement factorial> public> class> GFG> {> > >// Factorial function> >static> int> f(>int> n)> >> > >// Driver code> >public> static> void> main(String[] args)> >{> >int> n =>5>;> >System.out.println(>'factorial of '> + n +>' is: '> + f(n));> >}> }> > // This code is contributed by divyesh072019.> |
>
>
Python3
# Python3 code to implement factorial> > # Factorial function> def> f(n):> > ># Stop condition> >if> (n>=>=> 0> or> n>=>=> 1>):> >return> 1>;> > ># Recursive condition> >else>:> >return> n>*> f(n>-> 1>);> > > # Driver code> if> __name__>=>=>'__main__'>:> > >n>=> 5>;> >print>(>'factorial of'>,n,>'is:'>,f(n))> > ># This code is contributed by pratham76.> |
>
>
C#
// C# code to implement factorial> using> System;> class> GFG {> > >// Factorial function> >static> int> f(>int> n)> > n == 1)> >return> 1;> > >// Recursive condition> >else> >return> n * f(n - 1);> >> > >// Driver code> >static> void> Main()> >{> >int> n = 5;> >Console.WriteLine(>'factorial of '> + n +>' is: '> + f(n));> >}> }> > // This code is contributed by divyeshrabadiya07.> |
>
>
Javascript
> // JavaScript code to implement factorial> > // Factorial function> function> f(n)> n == 1)> >return> 1;> > >// Recursive condition> >else> >return> n*f(n-1);> > > // Initialize variable n.> let n = 5;> document.write(>'factorial of '>+ n +>' is: '> + f(n));> > // This code is contributed by probinsah.> > |
>
>Výkon
factorial of 5 is: 120>
Časová zložitosť: O(n)
Pomocný priestor: O(n)
pracuje:
Schéma faktoriálnej funkcie rekurzie pre vstup používateľa 5.
Príklad: Reálne aplikácie rekurzie v reálnych problémoch
Rekurzia je výkonná technika, ktorá má mnoho aplikácií v informatike a programovaní. Tu sú niektoré z bežných aplikácií rekurzie:
- Prechádzanie stromami a grafmi: Rekurzia sa často používa na prechádzanie a vyhľadávanie dátových štruktúr, ako sú stromy a grafy. Rekurzívne algoritmy možno použiť na systematické preskúmanie všetkých uzlov alebo vrcholov stromu alebo grafu. Algoritmy triedenia: Rekurzívne algoritmy sa používajú aj v algoritmoch triedenia, ako je rýchle triedenie a triedenie zlúčením. Tieto algoritmy používajú rekurziu na rozdelenie údajov do menších podpolí alebo podzoznamov, ich triedenie a následné zlúčenie. Algoritmy rozdeľuj a panuj : Mnoho algoritmov, ktoré používajú prístup rozdeľuj a panuj, ako napríklad algoritmus binárneho vyhľadávania, používa rekurziu na rozdelenie problému na menšie čiastkové problémy. Generovanie fraktálov: Fraktálne tvary a vzory možno generovať pomocou rekurzívnych algoritmov. Napríklad Mandelbrotova množina sa generuje opakovaným aplikovaním rekurzívneho vzorca na komplexné čísla. Algoritmy spätného sledovania: Algoritmy spätného sledovania sa používajú na riešenie problémov, ktoré zahŕňajú postupnosť rozhodnutí, pričom každé rozhodnutie závisí od predchádzajúcich. Tieto algoritmy je možné implementovať pomocou rekurzie na preskúmanie všetkých možných ciest a spätného chodu, keď sa nenájde riešenie. Zapamätanie: Zapamätanie je technika, ktorá zahŕňa ukladanie výsledkov drahých volaní funkcií a vrátenie výsledku uloženého vo vyrovnávacej pamäti, keď sa znova vyskytnú rovnaké vstupy. Memoizácia môže byť implementovaná pomocou rekurzívnych funkcií na výpočet a cacheovanie výsledkov čiastkových problémov.
Toto je len niekoľko príkladov z mnohých aplikácií rekurzie v informatike a programovaní. Rekurzia je všestranný a výkonný nástroj, ktorý možno použiť na riešenie mnohých rôznych typov problémov.
Vysvetlenie: jeden skutočný príklad rekurzie:
Rekurzia je programovacia technika, ktorá zahŕňa volanie samotnej funkcie. Môže to byť výkonný nástroj na riešenie zložitých problémov, ale vyžaduje si aj starostlivú implementáciu, aby sa predišlo nekonečným slučkám a pretečeniu zásobníka.
Tu je príklad implementácie rekurzie v Pythone:
C++
#include> using> namespace> std;> int> factorial(>int> n)> {> > >// Base case: if n is 0 or 1, return 1> >if> (n == 0 || n == 1) {> >return> 1;> >}> > >// Recursive case: if n is greater than 1,> >// call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n - 1);> >}> }> > int> main()> {> > >// Call the factorial function and print the result> >int> result = factorial(5);> >cout << result |
>
>
Java
ako vrátiť pole v jave
import> java.util.*;> > class> Main {> >public> static> int> factorial(>int> n)> >{> >// Base case: if n is 0 or 1, return 1> >if> (n ==>0> || n ==>1>) {> >return> 1>;> >}> > >// Recursive case: if n is greater than 1,> >// call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n ->1>);> >}> >}> > >public> static> void> main(String[] args)> >{> >// Call the factorial function and print the result> >int> result = factorial(>5>);> >System.out.println(result);>// Output: 120> >}> }> |
>
>
Python3
def> factorial(n):> ># Base case: if n is 0 or 1, return 1> >if> n>=>=> 0> or> n>=>=> 1>:> >return> 1> > ># Recursive case: if n is greater than 1, call the function with n-1 and multiply by n> >else>:> >return> n>*> factorial(n>->1>)> > # Call the factorial function and print the result> result>=> factorial(>5>)> print>(result)># Output: 120> |
>
>
C#
using> System;> > class> MainClass {> >public> static> int> factorial(>int> n)> >{> >// Base case: if n is 0 or 1, return 1> >if> (n == 0 || n == 1) {> >return> 1;> >}> > >// Recursive case: if n is greater than 1,> >// call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n - 1);> >}> >}> > >public> static> void> Main (>string>[] args) {> >// Call the factorial function and print the result> >int> result = factorial(5);> >Console.WriteLine(result);>// Output: 120> >}> }> |
>
>
Javascript
function> factorial(n) {> >// Base case: if n is 0 or 1, return 1> >if> (n === 0 || n === 1) {> >return> 1;> >}> > >// Recursive case: if n is greater than 1, call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n - 1);> >}> }> > // Call the factorial function and print the result> const result = factorial(5);> console.log(result);>// Output: 120> |
>
>Výkon
120>
V tomto príklade definujeme funkciu nazvanú faktoriál, ktorá berie ako vstup celé číslo n. Funkcia používa rekurziu na výpočet faktoriálu n (t. j. súčinu všetkých kladných celých čísel až do n).
Faktoriálna funkcia najprv skontroluje, či n je 0 alebo 1, čo sú základné prípady. Ak n je 0 alebo 1, funkcia vráti 1, pretože 0! a 1! obaja sú 1.
Ak je n väčšie ako 1, funkcia vstupuje do rekurzívneho prípadu. Volá sa s n-1 ako argument a vynásobí výsledok číslom n. Toto vypočíta n! rekurzívnym výpočtom (n-1)!.
Je dôležité poznamenať, že rekurzia môže byť neefektívna a viesť k pretečeniu zásobníka, ak sa nepoužíva opatrne. Každé volanie funkcie pridá do zásobníka volaní nový rámec, čo môže spôsobiť, že zásobník bude príliš veľký, ak je rekurzia príliš hlboká. Okrem toho môže rekurzia sťažiť pochopenie a ladenie kódu, pretože vyžaduje premýšľanie o viacerých úrovniach volaní funkcií.
Rekurzia však môže byť tiež účinným nástrojom na riešenie zložitých problémov, najmä tých, ktoré zahŕňajú rozdelenie problému na menšie podproblémy. Pri správnom použití môže rekurzia urobiť kód elegantnejším a ľahšie čitateľným.
Aké sú nevýhody rekurzívneho programovania oproti iteratívnemu programovaniu?
Všimnite si, že rekurzívne aj iteračné programy majú rovnaké schopnosti riešiť problémy, t.j. každý rekurzívny program možno písať iteračne a platí to aj naopak. Rekurzívny program má väčšie nároky na priestor ako iteračný program, pretože všetky funkcie zostanú v zásobníku, kým sa nedosiahne základný prípad. Má tiež väčšie časové požiadavky kvôli volaniam funkcií a vráteniu réžie.
Navyše, kvôli menšej dĺžke kódu sú kódy ťažko pochopiteľné, a preto je potrebné pri písaní kódu venovať zvýšenú pozornosť. Ak rekurzívne volania nie sú správne skontrolované, môže dôjsť k nedostatku pamäte.
Aké sú výhody rekurzívneho programovania oproti iteratívnemu programovaniu?
Rekurzia poskytuje čistý a jednoduchý spôsob písania kódu. Niektoré problémy sú vo svojej podstate rekurzívne, ako napríklad prechody cez stromy, Hanojská veža , atď. Pre takéto problémy je výhodné písať rekurzívny kód. Takéto kódy môžeme písať aj iteračne pomocou zásobníkovej dátovej štruktúry. Napríklad pozri Inorder Tree Traversal bez rekurzie, Iterative Tower of Hanoi.
Zhrnutie rekurzie:
- V rekurzii existujú dva typy prípadov, t. j. rekurzívny prípad a základný prípad.
- Základný prípad sa používa na ukončenie rekurzívnej funkcie, keď sa prípad ukáže ako pravdivý.
- Každé rekurzívne volanie vytvorí novú kópiu tejto metódy v pamäti zásobníka.
- Nekonečná rekurzia môže viesť k nedostatku pamäte zásobníka.
- Príklady rekurzívnych algoritmov: Merge Sort, Quick Sort, Tower of Hanoi, Fibonacci Series, Factorial Problem, atď.
Cvičné problémy založené na výstupe pre začiatočníkov:
Cvičné otázky pre rekurziu | Set 1
Cvičné otázky pre rekurziu | Súprava 2
Cvičné otázky pre rekurziu | Súprava 3
Cvičné otázky pre rekurziu | Súprava 4
Cvičné otázky pre rekurziu | Set 5
Cvičné otázky pre rekurziu | Súprava 6
Cvičné otázky pre rekurziu | Súprava 7
Kvíz o rekurzii
Prax kódovania pri rekurzii:
Všetky články o rekurzii
Problémy s rekurzívnou praxou s riešeniami