Jednoduchými slovami, rekurzia je spôsob riešenia problému tak, že sa funkcia volá sama, slovo „ rekurzívny „Pochádza z latinského slovesa“ opakovať ”, Čo znamená niečo prerobiť. To je to, čo robí rekurzívna funkcia, znova a znova opakuje to isté, to znamená, že sa sama pripomína. V tomto článku sa dozvieme o rekurzii v pythone. Nasledujúce témy sú predmetom tohto blogu:
- Čo je to rekurzia v Pythone?
- Podmienka ukončenia
- Limit rekurzie Pythonu
- Sploštenie zoznamov s rekurziou
- Výhody rekurzie
- Nevýhody rekurzie
Čo je to rekurzia v Pythone?
Rekurzia je proces určovania niečoho z hľadiska samého seba. Vieme, že v Pythone môže každá funkcia volať ktorúkoľvek inú funkciu, funkcia sa môže nazývať aj sama. Tieto typy funkcií, ktoré sa volajú, kým nie je splnená určitá podmienka, sa označujú ako rekurzívne funkcie.
Zoberme si niekoľko príkladov, aby sme videli, ako to funguje. Ak dostanete kladné celé číslo, faktoriál by bol.
- n! = n * (n-1) * (n-2) a tak ďalej.
- 2! = 2 * (2-1)
- jeden! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Nahradením vyššie uvedených hodnôt vznikne nasledujúci výraz
- 4! = 4 * 3 * 2 * 1
Musíme definovať funkciu, povedzme skutočnosť (n), ktorá ako parameter vezme kladné celé číslo alebo 0 a vráti n-tý faktoriál, ako to môžeme urobiť pomocou rekurzie?
Pozrime sa, že ak to chceme urobiť pomocou rekurzie, musíme preskúmať nasledujúcu rovnicu
n! = n. (n-1). (n-2) a hellip3.2.1
n! = n. (n-1)! # vyššie uvedený výrok môžeme prepísať na tento riadok
java programy pre sériu fibonacci
Teraz tu, ak odovzdáme 2 ako parameter, dostaneme:
2! = 2,1! = 2
Podobne, ak minieme 1, dostaneme:
jeden! = 1,0! = 1
čo je funkcia v sql
Ale ak minieme 0, zlomí sa to
0! = 0. (- 1)! a tu faktoriál pre -1 nie je definovaný, takže to funguje iba pre hodnoty> 0
Musíme teda napísať dva prípady
1. n! = n. (n-1)! ak n> = 1
2. 1 ak n = 0
Toto je kompletné riešenie pre všetky kladné celé čísla a 0.
Podmienka ukončenia
Rekurzívna funkcia musí na ukončenie splniť dôležitú podmienku. Ak sa posunieme smerom k stavu, v ktorom je možné problém vyriešiť bez ďalšej rekurzie, rekurzívna funkcia sa ukončí a problém sa minimalizuje na menšie čiastkové kroky. Rekurzia môže skončiť v nekonečnej slučke, ak vo hovoroch nie je splnená podmienka ukončenia.
Faktorové podmienky:
- faktoriál n = n * (n-1), pokiaľ n je väčšie ako 1.
- 1, ak n = 0
Vyššie uvedené faktoriálne podmienky prevedieme v kóde python:
def fact (n): if n == 1: return n else: return n * fact (n-1)
Uveďme si príklad, povedzme, že chceme nájsť faktoriál 4:
skutočnosť (4) #this vráti 4 * skutočnosť (3) a tak ďalej, kým n == 1.
Výkon: 24
Používa sa tak často ako príklad rekurzie kvôli svojej jednoduchosti a prehľadnosti. Riešenie menších prípadov problému sa v každom kroku nazývalo ako rekurzia v informatike.
Limit rekurzie Pythonu
V niektorých jazykoch môžete vytvoriť nekonečnú rekurzívnu slučku, ale v Pythone existuje limit rekurzie. Pre kontrolu limitu spustite nasledujúcu funkciu z modulu sys. ktorý dá limit rekurzie nastavenej pre python.
import sys sys.getrecursionlimit ()
Výkon: 1 000
Môžete tiež zmeniť limit pomocou modulu funkcií syrecursionlimit () podľa vašej požiadavky. Teraz vytvorme funkciu, ktorá sa rekurzívne volá, kým neprekročí limit a nekontroluje, čo sa stane:
def rekurzívne (): rekurzívne () ak __name__ == '__main__': rekurzívne ()
Ak spustíte vyššie uvedený kód, dostanete runtime výnimku: RuntimeError: prekročená maximálna hĺbka rekurzie. Python vám bráni vo vytvorení funkcie, ktorá skončí v nekonečnej rekurzívnej slučke.
Sploštenie zoznamov s rekurziou
Ďalšie veci, ktoré môžete robiť pomocou rekurzie, okrem faktoriálov, povedzme, že chcete vytvoriť singel zo zoznamu, ktorý je vnorený, je možné vykonať pomocou nasledujúceho kódu:
def flatten (a_list, flat_list = none): ak flat_list nie je none: flat_list = [] pre položku v a_list: if isinstance (item, list): flatten (item, flat_list) else: flat_list.append (item) vrátiť flat_list ak __name__ == '__main__': vnorené = [1,2,3, [4,5], 6] x = sploštiť (vnorené) tlačiť (x)
Výkon: [1,2,3,4,5,6]
Spustenie vyššie uvedeného kódu povedie k jedinému zoznamu namiesto celočíselného zoznamu obsahujúceho celočíselný zoznam, ktorý sme použili ako vstup. To isté môžete urobiť aj inými spôsobmi, Python má niečo, čo sa volá itertools.chain (), môžete skontrolovať kód použitý na vytvorenie funkčného reťazca (), je to iný prístup, ako to urobiť my.
Výhody rekurzie
Kód je čistý a elegantný v rekurzívnej funkcii.
Zloženú úlohu je možné pomocou rekurzie rozdeliť na jednoduchšie čiastkové problémy.
Generovanie postupnosti je pri rekurzii jednoduchšie ako pri použití vnorenej iterácie.
Nevýhody rekurzie
Sledovanie logiky za rekurzívnou funkciou môže byť niekedy ťažké.
Rekurzívne hovory sú drahé (neefektívne), pretože zaberajú veľa pamäte a času.
Rekurzívne funkcie je ťažké ladiť.
triediace polia c ++
V tomto článku sme videli, čo je to rekurzia a ako môžeme z výroku o úlohe vyvinúť rekurzívne funkcie, ako matematicky možno výrok o probléme definovať. Vyriešili sme problém faktoriálu a zistili sme podmienky potrebné na nájdenie faktoriálov, z ktorých sme boli schopní tieto podmienky previesť do kódu pythonu, aby ste pochopili, ako funguje rekurzia. Myslím si, že je úžasné, že Python má zabudovaný limit pre rekurziu, aby zabránil vývojárom vo vytváraní zle zostavených rekurzívnych funkcií. Jedna dôležitá vec, ktorú si treba všimnúť, je, že rekurziu je ťažké ladiť, pretože funkcia sa neustále volá.