V tomto kurzu se naučíte vytvářet rekurzivní funkce (funkce, která se sama volá).
Co je rekurze?
Rekurze je proces definování něčeho samotného.
Příkladem fyzického světa by bylo umístění dvou paralelních zrcadel proti sobě. Jakýkoli objekt mezi nimi by se odrazil rekurzivně.
Rekurzivní funkce Pythonu
V Pythonu víme, že funkce může volat jiné funkce. Je dokonce možné, aby se funkce sama volala. Tyto typy konstruktů se nazývají rekurzivní funkce.
Následující obrázek ukazuje fungování rekurzivní funkce s názvem recurse.
Rekurzivní funkce v Pythonu
Následuje příklad rekurzivní funkce k vyhledání faktoriálu celého čísla.
Faktoriál čísla je součinem všech celých čísel od 1 do tohoto čísla. Například faktoriál 6 (označený jako 6!) Je 1 * 2 * 3 * 4 * 5 * 6 = 720.
Příklad rekurzivní funkce
def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))
Výstup
Faktoriál 3 je 6
Ve výše uvedeném příkladu factorial()je rekurzivní funkce, jak se sama nazývá.
Když tuto funkci zavoláme s kladným celým číslem, rekurzivně se zavolá snížením počtu.
Každá funkce násobí číslo s faktoriálem čísla pod ním, dokud se nerovná jedné. Toto rekurzivní volání lze vysvětlit v následujících krocích.
faktoriál (3) # 1. hovor s 3 3 * faktoriál (2) # 2. hovor s 2 3 * 2 * faktoriál (1) # 3. hovor s 1 3 * 2 * 1 # návrat z 3. hovoru jako číslo = 1 3 * 2 # návrat z 2. hovoru 6 # návrat z 1. hovoru
Podívejme se na obrázek, který ukazuje postupný proces toho, co se děje:
Práce s rekurzivní faktoriální funkcí
Naše rekurze končí, když se počet sníží na 1. Tomu se říká základní podmínka.
Každá rekurzivní funkce musí mít základní podmínku, která zastaví rekurzi, jinak se funkce volá nekonečně.
Interpret Pythonu omezuje hloubky rekurze, aby pomohl vyhnout se nekonečným rekurzím, což má za následek přetečení zásobníku.
Ve výchozím nastavení je maximální hloubka rekurze 1000. Pokud dojde k překročení limitu, bude výsledkem RecursionError. Podívejme se na jednu takovou podmínku.
def recursor(): recursor() recursor()
Výstup
Traceback (poslední hovor poslední): Soubor "", řádek 3, v souboru "", řádek 2, v souboru "", řádek 2, v souboru "", řádek 2, v a (Předchozí řádek opakován 996 vícekrát ) RecursionError: překročena maximální hloubka rekurze
Výhody rekurze
- Díky rekurzivním funkcím bude kód vypadat čistě a elegantně.
- Složitý úkol lze pomocí rekurze rozdělit na jednodušší dílčí problémy.
- Generování sekvence je s rekurzí jednodušší než s použitím nějaké vnořené iterace.
Nevýhody rekurze
- Logiku za rekurzí je někdy těžké dodržet.
- Rekurzivní volání jsou drahá (neúčinná), protože zabírají spoustu paměti a času.
- Rekurzivní funkce se obtížně ladí.
