07 - imperatív for ciklusok átírása tail recursive függvényekké

Az előző összegző függvényünk most már tudjuk, hogy helyes és láttuk, hogy a Scalás implementáció tényleg nem tölti a stacket. A kérdés az, hogy hogyan tudunk készíteni ilyen függvényeket?

Valamiből persze ki kell indulni, nincs általános megoldó gép, de egy példán keresztül megnézzük, hogy ha pl. C-ben tudnánk valamire egy for ciklust írni, akkor abból hogyan lehet ,,automatikusan'' transzformálni egy tail rekurzív függvényt.

Vegyük megint az összegzést: adjuk össze a számokat n-től m-ig C-ben:

int sum(int n, int m) {
  int s = 0;
  for( int i = n; i <= m; i++ ) s+=i;
  return s;
}

Mondjuk, egy ilyet meg tudnánk írni C-ben, és az a kérdés, hogy lesz ebből tail rekurzív kód. Konkrétabban a ciklus részéből. Nem kell mást tennünk, mint

• kigyűjteni minden változót, melyet a ciklusban látunk,
• írni egy olyan (rekurzív) függvényt, ami ezeket mindet megkapja paraméterként,
• a rekurzív hívásban pedig a következő iterációnak megfelelően módosítjuk az értékeket.

Konkrétabban: itt a for ciklus, amit rekurzióval akarunk kódolni, látja az i, n, m és s változókat (a ciklusváltozó is számít, a feltételekben szereplő és használt változók is, meg minden ,,kintebb'' deklarált változó is, melyet akár írunk, akár olvasunk). Tehát ebből első körben készíthetünk egy négyváltozós függvényfejlécet:

def sum(i: Int, n: Int, m: Int, s: Int): Int = ???

A visszatérési értéken elmélázunk majd kicsit később, hogy mi is kéne legyen a típusa, most legyen az a szándékunk, hogy a ciklust ,,implementáló'' függvényünk adja vissza az s értékét.

A ciklus inicializálásával nem kell ekkor még foglalkoznunk, majd úgy hívjuk meg a függvényt, hogy jó legyen; a feltétellel kell foglalkoznunk - ha a feltétel hamis, akkor állunk meg, és ekkor vissza kell adjuk az eredményt, ami, hát az s ,,változó'' értéke ebben az esetben:

def sum(i: Int, n: Int, m: Int, s: Int): Int = {
  if( i > m ) s else ???
}

Alakul, ha a feltétel hamis, visszaadjuk az s értékét, amibe elvileg legyűjtöttük az összeget. Különben mit is kell tennünk? Ha a ciklusmagban, amit szimulálunk éppen, van valami mellékhatás, amit szeretnénk is elvégezni, tegyük meg (most nincs; korábban a kiíratásnál volt egy printf-ünk) aztán hívjuk rekurzívan a függvényünket úgy, hogy aktualizáljuk az i (eggyel nő), n, m (nem változnak), s értékeket (ez a legutóbbi meg i-vel nő, hiszen az utasítás az eredeti C kódban s+=i volt). Presto:

def sum(i: Int, n: Int, m: Int, s: Int): Int = {
  if( i > m ) s else sum(i+1, n, m, s+i)
}

Az eredeti függvényünk persze nem kapta meg sem az i-t, sem az s-et, ez a kód még csak a ciklust ,,szimulálja''; ebből úgy lesz egy n-t és m-et kapó függvényünk, hogy beleégetjük a két értékadást, ami a C kódban eredetileg szerepelt a ciklusmagba első belépés előtt: az s = 0; értékadás a kódban és az int i = n értékadás a ciklus inicializálásában:

def sum(n: Int, m: Int): Int = sum(n, n, m, 0)

Tulajdonképpen kész is vagyunk. Persze ezek után optimalizálhatunk is a kódon. Ha jobban megnézzük, az n paramétert nem is használjuk semmire a kódban, csak változtatás nélkül átadjuk a következő hívásnak - ennek nincs haszna, törölhetjük is a négyváltozós függvényünk második paraméterét:

def sum(i: Int, m: Int, s: Int): Int = {
  if( i > m ) s else sum(i+1, m, s+i)
}
def sum(n: Int, m: Int): Int = sum(n, m, 0)

Persze a második kódban még látunk egy n-t, ő az i=n inicializálásból származik.

Kérdések, feladatok

• Számoljuk végig az operatív szemantikával, hogy a sum függvény fenti rekurzív implementációi tényleg helyes értékeket adnak pl. az n=2, m=4 esetre!
• Igazoljuk is formálisan, hogy a sum(i,n,m,s) függvény az s + i + (i+1) + ... + m intre értékelődik ki!
• Hajtsuk végre a printelő for cikluson is ugyanezt az átalakítást.
• Hajtsuk végre a következő C kódon, ami szintén az első n pozitív egész szám összegét számítja ki, ezt az átalakítást:

int sum(int n) {
  int s = 0;
  for( int i = n; i > 0; i-- ) s += i;
  return s;
}

Hasonlítsuk össze a kapott kódot az első tailrec összegző függvényünkkel.

---

Utolsó frissítés: 2020-12-23 19:43:13