If you're seeing this message, it means we're having trouble loading external resources on our website.

Ha webszűrőt használsz, győződj meg róla, hogy a *.kastatic.org és a *.kasandbox.org nincsenek blokkolva.

Fő tartalom

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!
programsorRekurzí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 n = 0, adj vissza 1-et!
  • Ha nem, és n benne van a táblázatban, add vissza az n-hez tartozó értéket!
  • Ha nincs a táblázatban,
    • Számítsd ki (n1)!n-t!
    • Tárold el az eredményt a táblázatban!
    • Add vissza az eredményt!
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 O(1) 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:
ProgramsorRekurzí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 0 és 1. Az ez után következő szám 1 (mert = 0+1), majd 2 következik (mert = 1+1), és így tovább.
Az első 10 Fibonacci szám:
0,1,1,2,3,5,8,13,21,34
Az n-dik Fibonacci számot generáló egyszerű rekurzív függvény így néz ki:
  • Ha n 0 vagy 1, a visszaadott érték n
  • Ha nem, akkor a visszaadott érték fibonacci(n1)+fibonacci(n2)
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 n=5, a számítógép 15-ször hívja meg a függvényt:
Khan Academy video wrapper
Recursive Fibonacci Calls (Diagrammed)Videóátirat megtekintése
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 n 0 vagy 1, add vissza n-t
  • Egyébként, ha n a táblázatban van, akkor a táblázatban az n-hez tartozó értéket add vissza
  • Ha nincs a táblázatban,
    • Számold ki fibonacci(n1)+fibonacci(n2) értékét
    • Tárold el az értéket a táblázatban
    • Add vissza az eredményt
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 n=5, a számítógép 9 hívást fog elvégezni:
Khan Academy video wrapper
Memoized Recursive Fibonacci Calls (Diagrammed)Videóátirat megtekintése
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 n=5-től n=10-ig:
nEredetiMegjegyzéses
5159
62511
74113
86715
910917
1017719
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 n-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 n 0 vagy 1, add vissza n-t
  • Egyébként
    • Definiáld a twoBehind változót az (n2) érték megőrzéséhez, aminek a kezdeti értéke 0
    • Definiáld a oneBehind változót az (n1) érték megőrzéséhez, kezdeti értéke legyen 1
    • Definiáld a result változót a végeredmény tárolására, kezdeti értéke legyen 0
    • Ismételd meg (n1)-szer:
      • result értéke legyen twoBehind és oneBehind összege
      • twoBehind értéke legyen egyenlő oneBehind értékével
      • oneBehind-ba másold át result értékét
      • Add vissza result értékét
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 O(n), mint a megjegyzésesé, de a szükséges tárkapacitás csak O(1), 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.
Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.