02 - if-else és rekurzió

Nézzük ezt a függvényt (mostantól már rendszerint nem fogom kiírni a Main objectet, ami eddig minden példában szerepelt) és egy meghívását:

def parosE(n: Int) = {
  if (n % 2 == 0) "Páros" else "Páratlan"
}
println(parosE(2))

Ha futtatjuk, kiíródik, hogy "Páros". Amit a függvény törzsében látunk: egy if-else kifejezés, szintaxisa $\mathrm{if}~(B)~E~\mathrm{else}~F$, ahol $E$ és $F$ kifejezések, $B$ pedig egy $\mathrm{Boolean}$ típusú kifejezés.

C-ben megszokhattuk, hogy az intek is jók ifbe, 0 hamis, többi igaz -- Scalában nem így megy, az if feltételébe $\mathrm{Boolean}$ kell menjen, az $\mathrm{if}( n\%2 )$ nem fordul. A százalék a C-ben megszokott módon a maradékos osztás maradékát adja eredményül, tehát pl. $n\%2$ a páros számokra $0$, a páratlanokra pedig $1$ lesz. Az if-else kifejezés kiértékelésének a szabályai:

• először kiértékeljük a feltételt, lesz belőle $\mathrm{true}$ vagy $\mathrm{false}$,
• ha $\mathrm{true}$, akkor a kifejezést $E$-re írjuk át, ha $\mathrm{false}$, akkor $F$-re,
• és folytatjuk a kiértékelést.

Tehát pl. most a $\mathrm{parosE}(2)$ hívásakor a substitution model szerint egy $\mathrm{if}( 2 \% 2 == 0 )$ "Páros" $\mathrm{else}$ "Páratlan", majd egy $\mathrm{if}( 0 == 0 )$  "Páros" $\mathrm{else}$ "Páratlan", majd egy $\mathrm{if}( \mathrm{true} )$ "Páros" $\mathrm{else}$ "Páratlan", végül a "Páros" string lesz a kifejezésünk, ez a legutóbbi lesz az értéke.

A típusról: az $\mathrm{if}(B)~E~\mathrm{else}~F$ kifejezés típusa az $E$ és $F$ kifejezések típusának "legspecifikusabb közös őse" lesz - erre még visszatérünk később, mindenesetre ha $E$ és $F$ típusa ugyanaz (mint most, mindkettő String), akkor ez a közös típus lesz az if-else kifejezés típusa is. Mivel pedig emiatt a fordító ki tudja következteni, hogy String a típusa a függvényünk törzsének, ezért nem kell megadnunk, hogy a függvény visszatérési értékének a típusa String lesz.

Amikor a fordító biztos, hogy nem tudja kikövetkeztetni a típust: ha rekurzív függvényt írunk (ami saját magát hívja meg, remélhetőleg más argumentumokkal). Erre a klasszikus példa a faktoriálist számító függvény szokott lenni, amit Scalában pl. így is implementálhatunk:

def fakt(n: Int ): Int = {
  if (n <= 1) 1 else n * fakt(n - 1)
}

Lássuk, mi történik, ha pl. kiértékeljük a $\mathrm{fakt}(5)$ kifejezést. Mostantól használni fogjuk a $\triangleright$ jelet is, amikor példa kiértékelünk: $E\triangleright F$ jelenti azt, hogy az $E$ kifejezést egy lépésben az $F$ kifejezésre írjuk át. Tehát a $\mathrm{fakt}(5)$ kifejezés kiértékelése:

$\begin{align*}\mathrm{fakt}(5)&\triangleright \mathrm{ if}(5 \leq 1)~1~\mathrm{else}~5\cdot \mathrm{fakt}(5-1)\\&\triangleright \mathrm{if}(\mathrm{false})~1~\mathrm{else}~5\cdot \mathrm{fakt}(5-1)\\&\triangleright 5\cdot\mathrm{fakt}(5-1)\\&\triangleright 5\cdot\mathrm{fakt}(4)\\&\triangleright 5\cdot \left(\mathrm{if}(4\leq 1)~1~\mathrm{else}~4\cdot \mathrm{fakt}(4-1)\right)\\&\triangleright 5\cdot\left(\mathrm{if}(\mathrm{false})~1~\mathrm{else}~4\cdot \mathrm{fakt}(4-1)\right)\\&\triangleright 5\cdot \left(4\cdot \mathrm{fakt}(4-1)\right)\\&\triangleright 5\cdot \left(4\cdot \mathrm{fakt}(3)\right)\\&\triangleright 5\cdot\left( 4\cdot \mathrm{if}(3\leq 1)~1~\mathrm{else}~3\cdot \mathrm{fakt}(3-1)\right)\\&\triangleright 5\cdot\left( 4\cdot \mathrm{if}(\mathrm{false})~1~\mathrm{else}~3\cdot \mathrm{fakt}(3-1)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \mathrm{fakt}(3-1)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \mathrm{fakt}(2)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \mathrm{if}(2\leq 1)~1~\mathrm{else}~2\cdot\mathrm{fakt}(2-1)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \mathrm{if}(\mathrm{false})~1~\mathrm{else}~2\cdot\mathrm{fakt}(2-1)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \left(2\cdot\mathrm{fakt}(2-1)\right)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \left(2\cdot\mathrm{fakt}(1)\right)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \left(2\cdot\mathrm{if}(1\leq 1)~1~\mathrm{else}~1\cdot\mathrm{fakt}(1-1)\right)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \left(2\cdot\mathrm{if}(\mathrm{true})~1~\mathrm{else}~1\cdot\mathrm{fakt}(1-1)\right)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \left(2\cdot 1\right)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot 2\right)\right)\\&\triangleright 5\cdot\left( 4\cdot 6\right)\\&\triangleright 5\cdot 24\\&\triangleright 120\end{align*}$

és így kapjuk meg végül, hogy $5!$ az bizony $120$.

Amire mindenképp fel kell figyelnünk ennél a kiértékelésnél: a kifejezés hossza egyre csak növekszik, az utolsó rekurzív hívásnál, ha $\mathrm{fakt}(n)$-t hívunk, egy $n$-nel arányos méretű kifejezéssel dolgozunk. Valójában persze a Scala ugyanúgy, mint a C vagy a Java, a függvényhívásokkor a "hívási verembe" (call stack) pusholja le az argumentumokat, és hogy hova kell majd visszaugrani a vezérlésnek, aztán átugrik a meghívott függvény belépési pontjára. Ha ott lesz még egy rekurzív hívás, további argumentumokat pushol a call stackre, majd még továbbiakat, így egy $n$ mélységű rekurziónál a call stack is $n$-nel arányos ütemben telik be - és ez azért rossz hír, mert a call stack alapból elég kicsi, néhány tízezernél nem fog tudni mélyebb hívást managelni, és ekkor dob egy $\mathrm{StackOverflowError}$t, ami miatt a JVM kilövi a programunk futását.

Ezzel valamit kezdenünk kell, mert a funkcionális programozás egyik alap építőköve az, hogy ciklusok helyett rekurzióban gondolkodunk (azt lehet immutable értékek mellett is, a ciklushoz meg well, kellene ciklusváltozó). Szerencsére van a rekurziónak egy olyan fajtája, amit "farokrekurziónak" (tail recursion) hívnak és ha sikerül így írjunk programot, akkor attól nem telik a call stack. Ez lesz a következő poszt témája.

folytköv