Elkapott valaha egy véget nem érőnek tűnő körforgás, amikor egy probléma egyre kisebb darabokra ágazik?
Ha igen, akkor lehet, hogy a rekurzió lenyűgöző világába került. Bár nehéznek tűnik megérteni, ne aggódjon! Ebben a bejegyzésben egy érdekes utazásra indulunk, hogy megismerjük a rekurzió típusait.
Így hát bekötözni, miközben számos rekurzív megközelítést vizsgálunk. Készüljön fel arra, hogy belépjen a rekurzió lenyűgöző birodalmába, és figyelje meg annak figyelemre méltó képességét a bonyolult kérdések megoldásában.
Mik is pontosan a rekurziók?
Alapvetően a rekurzió egy hatékony programozási technika, amely magában foglal egy függvényt, amely meghívja magát a végrehajtás során. Ez olyan, mintha tükörbe bámulnánk, és egy képet látnánk a képen belül, ami egy önreferencia ciklust eredményez.
A nagy problémákat a rekurzió segítségével úgy kezelhetjük, hogy kisebb, jobban kezelhető részproblémákra osztjuk őket.
Ez hasonlít egy kirakós játék összeállításához, ahol az egyik darab a többi részhez kapcsolódik, hogy teljes képet hozzon létre. A rekurzió lehetővé teszi, hogy elegáns és hatékony módon oldjuk meg a problémákat ugyanazon utasításkészlet különböző bemenetekkel történő megismétlésével.
1-Közvetlen rekurzió
A közvetlen rekurzió a rekurzió legalapvetőbb típusa, amelyben egy függvény közvetlenül hívja meg magát. Ez azt jelenti, hogy egy problémás problémát kisebb részproblémákra osztanak, amíg el nem érik az alapesetet, ami a befejezéshez vezet.
A rekurzív függvény különféle bemenetekkel hívja meg magát, lehetővé téve ugyanazon utasításkészlet végrehajtásának megismétlését. Minden hívás az előzőre épül, fokozatosan közelítve a rekurzió befejezését okozó alapesethez.
Nézzük meg ezt a példát.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
output:
5
4
3
2
1
2-Közvetett rekurzió
A közvetett rekurzió érdekes csavart ad a rekurzív útvonalhoz. Ellentétben a közvetlen rekurzióval, amely magában foglalja egy függvény explicit meghívását, az indirekt rekurzió függvényhívások láncát foglalja magában.
Az egyik függvény meghívja a másikat, amely ezután meghívhatja az eredeti függvényt vagy bármely más függvényt, amely végül visszatér az eredetihez. A függvényhívások összekapcsolt hálója lenyűgöző táncot produkál, amelyben több funkció együttműködik a probléma megoldása érdekében.
Példa:
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)
output:
A: 3
B: 2
A: 1
3-Lineáris rekurzió
Fontolja meg az egyenes útvonalon való utazást, lépésről lépésre, amíg el nem éri célját. Ezt a szekvenciális technikát a lineáris rekurzió testesíti meg, amelyben egy függvény egyetlen rekurzív hívást hajt végre minden függvényiterációban.
Minden rekurzív hívásnál a rekurzív folyamat közelebb kerül az alapesethez a probléma méretének csökkentésével. Világos és lineáris módon halad, egyesével oldja meg a részproblémákat, amíg meg nem érkezik a végső válasz.
Példa:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
output:
120
4-fa rekurzió
Amikor egy függvény több rekurzív hívásra ágazik, belépünk a farekurzió világába. Egy függvény a fa rekurziójában sok rekurzív hívást generál, amelyek mindegyike külön részproblémát old meg, akárcsak a fa ágai.
Ez az elágazó struktúra több útvonal egyidejű vizsgálatát teszi lehetővé, a bonyolult kérdéseket hatékonyan kisebb, egymással összefüggő komponensekre bontva.
Példa:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
output:
8
5-beágyazott rekurzió
A beágyazott rekurzió izgalmas fokú összetettséget ad a rekurzív univerzumnak. A rekurziónak ebben a formájában egy függvény egy rekurzív hívást tartalmaz argumentumként egy másik rekurzív híváson belül.
A belső rekurzív hívás olyan értékre hat, amely a külső rekurzív hívástól függ. A bonyolultság minden egyes beágyazott meghívással növekszik, és a beágyazott rekurzív hívások érdekes mintájában csúcsosodik ki.
Példa:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Eredmény:
91
6-farkú rekurzió
A farokrekurzió a rekurzív algoritmusok optimalizálási módszere, amely javíthatja azok teljesítményét. A rekurzív hívás egy függvény végső műveleteként jelenik meg farokrekurzióval, készítéssel.
Mivel a rekurzív hívást követően nincsenek kiemelkedő műveletek, a fordító vagy az értelmező leegyszerűsítheti a rekurziót egy egyszerű ugrással helyettesítve.
Ez az optimalizálási megközelítés, amelyet farkhívás-optimalizálásnak neveznek, csökkenti annak követelményét, hogy minden rekurzív hívásnak meg kell tartania a veremkeretet, ami nagyobb sebességet és alacsonyabb memóriahasználatot eredményez.
Példa:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Outout:
120
7-Non-Tail Rekurzió
A farok rekurzióval ellentétben a nem farok rekurzió olyan extra tevékenységeket foglal magában, amelyeket a függvényen belüli rekurzív hívás után hajtanak végre. További műveletek végrehajtása előtt minden rekurzív hívásnak be kell fejeződnie és vissza kell térnie.
Ennek eredményeként az alapeset eléréséig és a rekurzió befejezéséig egy halom fennmaradó műveletek maradnak fenn. A nem végű rekurzió gyakran több memóriát használ, és kevésbé hatékony, mint a farokrekurzió, de még mindig hasznos eszköz számos probléma megoldásában.
Példa:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
output:
15
Wrap Up
A rekurzió egy érdekes fogalom a programozásban. Lehetővé teszi számunkra, hogy bonyolult problémákat rekurzív, önreferenciális módon kezeljünk.
Különálló módszert kínál a problémák gondolkodására és megoldására, kisebb, jobban kezelhető darabokra bontva azokat. A rekurzióval való munka során azonban kritikus fontosságú, hogy néhány pontra figyeljünk.
Meg kell határoznia a megfelelő alapeseteket, amelyek lehetővé teszik a rekurzió befejezését. Ha nincsenek jelen, a függvény örökre hívhatja magát.
Másodszor, az adott forgatókönyv alapján a megfelelő típusú rekurzió kiválasztása hatékonyabb és elegánsabb megoldásokhoz vezethet. Próbálja meg megtalálni a legjobb megoldást a kezében lévő problémára. Ha hatalmas rekurziós mélységekkel dolgozik, ügyeljen a lehetséges veszélyekre, például a verem túlcsordulására.
Hagy egy Válaszol