Čo je rekurzívna funkcia?
Funkcia sa volá znova a znova, kým nespĺňa rekurzívnu podmienku. Funkcia rekurzie rozdeľuje problém na menšie problémy a volá svoju vlastnú logiku, aby vyriešila menší problém. Táto technika je známa ako rozdelenie a dobitie. Používa sa v oblasti matematiky a informatiky.
Rekurzívna funkcia zahŕňa základný prípad (alebo terminálový prípad) a rekurzívny prípad. V základnom prípade môžete zvážiť hlavný problém, ktorý je potrebné vyriešiť, a rekurzívny prípad rozdelí problém na menšie časti, až kým nedosiahne úroveň, kde sa dá ľahko vyriešiť. Rekurzívny prípad môže vrátiť výsledok alebo sa môže znova nazvať, aby sa problém ďalej rozdelil. Zakaždým, keď sa problém rozdelí na menší problém, funkcia, ktorá sa nazýva rekurzívne, uloží stav hovoru a po jeho odstránení očakáva výsledok sám od seba.
Rekurzívna funkcia v Pythone
Pojem rekurzia zostáva v Pythone rovnaký. Táto funkcia sa nazýva rozdelenie problému na menšie problémy. Najjednoduchším príkladom, ktorý by sme si mohli myslieť na rekurziu, by bolo nájsť faktoriál čísla.
Povedzme, že musíme nájsť faktoriál čísla 5 => 5! (Náš problém)
Nájdite 5! problém možno rozdeliť na menšie 5! => 5 x 4!
Takže, dostať 5! Musíme nájsť 4! a vynásobte ho 5.
Pokračujme v rozdelení problému
5! = 4! x 5
4! = 3! x 4
3! = 3 x 2!
2! = 2 x 1!
1! = 1
Keď dosiahne najmenší kus, tj získame faktoriál 1, môžeme výsledok vrátiť ako
Vezmime si príklad s pseudokódom: -
Algoritmus pre faktoriál
Pozrime sa na algoritmus pre faktoriál:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Hovory funkcií
Predpokladajme, že nachádzame faktoriál 5.
get_factorial(5) 5 * get_factorial(4) = returns 120 #1st call
get_factorial(4) 4 * get_factorial(3) = returns 24 #2nd call
get_factorial(3) 3 * get_factorial(2) = returns 6 #3rd call
get_factorial(2) 2 * get_factorial(1) = returns 2 #4th call
get_factorial(1) returns 1 #5th call
Konečným výsledkom bude 120, kde sme začali vykonávať funkciu. Naša funkcia rekurzie sa zastaví, keď sa počet zníži tak, že sa dá získať výsledok.
- Prvý hovor, ktorý získa faktoriál 5, bude mať za následok rekurzívny stav, keď sa pridá do zásobníka a ďalší hovor sa uskutoční po znížení čísla na 4.
- Táto rekurzia bude pokračovať v volaní a rozdelení problému na menšie kúsky, až kým nedosiahne základné podmienky.
- Základná podmienka je, keď je číslo 1.
- Každá rekurzívna funkcia má svoj vlastný rekurzívny stav a základný stav.
Výhody a nevýhody rekurzívnej funkcie Pythonu
- Vykonanie rekurzie je také, že nebude robiť žiadne výpočty, kým nedosiahne základné podmienky.
- Pri dosahovaní základných podmienok môže dôjs nedostatok pamäte.
- Vo veľkom probléme, kde môže byť milión krokov alebo môžeme povedať, že milión rekurzií na vykonanie programu by mohol skončiť chybou pamäte alebo segmentáciou.
- 1000000! = 1000000 * 999999! =?
- Rekurzia je iná ako iteračná metóda, ktorá sa nezväčšuje ako iteračná metóda.
- Rôzne jazyky majú rôzne optimalizácie pre rekurziu.
- V mnohých jazykoch by iteračná metóda fungovala lepšie ako rekurzia.
- Každý jazyk má určité obmedzenia týkajúce sa hĺbky rekurzie, s ktorou sa môžete stretnúť pri riešení veľkých problémov.
- Niekedy je ťažké pochopiť zložité problémy s rekurziou, zatiaľ čo pri iterácii je to celkom jednoduché.
Niektorí profesionáli
- V niektorých prípadoch je rekurzia pohodlným a rýchlejším spôsobom použitia.
- Veľmi užitočné pri priechode stromom a binárnom vyhľadávaní.
Pythonov kód - Rekurzia verzus Iterácia
Pochopili sme, čo je rekurzia a ako to funguje v Pythone, pretože vieme, že všetky jazyky majú rozdielnu implementáciu rekurzie pre optimalizáciu pamäte a výpočty. Môže sa stať, že iterácia bude rýchlejšia ako rekurzia.
Tu by sme porovnali rekurznú aj iteračnú metódu, aby sme zistili, ako Python v oboch prípadoch funguje.
1. Kód rekurzie pre Factorial
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2: #base condition
return 1
else:
return n * get_recursive_factorial(n -1) #recursion condition
2. Faktorový problém využívajúci iteráciu (opakovanie)
def get_iterative_factorial(n):
if n < 0:
return -1
else:
fact = 1
for i in range( 1, n+1 ):
fact *= i
return fact
3. Výsledky tlače
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
Výkon:
Ako vidíme, obidve dávajú rovnaký výstup, ako sme napísali rovnakú logiku. Tu nevidíme žiadny rozdiel vo vykonávaní.
Pridajme nejaký časový kód, aby sme získali viac informácií o vykonaní rekurzie a iterácie v Pythone.
Importujeme knižnicu „času“ a skontrolujeme, akú časovú rekurziu a iteráciu je potrebné na vrátenie výsledku.
4. Kód s výpočtom času
import time
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2:
return 1
else:
return n * get_recursive_factorial(n-1)
def get_iterative_factorial(n):
if n < 0 :
return -1
else:
fact = 1
for i in range(1, n+1):
fact *= i
return fact
start_time = time.time()
get_recursive_factorial(100)
print("Recursion--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
get_iterative_factorial(100)
print("Iteration--- %s seconds ---" % (time.time() - start_time))
Urobíme opakované popravy s inou hodnotou pre faktoriál a uvidíme výsledky. Nižšie uvedené výsledky sa môžu v jednotlivých strojoch líšiť. Použili sme MacBook Pro 16 GB RAM i7.
Na vykonávanie používame Python 3.7
Prípad 1: - Factorial of 6:
Prípad 2: Faktor 50:
Prípad 3: Faktor 100:
Prípad 4: Faktor 500:
Prípad 5: Factorial 1000:
Analyzovali sme obe metódy v inom probléme. Okrem toho obidve s výnimkou prípadu 4 dosiahli podobné výsledky.
V prípade 5 sme pri rekurzii dostali chybu.
Python dostal obmedzenie maximálnej hĺbky, ktorú môžete dosiahnuť rekurziou, ale ten istý problém som bol schopný vyriešiť iteráciou.
Python má obmedzenia proti problému pretečenia. Python nie je optimalizovaný na rekurziu chvosta a nekontrolovaná rekurzia spôsobuje pretečenie zásobníka.
Funkcia sys.getrecursionlimit () vám oznámi limit rekurzie.
Limit rekurzie sa dá zmeniť, ale neodporúča sa, že by to mohlo byť nebezpečné.
Záver - Rekurzívna funkcia Pythonu
- Rekurzia je užitočným riešením pre niektoré problémy, ako je stromový strom a iné problémy.
- Python nie je funkčný programovací jazyk a vidíme, že rekurzný zásobník nie je v porovnaní s iteráciou optimalizovaný.
- V našom algoritme by sme mali použiť iteráciu, pretože je v Pythone optimalizovaná a poskytuje vám lepšiu rýchlosť.
Odporúčané články
Toto je sprievodca rekurzívnymi funkciami v Pythone. Tu diskutujeme o tom, čo je rekurzívna funkcia, rekurzívna funkcia v Pythone, algoritmus pre faktoriál atď. Ak sa chcete dozvedieť viac, môžete si tiež prečítať naše ďalšie navrhované články -
- Factorial v Pythone
- Príkazy Spark Shell
- Najlepšie kompilátory C.
- Druhy algoritmov
- Faktorský program v JavaScripte
- Sprievodca zoznamom príkazov shellu Unix
- Druhy formulárov v reakcii s príkladmi