A rekurzió az informatika és a matematika alapvető fogalma, amely lehetővé teszi a függvények önmaguk elnevezését, lehetővé téve összetett problémák iteratív lépéseken keresztüli megoldását. A rekurzív függvények végrehajtásának megértésére és elemzésére általánosan használt vizuális ábrázolás a rekurziós fa. Ebben a cikkben megvizsgáljuk a rekurziós fák mögött meghúzódó elméletet, felépítésüket és a rekurzív algoritmusok megértésében betöltött jelentőségüket.

Mi az a rekurziós fa?

A rekurziós fa egy grafikus ábrázolás, amely egy rekurzív függvény végrehajtási folyamatát szemlélteti. A rekurzív hívások vizuális lebontását nyújtja, bemutatva az algoritmus előrehaladását, amint az elágazik, és végül eléri az alapesetet. A fastruktúra segít az idő bonyolultságának elemzésében és a rekurzív folyamat megértésében.

Fa szerkezete

A rekurziós fa minden csomópontja egy adott rekurzív hívást képvisel. A kezdeti hívás felül látható, alatta pedig a következő hívások ágaznak ki. A fa lefelé nő, hierarchikus struktúrát alkotva. Az egyes csomópontok elágazási tényezője a függvényen belüli rekurzív hívások számától függ. Ezenkívül a fa mélysége megfelel az alapeset elérése előtti rekurzív hívások számának.

Alap helyzet

Az alapeset a rekurzív függvény lezárási feltételeként szolgál. Meghatározza azt a pontot, ahol a rekurzió leáll, és a függvény elkezd értékeket visszaadni. A rekurziós fában az alapesetet reprezentáló csomópontok általában levélcsomópontként jelennek meg, mivel ezek nem eredményeznek további rekurzív hívásokat.

Rekurzív hívások

A rekurziós fa gyermekcsomópontjai a függvényen belül végrehajtott rekurzív hívásokat képviselik. Minden gyermek csomópont egy külön rekurzív hívásnak felel meg, ami új alproblémákat eredményez. Az ezeknek a rekurzív hívásoknak átadott értékek vagy paraméterek eltérőek lehetnek, ami az alproblémák jellemzőinek eltéréseit eredményezheti.

Végrehajtási folyamat:

A rekurziós fa bejárása betekintést nyújt a rekurzív függvény végrehajtási folyamatába. A gyökércsomópont kezdeti hívásától kezdve követjük az ágakat, hogy elérjük a következő hívásokat, amíg nem találkozunk az alapesettel. Az alapesetek elérésekor a rekurzív hívások elkezdenek visszatérni, és a fa megfelelő csomópontjait megjelölik a visszaadott értékekkel. A bejárás addig folytatódik, amíg az egész fát be nem járták.

Időkomplexitás-elemzés

A rekurziós fák segítenek a rekurzív algoritmusok időbeli összetettségének elemzésében. A fa szerkezetét megvizsgálva meghatározhatjuk az egyes szinteken végrehajtott rekurzív hívások számát és az elvégzett munkát. Ez az elemzés segít megérteni az algoritmus általános hatékonyságát, és azonosítani a potenciális hatástalanságokat vagy az optimalizálási lehetőségeket.

Bevezetés

• Gondolj egy programra, amely meghatározza egy szám faktoriálisát. Ez a függvény egy N számot vesz fel bemenetként, és eredményeként adja vissza az N faktoriálisát. Ennek a függvénynek a pszeudokódja hasonlít majd

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

• A rekurzió példája a korábban említett függvény. Egy függvényt hívunk meg egy szám faktoriálisának meghatározására. Ezután, ha ugyanannak a számnak kisebb értéke van, ez a függvény meghívja magát. Ez addig folytatódik, amíg el nem érjük az alapesetet, amelyben már nincs függvényhívás.
• A rekurzió bonyolult problémák kezelésére szolgáló technika, amikor az eredmény ugyanazon probléma kisebb példányainak kimenetelétől függ.
• Ha függvényekre gondolunk, egy függvényt rekurzívnak mondunk, ha addig hívja magát, amíg el nem éri az alapesetet.
• Minden rekurzív függvénynek két elsődleges összetevője van: az alapeset és a rekurzív lépés. Ha elérjük az alapesetet, abbahagyjuk a rekurzív fázisba lépést. A végtelen rekurzió megelőzése érdekében az alapeseteket megfelelően meg kell határozni, és ezek kulcsfontosságúak. A végtelen rekurzió definíciója olyan rekurzió, amely soha nem éri el az alapesetet. Ha egy program soha nem éri el az alapesetet, a veremtúlcsordulás továbbra is előfordul.

Rekurziós típusok

Általánosságban elmondható, hogy a rekurziónak két különböző formája van:

• Lineáris rekurzió
• Fa rekurzió
• Lineáris rekurzió

Lineáris rekurzió

• Azt a függvényt, amely minden egyes végrehajtáskor csak egyszer hívja meg magát, lineárisan rekurzívnak nevezzük. A lineáris rekurzió szép példája a faktoriális függvény. A „lineáris rekurzió” elnevezés arra a tényre utal, hogy egy lineárisan rekurzív függvény végrehajtása lineárisan sok időt vesz igénybe.
• Vessen egy pillantást az alábbi pszeudokódra:

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• Ha megnézzük a doSomething(n) függvényt, az elfogad egy n nevű paramétert, és elvégzi a számításokat, mielőtt még egyszer meghívná ugyanazt az eljárást, de alacsonyabb értékekkel.
• Ha a doSomething() metódust n argumentumértékkel hívjuk meg, tegyük fel, hogy T(n) a számítás befejezéséhez szükséges teljes időt jelenti. Ehhez egy ismétlődési relációt is megfogalmazhatunk, T(n) = T(n-1) + K. Itt K konstansként szolgál. A K konstans azért van benne, mert időbe telik, amíg a függvény memóriát lefoglal vagy lefoglal egy változóhoz, vagy végrehajt egy matematikai műveletet. K-t használunk az idő meghatározására, mivel az nagyon kicsi és jelentéktelen.
• Ennek a rekurzív programnak az időbonyolultsága egyszerűen kiszámítható, mivel a legrosszabb esetben a doSomething() metódust n-szer hívják meg. Formálisan a függvény időbeli összetettsége O(N).

Fa rekurzió

• Ha egynél többször indít rekurzív hívást a rekurzív esetben, azt fa rekurziónak nevezzük. A fa rekurzió hatásos illusztrációja a fibonacci sorozat. A fa rekurzív függvényei exponenciális időben működnek; időbeli összetettségükben nem lineárisak.
• Vessen egy pillantást az alábbi pszeudokódra,

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• Az egyetlen különbség ez a kód és az előző között az, hogy ez még egy hívást hajt végre ugyanarra a függvényre alacsonyabb n értékkel.
• T(n) = T(n-1) + T(n-2) + k tegyük ennek a függvénynek az ismétlődési relációját. K még egyszer konstansként szolgál.
• Ha ugyanannak a függvénynek egynél több hívása történik kisebb értékekkel, akkor ezt a fajta rekurziót farekurziónak nevezzük. Az érdekes szempont most: mennyire időigényes ez a funkció?
• Az alábbi rekurziós fa alapján tippeljen ugyanarra a függvényre.
  
• Előfordulhat, hogy nehéz megbecsülni az időbonyolultságot egy rekurzív függvény közvetlen megtekintésével, különösen, ha az egy fa rekurzió. A rekurziós fa módszer egyike azon technikák közül, amelyekkel kiszámítható az ilyen függvények időbeli összetettsége. Vizsgáljuk meg részletesebben.

Mi az a rekurziós fa módszer?

• Az olyan ismétlődési relációkat, mint a T(N) = T(N/2) + N, vagy a kettő, amelyet korábban a rekurzió típusainál tárgyaltunk, a rekurziós fa megközelítéssel oldjuk meg. Ezek az ismétlődő kapcsolatok gyakran az oszd meg és uralkodj stratégiát alkalmaznak a problémák megoldására.
• Időbe telik a válaszok integrálása a kisebb részproblémákra, amelyek akkor jönnek létre, amikor egy nagyobb problémát kisebb részproblémákra bontanak.
• Az ismétlődési reláció például T(N) = 2 * T(N/2) + O(N) az összevonási rendezésnél. A két részprobléma T(N/2) kombinált méretű válaszainak kombinálásához szükséges idő O(N), ami igaz a megvalósítás szintjén is.
• Például, mivel a bináris keresés ismétlődési relációja T(N) = T(N/2) + 1, tudjuk, hogy a bináris keresés minden iterációja egy olyan keresési teret eredményez, amely felére van vágva. Az eredmény meghatározása után kilépünk a függvényből. Az ismétlődési reláció +1 hozzáadva, mert ez egy állandó idejű művelet.
• A T(n) = 2T(n/2) + Kn ismétlődési összefüggést érdemes figyelembe venni. Kn az n/2-dimenziós részfeladatok válaszainak kombinálásához szükséges időt jelöli.
• Ábrázoljuk a rekurziós fát a fent említett ismétlődési relációhoz.

A fenti rekurziós fa tanulmányozásából levonhatunk néhány következtetést, többek között

1. Egy csomópont értékének meghatározásához csak a probléma nagysága minden szinten számít. A kiadás mérete n a 0. szinten, n/2 az 1. szinten, n/2 a 2. szinten stb.

2. Általánosságban a fa magasságát log (n) értékkel definiáljuk, ahol n a probléma mérete, és ennek a rekurziós fának a magassága megegyezik a fában lévő szintek számával. Ez igaz, mert amint azt az imént megállapítottuk, az oszd meg és uralkodj stratégiát az ismétlődő relációk használják problémák megoldására, és az n-es problémaméretről az 1-es problémaméretre való eljutáshoz egyszerűen log (n) lépések megtétele szükséges.

• Vegyük például az N = 16 értékét. Ha megengedjük, hogy minden lépésben elosztjuk N-t 2-vel, hány lépésre van szükség ahhoz, hogy N = 1 legyen? Tekintettel arra, hogy minden lépésben osztunk kettővel, a helyes válasz 4, ami a log(16) 2-es bázis értéke.

log(16) 2. alap

A karakterlánc java-t tartalmaz

log(2^4) 2. bázis

4 * log(2) bázis 2, mivel log(a) bázis a = 1

tehát 4 * log(2) bázis 2 = 4

3. Minden szinten az ismétlődés második tagját tekintjük gyökérnek.

Bár a „fa” szó szerepel ennek a stratégiának a nevében, nem kell a fák szakértőjének lenni ahhoz, hogy megértse.

Hogyan használjunk rekurziós fát az ismétlődési kapcsolatok megoldására?

A részprobléma költsége a rekurziós fa technikában a részprobléma megoldásához szükséges idő. Ezért, ha észreveszi a „költség” kifejezést a rekurziós fával kapcsolatban, az egyszerűen egy bizonyos részprobléma megoldásához szükséges időre utal.

Nézzük meg ezeket a lépéseket néhány példával.

Példa

Tekintsük az ismétlődési összefüggést,

T(n) = 2T(n/2) + K

Megoldás

Az adott ismétlődési reláció a következő tulajdonságokat mutatja:

távolítsa el az utolsó karaktert a karakterláncból

Egy n méretű probléma két részproblémára van osztva, amelyek mindegyike n/2 méretű. Ezen részproblémák megoldásainak kombinálásának költsége K.

Minden n/2 problémaméret két részproblémára van osztva, amelyek mindegyike n/4 és így tovább.

Az utolsó szinten a részprobléma mérete 1-re csökken. Vagyis végre eltaláltuk az alapesetet.

Kövesse az ismétlődési reláció megoldásának lépéseit,

1. lépés: Rajzolja meg a rekurziós fát

2. lépés: Számítsa ki a fa magasságát

Mivel tudjuk, hogy ha egy számot folyamatosan osztunk 2-vel, eljön az idő, amikor ez a szám 1-re csökken. Ugyanúgy, mint az N feladatnál, tegyük fel, hogy K 2-vel való osztás után N egyenlő lesz 1-gyel, ami azt jelenti, ( n/2^k) = 1

Itt n / 2^k a probléma mérete az utolsó szinten, és mindig egyenlő 1-gyel.

Most már könnyen kiszámíthatjuk k értékét a fenti kifejezésből, ha mindkét oldalra felvesszük a log()-t. Az alábbiakban egy egyértelműbb levezetés látható,

n = 2^k

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) bázis 2

Tehát a fa magassága log (n) bázis 2.

3. lépés: Számítsa ki a költségeket minden szinten

• Költség a 0. szinten = K, két részprobléma összevonásra kerül.
• Költség az 1. szinten = K + K = 2*K, két részprobléma kétszer összevonásra kerül.
• Költség a 2. szinten = K + K + K + K = 4*K, két részprobléma négyszer összevonásra kerül. stb....

4. lépés: Számítsa ki a csomópontok számát minden szinten

dateformat.format

Először határozzuk meg a csomópontok számát az utolsó szinten. A rekurziós fából erre következtethetünk

• A 0. szintnek 1 (2^0) csomópontja van
• Az 1. szintnek 2 (2^1) csomópontja van
• A 2. szintnek 4 (2^2) csomópontja van
• A 3. szint 8 (2^3) csomóponttal rendelkezik

Tehát a log(n) szintnek 2^(log(n)) csomópontja kell, hogy legyen, azaz n csomópont.

5. lépés: Adja össze az összes szint költségét

• A teljes költség így írható fel,
• Teljes költség = az utolsó szint kivételével az összes szint költsége + az utolsó szint költsége
• Teljes költség = 0. szint költsége + 1. szint költsége + 2. szint költsége +.... + log(n) szint költsége + utolsó szint költsége

Az utolsó szint költsége külön kerül kiszámításra, mivel ez az alapeset, és az utolsó szinten nem történik összevonás, így ezen a szinten egyetlen probléma megoldásának költsége valamilyen állandó érték. Vegyük O-nak (1).

Tegyük az értékeket a képletekbe,

• T(n) = K + 2*K + 4*K + .... + log(n)' szor + 'O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n)-szor)' + 'O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n)-szor + O(n)

Ha alaposan megnézi a fenti kifejezést, geometriai progressziót alkot (a, ar, ar^2, ar^3 ...... végtelen idő). A GP összegét S(N) = a / (r - 1) adja meg. Itt van az első tag, és r a közös arány.