Kihagyás

04 - for ciklus rekurzióval

Visszatérve a korábbi kérdésre, egy for ciklust most már tudunk írni rekurzióval. Lássuk a tipikus C példánkat még egyszer:

1
2
3
for( int i = 0; i < 10; i++ ) {
  printf( "%d\n", i );
}
Ezzel ekvivalenst szeretnénk építeni Scalában (vagy egy másmilyen nyelven), ciklusváltozó nélkül. Mármost amit itt látunk, az az, hogy amikor belépünk a ciklus törzsébe, ott az i az egyetlen változónk, ami a ciklus törzsében nem változik meg, a következő iterációban pedig eggyel nagyobb i-re hívjuk a ciklusmagot, stb.

For ciklus valamettől tízig

Ez megoldható rekurzióval: csak írnunk kell egy függvényt, ami paraméterként megkapja i-t:

1
2
3
4
5
6
7
8
def printTizig( i: Int ): Unit = {
  if( i < 10 ) {
    println( i )
    printTizig( i+1 )
  } else ()
}

printTizig(0) //prints 0\n1\n2\n..\n9
Amit ebből a kódból érdemes hazavinnünk:

  • Ciklusban ,,végrehajtunk'' valamit, lényegében csak kifejezéseket értékelünk ki, az eredményeket (ha vannak) (most pl. tíz Unit típusú () érték potyog ki menet közben a println függvény kiértékelésekor) eldobjuk: ezért magának a ciklus kifejezésnek a típusa Unit lesz (kell neki egy típus)
  • az else () kódrészlet azért van ott, mert az if-else szerkezetnek része az, hogy ha a faltétel hamis, akkor is meg kell mondjuk, hogy mi legyen a kifejezés értéke; mindig kell, hogy legyen érték. Ha egy if-else kifejezésbe nem írunk else ágat, a fordító odagenerál egy else () végződést, ami vagy az, ami nekünk kell és jó lesz, vagy nem.

Tehát ez is ugyanaz, mint a fentebbi:

1
2
3
4
5
6
def printTizig( i: Int ): Unit = {
  if( i < 10 ) {
    println( i )
    printTizig( i+1 )
  }
}
Nézzük is meg, hogy mi történik, ha mondjuk printTizig(7)-tel hívjuk a függvényt:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
printTizig(7)  if( 7 < 10 ) { println(7); printTizig(7+1) } else ()
//ha több kifejezést teszünk egy sorba, akkor kell kirakjuk a pontosvesszőt
//most kiraktam, hogy az aktuális kifejezésünk mindig egy sorban legyen
    if( true ) { println(7); printTizig(7+1) } else ()
    println(7); printTizig(7+1)
    (); printTizig(7+1) //közben kiírtuk, hogy 7, és visszakaptuk a () értéket
    printTizig(7+1)     //ha több kifejezés van egymás után és az első már érték, eldobjuk
    printTizig(8)       //call-by-value
    if( 8<10 ) { println(8); printTizig(8+1) } else ()
    if( true ) { println(8); printTizig(8+1) } else ()
    println(8); printTizig(8+1)
    (); printTizig(8+1) //közben kiírtuk, hogy 8
    printTizig(9)       //első kifejezés már érték, van tovább, eldobjuk
    if( 9<10 ) { println(9); printTizig(9+1) } else ()  //függvény subst
    if( true ) { println(9); printTizig(9+1) } else ()  //feltétel kiértékelés
    println(9); printTizig(9+1)  //if(true) E1 else E2 ▹ E1
    (); printTizig(9+1) //kiírtuk közben, hogy 9
    printTizig(9+1)     //() eldobva
    if( 10<10 ) { println(10); printTizig(10+1) } else () //wait for it
    if( false ) { println(10); printTizig(10+1) } else () //feltétel false
    () //és kész, ez a for ,,kifejezés'' értéke
Érdemes megfigyelni ebből a futásból, hogy az elméleti modellben, ami szerint kifejtjük a ▹-gel jelölt operatív szemantika mentén a kifejezést, nem telik a stack ennek a konstrukciónak az esetén! Azért is hívtuk 7-tól. Ha visszanézünk a faktoriális példánkra, ott látszott, hogy középtájon ,,meghízott'' a kifejezés mérete (és minél nagyobb n-re hívnánk a függvényt, annál jobban meghízna), itt ebben a példánkban egy állandó hossza volt minden iterációban. Ez jobb.

For ciklus valamettől valameddig

Persze a fenti kódban az, hogy konstans 10-ig el tudunk menni, az nem túl hasznos, de egy kis módosítással persze a felső korlátot is tudjuk kezelni - csak át kell adjuk paraméterként azt is:

1
2
3
4
5
6
def myForLoop(from: Int, to: Int): Unit = {
  if( from < to ) {
    println(from)
    myForLoop(from+1, to)
  } //implicite itt az else ()
}
Van pár probléma ezzel a megközelítéssel még:

  • egyelőre csak println-olni tudunk, ha mást kéne csinálni a ciklusváltozóval, akkor azt azért mégiscsak el kéne kerülni, hogy ilyen mintára el kelljen készítsünk egy csomó másik függvényt, ahányszor csak egy for ,,ciklusra'' lenne szükségünk
  • a from ciklus,,változó''t is beégetve mindenképp eggyel növeljük, ezt is jó volna customizálni anélkül, hogy minden use case-re egy újabb és újabb függvényt kéne implementálnunk

Ezeket meg fogjuk később oldani, mikor függvény típust is átadunk paraméterként.

Kérdések, feladatok

  • Értékeld ki az operatív szemantika szerint a myForLoop(1,4)-et!
  • Meg tudnád-e fogalmazni, hogy mi lehet a különbség a faktoriális és a forciklus rekurziói közt, hogy az előbbi egyre inkább töltötte a stacket, az utóbbi pedig nem?

Utolsó frissítés: 2021-02-07 23:06:47