Co je rekurzivní funkce?
Funkce se volá znovu a znovu, dokud nesplňuje rekurzivní stav. Funkce rekurze rozdělí problém na menší problémy a jeho vlastní logika vyřeší menší problém. Tato technika je známá jako rozdělení a dobytí. Používá se v oblasti matematiky a informatiky.
Rekurzivní funkce zahrnuje základní případ (nebo terminálový případ) a rekurzivní případ. V základním případě můžete zvážit hlavní problém, který má být vyřešen, a rekurzivní případ rozdělí problém na menší části, dokud nedosáhne úrovně, kde může být snadno vyřešen. Rekurzivní případ může vrátit výsledek nebo se může znovu volat, aby problém dále rozdělil. Pokaždé, když se problém rozdělí na menší problém, funkce, která se nazývá rekurzivně, uloží stav hovoru a po vyřešení problému očekává výsledek sám od sebe.
Rekurzivní funkce v Pythonu
Koncept rekurze zůstává v Pythonu stejný. Funkce se volá, aby se problém rozdělil na menší problémy. Nejjednodušším příkladem, který bychom si mohli vzpomenout na rekurzi, bylo nalezení faktoriálu čísla.
Řekněme, že musíme najít faktoriál čísla 5 => 5! (Náš problém)
Najít 5! problém lze rozdělit na menší 5! => 5 x 4!
Takže, dostat 5! Musíme najít 4! a vynásobte jej 5.
Pokračujme v rozdělení problému
5! = 4! x 5
4! = 3! x 4
3! = 3 x 2!
2! = 2 x 1!
1! = 1
Když dosáhne nejmenšího kusu, tj. Získáme faktoriál 1, můžeme výsledek vrátit jako
Vezměme si pseudokódový příklad: -
Algoritmus pro faktoriál
Podívejme se na algoritmus pro faktoriál:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Volání funkcí
Předpokládejme, že najdeme 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ýsledkem bude 120, kde jsme zahájili provádění funkce. Naše rekurzní funkce se zastaví, když je počet tak snížen, že lze dosáhnout výsledku.
- První hovor, který získává faktoriál 5, bude mít za následek rekurzivní stav, kdy bude přidán do zásobníku a další hovor bude proveden po snížení čísla na 4.
- Tato rekurze bude pokračovat v volání a rozdělení problému na menší kousky, dokud nedosáhne základního stavu.
- Základní podmínkou je, že číslo je 1.
- Každá rekurzivní funkce má svůj vlastní rekurzivní stav a základní stav.
Výhody a nevýhody rekurzivní funkce Pythonu
- Provedení rekurze je tak, že nebude provádět žádné výpočty, dokud nedosáhne základní podmínky.
- Při dosažení základních podmínek vám může dojít nedostatek paměti.
- Ve velkém problému, kde může být milión kroků nebo můžeme říci, že k tomu může dojít milión rekurzí, by program mohl skončit chybou paměti nebo chybou segmentace.
- 1000000! = 1000000 * 999999! =?
- Rekurze je jiná než iterace, která se nezmění jako iterační metoda.
- Různé jazyky mají různé optimalizace pro rekurzi.
- V mnoha jazycích by iterační metoda fungovala lépe než rekurze.
- Každý jazyk má určitá omezení ohledně hloubky rekurze, s níž se můžete při řešení velkých problémů setkat.
- Někdy je těžké pochopit složité problémy s rekurzí, zatímco je to docela jednoduché s iterací.
Někteří profesionálové
- V některých případech je rekurze pohodlným a rychlejším způsobem použití.
- Velmi užitečné při procházení stromu a binárním vyhledávání.
Pythonův kód - Rekurze vs. Iterace
Pochopili jsme, co je rekurze a jak to funguje v Pythonu, protože víme, že všechny jazyky mají jinou implementaci rekurze pro optimalizaci paměti a výpočet. Může nastat případ, kdy by iterace byla rychlejší než rekurze.
Zde bychom porovnali rekurzi i iterační metodu, abychom viděli, jak Python hraje v obou případech.
1. Kód rekurze pro 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 pomocí iterace (opakování)
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 tisku
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
Výstup:
Jak vidíme, oba dávají stejný výstup, jak jsme psali stejnou logiku. Tady nevidíme žádný rozdíl ve vykonávání.
Přidáme nějaký časový kód, abychom získali více informací o provádění rekurze a iterace v Pythonu.
Importujeme knihovnu „času“ a zkontrolujeme, jakou časovou rekurzi a iteraci trvá, než se výsledek vrátí.
4. Kód s výpočtem č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))
Učiníme opakované provádění s jinou hodnotou pro faktoriál a uvidíme výsledky. Níže uvedené výsledky se mohou u jednotlivých strojů lišit. Použili jsme MacBook Pro 16 GB RAM i7.
K provedení používáme Python 3.7
Případ 1: - Faktor 6:
Případ 2: Factorial of 50:
Případ 3: Factorial 100:
Případ 4: Factorial 500:
Případ 5: Factorial 1000:
Analyzovali jsme obě metody v jiném problému. Kromě toho oba provedli podobné, kromě případu 4.
V případě 5 jsme při rekurzi dostali chybu.
Python dostal omezení na maximální hloubku, kterou můžete jít s rekurzí, ale stejný problém jsem byl schopen vyřešit iterací.
Python má omezení proti problému přetečení. Python není optimalizován pro rekurzi ocasu a nekontrolovaná rekurze způsobuje přetečení zásobníku.
Funkce sys.getrecursionlimit () vám řekne limit rekurze.
Limit rekurze lze změnit, ale nedoporučuje se, že by to mohlo být nebezpečné.
Závěr - Pythonova rekurzivní funkce
- Rekurze je užitečným řešením pro některé problémy, jako je stromový strom a jiné problémy.
- Python není funkční programovací jazyk a můžeme vidět, že rekurzní zásobník není ve srovnání s iterací optimalizovaný.
- Měli bychom použít iteraci v našem algoritmu, protože je v Pythonu optimalizován a poskytuje vám vyšší rychlost.
Doporučené články
Toto je průvodce rekurzivní funkcí v Pythonu. Zde diskutujeme o tom, co je rekurzivní funkce, rekurzivní funkce v Pythonu, Algoritmus pro faktoriál atd. Další informace naleznete také v našich dalších navrhovaných článcích -
- Factorial v Pythonu
- Příkazy Spark Shell
- Nejlepší kompilátory C
- Druhy algoritmů
- Věcný program v JavaScriptu
- Průvodce seznamem unixových příkazů shellu
- Druhy formulářů v reakci s příklady