05 - tail recursion¶
Mondjuk, szeretnénk írni olyan függvényt, ami ciklusban összeadja az első n
pozitív egész
számot (visszaadhatnánk persze csak simán a számtani összegképletből jövő n*(n+1)/2
értéket
is, de most a ciklussal kapcsolatos problémákkal szeretnénk foglalkozni).
Rekurzió és a call stack¶
Az első ötlet az előző poszt alapján lehet kb. ilyen:
1 2 3 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|
- azért tesszük ki függvényhívásnál mindig a kapcsost, és oldjuk fel csak akkor, mikor már egy érték van benne,
mert ez így jól modellezi azt, hogy valójában ,,mi is történik'' függvényhíváskor: például látja mindenki,
hogy az
5 + { 4 + sum(3) }
kifejezést nem tudjuk átírni9 + sum(3)
-ra, mert a függvény kiértékelése a kapcsoson belül még zajlik. - Aggasztóan hízik a függvénykifejezés mérete.
Hihetnénk persze azt, hogy ez csak papíron van így, de ha megpróbáljuk kiprintelni sum(20000)
-et:
A függvényhívások ilyen mélységű egymásba ágyazása az, amit a call stack már nem bír el. Persze meg lehet növelni JVM argumentummal, de az nem megoldás, alapvetően egy több tízezres mélységű rekurzív hívás olyasmi, amit mindenképp el szeretnénk kerülni.
Itt jön be a képbe a tail call optimization, amit már tulajdonképpen láttunk is.
Tail call optimization, tailrec¶
Egy rekurzív függvényhívást tail pozíción lévő hívásnak mondunk, ha a hívás értékével eztán már nem csinálunk semmit:
imperatív nyelven (java, C stb) ez annyit tesz, hogy return f(...);
-fel egyből visszaadjuk, funkcionális nyelven meg
kb. azt, hogy se nem helyettesítjük be függvénybe, se nem jön utána további kifejezés-kiértékelés. Maga a függvény
tail rekurzív akkor, ha rekurzív és az összes rekurzív hívása tail pozin van.
A sum
függvényünk előző implementációja nem ilyen, mert a kifejezés értéke az egyik szálon n+sum(n-1)
lesz, azaz miután
kiértékeltük rekurzívan a függvényt, még az értékkel csinálunk valamit.
Viszont pl. a for ciklusunk implementációja ilyen volt: a rekurzív hívás, printTizig( i+1 )
, az utolsó kifejezés volt a
szálon, nem követte semmi. Coincidentally, az nem is töltötte a stacket, legalábbis papíron.
Ha egy rekurzív hívás tail call, akkor a fordítónak alkalma van optimalizálni, és nem generálni függvényhívást: egyszerűen csak be kell állítani az argumentumokat az aktuális függvényük példányában a memóriában arra, amivel most hívnánk, és csak ,,gotozni'' a függvény elejére.
Ennek a módszernek, amit tail call optimizationnak hívnak, vannak persze előnyei és hátrányai:
- előny: nem tölti a stacket, és valamivel gyorsabb is, hiszen nem kell újrafoglalni memóriát a lokális változóknak, eltárolni a visszatérési címet stb
- hátrány: nehezebb debugolni, ha arra lenne szükségünk, hogy melyik ,,föntebbi'' példányában a függvénynek mi az ottani lokális változók értéke, azt nem tudjuk előbányászni, mert felülírtuk őket.
Egy pure funkcionális programozási nyelvben alapelem a nagy mélységű rekurzió, ezért az ilyen nyelvek általában támogatják a tail call optimalizálást; a Scala is. (A Java egyébként nem, ott tail recursive függvények is simán dobnak egy stacktracet, ha túl mély a rekurzió.) Persze ehhez tail recursive alakra kell átalakítsuk a függvényünket, ami vagy sikerül, vagy nem. Nézzük meg pl. az összegző függvényt tail rekurzívan:
1 2 3 4 5 6 7 8 |
|
- van benne function overloading: nevezhetünk el ugyanúgy két függvényt, ha a paraméterlistájuk különbözik. (vagy a paraméterek száma, vagy ha az egyenlő, akkor valahanyadik paraméter típusa eltér)
Hogy megértsük, hogyan működik, próbáljuk kiértékelni a tailSum(5)
-öt ismét:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
Amiért pedig ez jó függvény lesz: azt lehet bebizonyítani indukcióval, hogy tailSum(n,s) = s + 1 + 2 + ... + n
lesz minden s,n >= 0
egészek
esetén. Ezt a következő posztban meg is nézzük, hogy ne legyen ez hosszú.
Kérdések, feladatok¶
- Ellenőrizzük, hogy a tail recursive for loop implementációnk tényleg nem tölti a stacket: írassuk ki vele mondjuk 1-től 20.000-ig a számokat!
- Mi történik, ha a loop függvényünket meghívjuk? Miért? Próbáljuk ki, hogy Javában mi a helyzet egy ugyanilyen sémára épülő függénnyel.