Byli jste někdy chyceni ve zdánlivě nekonečném cyklu, kdy se problém stále větví na menší fragmenty?
Pokud ano, možná jste narazili na fascinující svět rekurze. I když se to může zdát náročné na pochopení, nebojte se! V tomto příspěvku se vydáme na zajímavou cestu, abychom se dozvěděli o typech rekurzí.
Připoutejte se, až budeme zkoumat četné rekurzivní přístupy. Připravte se na vstup do fascinující říše rekurze a pozorujte její pozoruhodnou schopnost při řešení složitých problémů.
Co přesně jsou rekurze?
Jednoduše řečeno, rekurze je výkonná programovací technika, která zahrnuje funkci, která se během provádění sama volá. Je to jako zírat do zrcadla a vidět obraz uvnitř obrazu, což má za následek sebereferenční cyklus.
Velké problémy můžeme řešit pomocí rekurze tak, že je rozdělíme na menší, lépe zvládnutelné dílčí problémy.
Je to podobné, jako když skládáte skládačku, kde se jeden kus spojuje s dalšími částmi a vytváří tak úplný obraz. Rekurze nám umožňuje řešit problémy elegantním a efektivním způsobem opakováním stejné sady instrukcí s různými vstupy.
1-přímá rekurze
Přímá rekurze je nejzákladnějším typem rekurze, ve které funkce volá sama sebe přímo. Znamená to rozdělení problematického problému na menší dílčí problémy, dokud není dosaženo základního případu, což vede k ukončení.
Rekurzivní funkce volá sama sebe s různými vstupy, což umožňuje opakování provádění stejné sady instrukcí. Každé vyvolání navazuje na předchozí a postupně se blíží základnímu případu, který způsobí ukončení rekurze.
Podívejme se na tento příklad.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
Výstup:
5
4
3
2
1
2-Nepřímá rekurze
Nepřímá rekurze dodává rekurzivní cestě zajímavý zvrat. Na rozdíl od přímé rekurze, která zahrnuje funkci explicitně volající samotnou, nepřímá rekurze zahrnuje řetězec volání funkcí.
Jedna funkce volá jinou, která pak může volat původní funkci nebo jakoukoli jinou funkci, která se nakonec vrátí k originálu. Tato propojená síť volání funkcí vytváří fascinující tanec, ve kterém několik funkcí spolupracuje na vyřešení problému.
Příklad:
def function_A(n):
if n > 0:
print("A:", n)
function_B(n - 1)
def function_B(n):
if n > 0:
print("B:", n)
function_A(n - 1)
function_A(3)
Výstup:
A: 3
B: 2
A: 1
3-lineární rekurze
Zvažte cestu po přímé trase, jeden krok po druhém, dokud nedosáhnete svého cíle. Tato sekvenční technika je ztělesněna lineární rekurzí, ve které funkce provádí jediné rekurzivní volání v každé iteraci funkce.
S každým rekurzivním voláním se rekurzivní proces přibližuje k základnímu případu snížením velikosti problému. Postupuje jasným a lineárním způsobem a řeší dílčí problémy jeden po druhém, dokud není dosaženo konečné odpovědi.
Příklad:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
Výstup:
120
4-stromová rekurze
Když se funkce rozvětví do několika rekurzivních volání, vstupujeme do světa stromové rekurze. Funkce ve stromové rekurzi generuje mnoho rekurzivních volání, z nichž každé řeší samostatný dílčí problém, stejně jako to dělají větve stromu.
Tato rozvětvená struktura umožňuje současné zkoumání několika tras a efektivně rozděluje komplikované problémy na menší, vzájemně propojené komponenty.
Příklad:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
Výstup:
8
5-vnořená rekurze
Vnořená rekurze dodává rekurzivnímu vesmíru vzrušující stupeň složitosti. V této formě rekurze funkce zahrnuje rekurzivní volání jako argument v rámci jiného rekurzivního volání.
Vnitřní rekurzivní volání působí na hodnotu, která je závislá na vnějším rekurzivním volání. Složitost roste s každým vnořeným vyvoláním a vyvrcholí zajímavým vzorem vnořených rekurzivních volání.
Příklad:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Výsledek:
91
6-ocasní rekurze
Tailová rekurze je optimalizační technika pro rekurzivní algoritmy, která může zlepšit jejich výkon. Rekurzivní volání se objeví jako poslední akce funkce s koncovou rekurzí, takže.
Protože po rekurzivním volání nejsou žádné nevyřízené operace, kompilátor nebo interpret může rekurzi zjednodušit tím, že ji nahradí jednoduchým skokem.
Tento přístup optimalizace, známý jako optimalizace koncového volání, snižuje požadavek, aby si každé rekurzivní volání zachovalo rámec zásobníku, což má za následek vyšší rychlost a nižší využití paměti.
Příklad:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Out out:
120
7-Neocasní rekurze
Na rozdíl od koncové rekurze, non-tail rekurze zahrnuje další aktivity prováděné po rekurzivním volání v rámci funkce. Před provedením dalších akcí se musí každé rekurzivní volání dokončit a vrátit se zpět.
V důsledku toho, dokud není dosaženo základního případu a neskončí rekurze, je udržován zásobník nevyřízených operací. Non-tail rekurze často využívá více paměti a je méně efektivní než tail rekurze, ale je to stále užitečný nástroj pro řešení různých problémů.
Příklad:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
Výstup:
15
Zabalit
Rekurze je v programování zajímavý koncept. Umožňuje nám řešit komplikované problémy rekurzivním, sebereferenčním způsobem.
Nabízí odlišnou metodu přemýšlení a řešení problémů, jejich rozdělení na menší, lépe zvládnutelné části. Při práci s rekurzí je však důležité věnovat pozornost některým bodům.
Měli byste identifikovat vhodné základní případy, které umožní ukončení rekurze. Pokud nejsou přítomny, může se funkce nadále volat navždy.
Za druhé, na základě aktuálního scénáře může výběr vhodného druhu rekurze vést k efektivnějším a elegantnějším řešením. Pokuste se najít to, co nejlépe funguje na problém v ruce. Při práci s obrovskými hloubkami rekurze mějte na paměti potenciální nebezpečí, jako je přetečení zásobníku.
Napsat komentář