Fő tartalom
Tantárgy/kurzus: Számítástudomány > 1. témakör
6. lecke: Rekurzív algoritmusok- Rekurzió
- A faktoriális függvény
- Feladat: Iteratív faktoriális
- Faktoriális rekurzív kiszámítása
- Feladat: Rekurzív faktoriális
- Rekurzív algoritmusok tulajdonságai
- Állapítsuk meg rekurzív algoritmussal egy szóról, hogy az palindrom-e!
- Feladat: A szó palindróma?
- Számoljuk ki egy szám hatványát!
- Feladat: Rekurzív hatványok
- Sierpinski tömítés többszörös rekurzióval
- Hogyan tehetjük a rekurziót hatékonyabbá?
- Projekt: Rekurzív művészet
© 2024 Khan AcademyFelhasználási feltételekAdatkezelési tájékoztatóSüti figyelmeztetés
Hogyan tehetjük a rekurziót hatékonyabbá?
Elegáns megoldás lehet egy problémára a rekurzió, és sok algoritmus könnyen megfogalmazható rekurzívan. A rekurzió azonban futási idő és tárhely tekintetében gyakran kevésbé hatékony. Itt most meg fogunk vizsgálni néhány olyan technikát, amivel a hatékonyságot növelhetjük.
A Rekurzív faktoriális feladatban azt kértük, hogy különböző számok faktoriálisát számítsátok ki a függvény többszöri meghívásával.
Például az alábbi JavaScript program négyszer hívja meg a
factorial()
-t:factorial(0);
factorial(2);
factorial(5);
factorial(10);
Vegyük sorra a hívásokat, és nézzük meg, mit csinál a számítógép a hívások során!
programsor | Rekurzív hívások | Összes hívás |
---|---|---|
factorial(0) | 1 hívás | |
factorial(2) | factorial(1) → factorial(0) | 3 hívás |
factorial(5) | factorial(4) → factorial(3) → factorial(2) → factorial(1) → factorial(0) | 6 hívás |
factorial(10) | factorial(9) → factorial(8) → factorial(7) → factorial(6) → factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1) → factorial(0) | 11 hívás |
Figyeld meg, hogy
factorial(10)
11 függvényhívást hajt végre, amiből 6-nak ugyanaz az argumentuma és a visszaadott értéke, mint az előzőleg hívott factorial(5)
-nek.A faktoriális érték megjegyzése
Alkalmazhatunk egy megjegyzésnek nevezett technikát arra, hogy futási időt spóroljunk akkor, ha korábban már futtattunk egy ugyanolyan hívást. A megjegyzéses technika (a rögzítésnek egy formája) egy táblázatban raktározza el az adott bemenethez tartozó függvényhívás eredményét, ahonnan előkeresi az értéket, ha a függvényt újra ugyanazzal a paraméterrel hívják meg.
A faktoriális függvény megjegyzéses technikája így néz ki:
- Ha
= 0, adj vissza 1-et! - Ha nem, és
benne van a táblázatban, add vissza az -hez tartozó értéket! - Ha nincs a táblázatban,
- Számítsd ki
-t! - Tárold el az eredményt a táblázatban!
- Add vissza az eredményt!
- Számítsd ki
Ez az algoritmus a potenciálisan költséges rekurzív eljárás meghívása előtt ellenőrzi az inputot a táblázatban. A táblázatnak hatékony keresést megvalósító adatstruktúrának kell lennie, például egy hash táblázatnak, amiben a keresés időt vesz igénybe.
Ha szeretnéd megfigyelni a megjegyzéses algoritmus JavaScriptben megírt programjának működését, nézd meg ezt a videót, vagy futtasd a vizualizációt! Mielőtt megnézed, megpróbálhatod magad megírni az algoritmust valamilyen általad kiválasztott nyelven.
A megjegyzéses módszer alkalmazása esetén kevesebb hívás fog kelleni, ha a
factorial()
függvényt többször hívjuk meg:Programsor | Rekurzív hívások | Összes hívás |
---|---|---|
factorial(0) | 1 hívás | |
factorial(2) | factorial(1) → factorial(0) | 3 hívás |
factorial(5) | factorial(4) → factorial(3) → factorial(2) | 3 hívás |
factorial(10) | factorial(9) → factorial(8) → factorial(7) → factorial(6) → factorial(5) | 6 hívás |
A megjegyzéses eljárásnál az idő megtakarítása tárolási helyigény növelésével jár. Ha a keresés hatékony, és a függvényt sokszor hívják meg, időt spórolhatunk meg annak árán, hogy a memóriában helyet foglalunk le a táblázat tárolásához.
Fibonacci számok megjegyzéses technikával
A faktoriális függvény esetében az algoritmus csak akkor válik hatékonyabbá, ha a program végrehajtása során többször is meghívja a függvényt. Bizonyos esetekben akár a rekurzív függvény egyetlen meghívása esetén is időt takarít meg a megjegyzéses eljárás.
Vegyünk egy egyszerű példát, a Fibonacci számok generálását.
A Fibonacci számok egy híres számsorozat, ahol minden szám az azt megelőző két szám összege. A sorozat első két száma definíció szerint és . Az ez után következő szám (mert = ), majd következik (mert = ), és így tovább.
Az első 10 Fibonacci szám:
Az -dik Fibonacci számot generáló egyszerű rekurzív függvény így néz ki:
- Ha
0 vagy 1, a visszaadott érték - Ha nem, akkor a visszaadott érték
Ez az algoritmus a többszörös rekurzív hívás egy példája, mivel többször is meghívja önmagát. Könnyebben érthetővé válik a program többszörös hívása, ha a hívásokat egy fával ábrázoljuk.
Ha , a számítógép 15-ször hívja meg a függvényt:
Figyeld meg, hogy a fibonacci függvényt többszörösen meghívjuk 3, 2, 1 és 0 paraméterrel. Ahogy nő a bemenet, úgy csökken a hatékonyság.
fibonacci(30)
esetén a számítógép több, mint fél milliószor hívja meg fibonacci(2)
-t.Itt használhatjuk a megjegyzéses eljárást arra, hogy ne kelljen a számítógépnek újra és újra kiszámítani az egyszer már kiszámított értéket.
A rekurzív Fibonacci algoritmus megjegyzéses változata így néz ki:
- Ha
0 vagy 1, add vissza -t - Egyébként, ha
a táblázatban van, akkor a táblázatban az -hez tartozó értéket add vissza - Ha nincs a táblázatban,
- Számold ki
értékét - Tárold el az értéket a táblázatban
- Add vissza az eredményt
- Számold ki
Ha meg szeretnéd figyelni a megjegyzéses algoritmus JavaScriptben megírt programjának működését, nézd meg ezt a videót vagy futtasd a vizualizációt!
Ha , a számítógép 9 hívást fog elvégezni:
Az eredeti verzió 15 függvényhívást végzett, a megjegyzéses változat 6 hívást spórolt meg.
Ez a táblázat bemutatja a szükséges hívások számát -től -ig:
Eredeti | Megjegyzéses | |
---|---|---|
5 | 15 | 9 |
6 | 25 | 11 |
7 | 41 | 13 |
8 | 67 | 15 |
9 | 109 | 17 |
10 | 177 | 19 |
A szükséges függvényhívások száma exponenciálisan nő az eredeti algoritmusban, a megjegyzéses algoritmus esetén azonban sokkal lassabban nő.
A megjegyzéses algoritmusnak viszont nagyobb a tárigénye; tárhely kell minden -hez tartozó visszaadott értékhez.
Fordított megközelítés
Néha a rekurzív eljárás hatékonyságának növelésére az a legjobb módszer, ha nem használunk rekurziót.
Fibonacci számok generálása esetén a fordított megközelítéses iteratív technika időt és tárhelyet takarít meg. Fordított megközelítésben a számítógép először a részproblémákat oldja meg, és ezeket a részeredményeket felhasználva jut el a végeredményig.
A fordított eljárással generált Fibonacci szám algoritmusa így néz ki:
- Ha
0 vagy 1, add vissza -t - Egyébként
- Definiáld a
változót az érték megőrzéséhez, aminek a kezdeti értéke 0 - Definiáld a
változót az érték megőrzéséhez, kezdeti értéke legyen 1 - Definiáld a
változót a végeredmény tárolására, kezdeti értéke legyen 0 - Ismételd meg
-szer: értéke legyen és összege értéke legyen egyenlő értékével -ba másold át értékét- Add vissza
értékét
- Definiáld a
Ebben a megközelítésben nincs rekurzív hívás; itt iterációt használunk a részeredmények összeadásához és az eredmény kiszámításához.
Ha szeretnéd megfigyelni a fordított megközelítéses algoritmus JavaScriptben megírt programjának működését, nézd meg ezt a videót vagy futtasd a vizualizációt!
A fordított megközelítést alkalmazó algoritmus futási ideje ugyanúgy , mint a megjegyzésesé, de a szükséges tárkapacitás csak , mivel csak három számot kell megjegyeznie.
Dinamikus programozás
Mind a megjegyzéses, mind a fordított technika a dinamikus programozás eszköze, mely a matematikában és a számítástudomány területén alkalmazott probléma-megoldó technika.
Dinamikus programozást akkor használunk, amikor egy feladat optimális részstruktúrájú és átfedő részproblémákra bontható. Az optimális részstruktúra azt jelenti, hogy a feladat optimális megoldása elkészíthető a részfeladatok optimális megoldása alapján. Más szóval,
fib(5)
megoldható fib(4)
és fib(3)
segítségével. Átfedő részproblémákról akkor beszélünk, ha egy részproblémát többször is megoldunk, amint azt láthattuk, amikor fib(5)
kiszámításához többször is meghívtuk fib(3)
-t és fib(2)
-t.A dinamikus programozást számos probléma megoldására használhatjuk, és az itt megtanult technikákon kívül még más technikák is léteznek. Ha olyan feladattal találkozol, amelynek optimális részstruktúrája és átfedő részproblémái vannak, akkor gondolkodj el azon, hogy dinamikus programozási technikák jó megoldást tudnának-e nyújtani.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.