Už ste sa niekedy ocitli v zdanlivo nekončiacom kolobehu, kde sa problém stále rozvetvuje na menšie fragmenty?
Ak áno, možno ste narazili na fascinujúci svet rekurzie. Aj keď sa to môže zdať náročné na pochopenie, nebojte sa! V tomto príspevku sa vydáme na zaujímavú cestu, aby sme sa dozvedeli o typoch rekurzie.
Takže sa pripútajte, keď skúmame množstvo rekurzívnych prístupov. Pripravte sa vstúpiť do fascinujúcej ríše rekurzie a pozorujte jej pozoruhodnú schopnosť pri riešení zložitých problémov.
Čo sú to vlastne rekurzie?
Stručne povedané, rekurzia je výkonná programovacia technika, ktorá zahŕňa funkciu, ktorá sa počas vykonávania volá. Je to ako pozerať sa do zrkadla a vidieť obraz vo vnútri obrazu, čo vedie k cyklu sebareferencovania.
Veľké problémy môžeme riešiť pomocou rekurzie tak, že ich rozdelíme na menšie, lepšie zvládnuteľné podproblémy.
Je to podobné, ako keď skladáte skladačku, kde je jeden diel prepojený s ostatnými časťami a vytvára tak úplný obraz. Rekurzia nám umožňuje riešiť problémy elegantným a efektívnym spôsobom opakovaním rovnakej sady inštrukcií s rôznymi vstupmi.
1-Priama rekurzia
Priama rekurzia je najzákladnejším typom rekurzie, pri ktorej funkcia volá sama seba priamo. Znamená to rozdeliť problémový problém na menšie podproblémy, kým sa nedosiahne základný prípad, čo vedie k ukončeniu.
Rekurzívna funkcia volá seba s rôznymi vstupmi, čo umožňuje opakovanie vykonania rovnakej sady inštrukcií. Každé vyvolanie nadväzuje na predchádzajúce, pričom sa postupne približuje k základnému prípadu, ktorý spôsobí ukončenie rekurzie.
Pozrime sa na tento príklad.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
Výkon:
5
4
3
2
1
2-Nepriama rekurzia
Nepriama rekurzia dodáva rekurzívnej ceste zaujímavý zvrat. Na rozdiel od priamej rekurzie, ktorá zahŕňa funkciu, ktorá sa explicitne volá, nepriama rekurzia zahŕňa reťaz volaní funkcií.
Jedna funkcia volá inú, ktorá potom môže volať pôvodnú funkciu alebo akúkoľvek inú funkciu, ktorá sa nakoniec vráti k originálu. Táto prepojená sieť volaní funkcií vytvára fascinujúci tanec, v ktorom niekoľko funkcií spolupracuje na riešení problému.
Prí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ýkon:
A: 3
B: 2
A: 1
3-lineárna rekurzia
Zvážte cestu po priamej trase, krok za krokom, kým nedosiahnete svoj cieľ. Táto sekvenčná technika je stelesnená lineárnou rekurziou, v ktorej funkcia vykonáva jediné rekurzívne volanie v každej iterácii funkcie.
S každým rekurzívnym volaním sa rekurzívny proces približuje k základnému prípadu znížením veľkosti problému. Postupuje jasným a lineárnym spôsobom a rieši podproblémy jeden po druhom, až kým sa nedosiahne konečná odpoveď.
Príklad:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
Výkon:
120
4-stromová rekurzia
Keď sa funkcia rozvetví na niekoľko rekurzívnych volaní, vstúpime do sveta stromovej rekurzie. Funkcia v stromovej rekurzii generuje mnoho rekurzívnych volaní, z ktorých každé rieši samostatný podproblém, rovnako ako to robia vetvy stromu.
Táto rozvetvená štruktúra umožňuje súčasné skúmanie niekoľkých trás a efektívne rozdeľuje komplikované problémy na menšie, vzájomne prepojené komponenty.
Príklad:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
Výkon:
8
5-vnorená rekurzia
Vnorená rekurzia dodáva rekurzívnemu vesmíru vzrušujúci stupeň zložitosti. V tejto forme rekurzie funkcia zahŕňa rekurzívne volanie ako argument v rámci iného rekurzívneho volania.
Vnútorné rekurzívne volanie pôsobí na hodnotu, ktorá je závislá od vonkajšieho rekurzívneho volania. Zložitosť rastie s každým vnoreným vyvolaním, čo vyvrcholí v pútavom vzore vnorených rekurzívnych volaní.
Prí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ýsledok:
91
6-chvostová rekurzia
Rekurzia chvosta je optimalizačná technika pre rekurzívne algoritmy, ktorá môže zlepšiť ich výkon. Rekurzívne volanie sa javí ako posledná akcia funkcie s koncovou rekurziou.
Pretože po rekurzívnom volaní nie sú žiadne nevybavené operácie, kompilátor alebo interpret môže zjednodušiť rekurziu tým, že ju nahradí jednoduchým skokom.
Tento prístup optimalizácie, známy ako optimalizácia koncového volania, znižuje požiadavku, aby si každé rekurzívne volanie zachovalo rámec zásobníka, čo vedie k vyššej rýchlosti a nižšej spotrebe pamäte.
Prí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-Nechvostová rekurzia
Na rozdiel od koncovej rekurzie, non-tailová rekurzia zahŕňa ďalšie aktivity vykonávané po rekurzívnom volaní v rámci funkcie. Pred vykonaním akýchkoľvek ďalších akcií sa musí každé rekurzívne volanie dokončiť a vrátiť.
V dôsledku toho, kým sa nedosiahne základný prípad a neskončí sa rekurzia, udržiava sa zásobník nevybavených operácií. Rekurzia bez chvosta často využíva viac pamäte a je menej efektívna ako rekurzia chvosta, ale stále je to užitočný nástroj na riešenie rôznych problémov.
Prí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ýkon:
15
Zabaliť
Rekurzia je v programovaní zaujímavý koncept. Umožňuje nám riešiť komplikované problémy rekurzívnym, sebareferenčným spôsobom.
Ponúka osobitnú metódu premýšľania a riešenia problémov, pričom ich rozdeľuje na menšie, lepšie zvládnuteľné časti. Pri práci s rekurziou je však dôležité venovať pozornosť niektorým bodom.
Mali by ste identifikovať vhodné základné prípady, ktoré umožnia ukončenie rekurzie. Ak nie sú prítomné, funkcia sa môže naďalej volať sama.
Po druhé, na základe daného scenára môže výber vhodného druhu rekurzie viesť k efektívnejším a elegantnejším riešeniam. Pokúste sa nájsť to, čo najlepšie funguje na problém v ruke. Pri práci s obrovskými hĺbkami rekurzie si uvedomte potenciálne nebezpečenstvá, ako je pretečenie zásobníka.
Nechaj odpoveď