co je rekurze?

rekurze je proces definování něčeho z hlediska sebe sama.

příkladem fyzického světa by bylo umístit dvě paralelní zrcadla proti sobě. Jakýkoli objekt mezi nimi by se rekurzivně odrážel.

Python rekurzivní funkce

v Pythonu víme, že funkce může volat jiné funkce. Je dokonce možné, aby se funkce sama zavolala. Tyto typy konstruktů se nazývají rekurzivní funkce.

následující obrázek ukazuje práci rekurzivní funkce nazvané recurse.

Následující je příklad rekurzivní funkce najít faktoriál celočíselné.

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 = 3print("The factorial of", num, "is", factorial(num))

Výstupní

The factorial of 3 is 6

Ve výše uvedeném příkladu, factorial() je rekurzivní funkci, jak to sama nazývá.

Když jsme volání této funkce s pozitivní celé číslo, bude rekurzivně volat sám tím, že klesá počet.

každá funkce vynásobí číslo faktoriálem čísla pod ním, dokud se rovná jednomu. Toto rekurzivní volání lze vysvětlit v následujících krocích.

factorial(3) # 1st call with 33 * factorial(2) # 2nd call with 23 * 2 * factorial(1) # 3rd call with 13 * 2 * 1 # return from 3rd call as number=13 * 2 # return from 2nd call6 # return from 1st call

Pojďme se podívat na obrázek, který ukazuje, krok-za-krokem procesu o tom, co se děje:

Naše rekurze končí, když se počet snižuje na 1. Tomu se říká základní podmínka.

každá rekurzivní funkce musí mít základní podmínku, která rekurzi zastaví, jinak se funkce volá nekonečně.

interpret Pythonu omezuje hloubky rekurze, aby zabránil 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 je limit překročen, výsledkem je RecursionError. Podívejme se na jednu takovou podmínku.

def recursor(): recursor()recursor()

Výstupní

Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a RecursionError: maximum recursion depth exceeded

Výhody Rekurze

1. Rekurzivní funkce, aby kód vypadají čisté a elegantní.
2. složitou úlohu lze pomocí rekurze rozdělit na jednodušší dílčí problémy.
3. generování sekvencí je jednodušší s rekurzí než pomocí nějaké vnořené iterace.

nevýhody rekurze

1. někdy je logika za rekurzí obtížná.
2. rekurzivní hovory jsou drahé (neefektivní), protože zabírají spoustu paměti a času.
3. rekurzivní funkce se těžko ladí.