Tämä kurssi on jo päättynyt.

Kurssin viimeisimmän version löydät täältä: O1: 2024

  1. CS-A1110
  2. Kierros 11
  3. Luku 11.2: Rekursio

Luku 11.2: Rekursio

Tästä sivusta:

Pääkysymyksiä: Mitä jos funktio kutsuu itseään? Ja miksi kutsuisi?

Mitä käsitellään? Rekursiivisesti määritelty eli itseensä viittava tieto. Rekursio funktioiden toteutustekniikkana. Sivuamme myös algoritmien tehokkuutta.

Mitä tehdään? Useita tehtäviä ja varsin paljon luettavaa.

Suuntaa antava työläysarvio:? Noin neljä tuntia.

Pistearvo: C95.

Oheisprojektit: Recursion (uusi), Viinaharava.

../_images/person07.png

Johdanto

Ikivanha vitsi

rekursio (substantiivi): Katso rekursio.

Rekursion (recursion) perusajatus on, että jokin asia määritellään asian itsensä kautta. Tässä luvussa viittaamme sanalla eritoten siihen, että funktio voidaan määritellä kutsumaan itseään.

Tällainen rekursio on ohjelmointitekniikkana paljon monipuolisempi kuin ensi kuulemalta tulee mieleenkään, mitä voimme havainnollistaa vaikkapa sijoittamalla sen luvun 6.2 kaavioon:

Rekursio on monisyinen aihe, jota voi tarkastella eri näkökulmista. Tässä luvussa se näyttäytyy ennen muuta funktioiden toteutustekniikkana, joka perustuu kutsupinon kehyksiin ja jota voi käyttää toistokäskyjen (silmukoiden) asemesta; toistokäskyjen käyttöön viittaamme termillä iteraatio.

Rekursiivisia funktioita käytetään useimmissa ohjelmoinnin valtaparadigmoissa: imperatiivisessa, funktionaalisessa ja olio-ohjelmoinnissa (luku 10.2). Mainituista paradigmoista rekursion käyttö on erityisen runsasta funktionaalisessa ohjelmoinnissa.

Aloitetaan rekursion muodosta, joka on monen mielestä helpoin ymmärtää:

Rakenteellinen rekursio

Ei ole harvinaista, että tietotyypin määrittelyssä viitataan tietotyyppiin itseensä. Esimerkiksi:

  • Kurssilla voi olla esitietokurssi, joka on myös kurssi(olio).
  • Työntekijällä voi olla alaisia, jotka ovat myös työntekijöitä.
  • Pelialueella voi olla naapureita, jotka ovat myös alueita (tekstipeli; luku 9.1).

Voimme kutsua tällaista nimellä rakenteellinen rekursio (structural recursion). Rakenteellisesti rekursiivisessa olio-ohjelmassa keskenään samantyyppiset oliot sisältävät viittauksia toisiinsa ja muodostavat näin esitietoketjun, yrityksen henkilöstöpuun, alueiden verkoston tai muun vastaavan rakenteen.

Osoittautuu, että rakenteellisen rekursion yhteyteen sopivat usein itseään kutsuvat rekursiiviset metodit.

Esimerkki: kurssien esitietoja

Ajatellaan tilannetta, jossa kursseja on mallinnettu olioina, joilla kullakin on oma opintopistemääränsä. Lisäksi kursseilla voi olla esitietoja. Oletetaan esimerkin yksinkertaistamiseksi, että kurssilla ei voi olla välittömänä esitietonaan yli yhtä kurssia.

Olkoon kurssioliolla metodi kokonaisOp, joka selvittää kurssin "kokonaisopintopistemäärän" eli opintopistemäärän, johon on laskettu mukaan paitsi kurssin oma pistemäärä myös kaikkien kurssin esitietojen pistemäärä eli kurssin oman esitiedon pisteet plus esitiedon esitiedon pisteet, jne.

Tämän metodin suoritus voidaan ajatella toisiinsa liittyvien kurssiolioiden keskinäisenä viestintänä. Tutkitaan asiaa ensin samanlaisen pallurakaavion avulla, joita aiemminkin käytimme olioiden havainnollistamiseen:

Sama Scalalla

Oletetaan, että meillä on kursseja yleisesti kuvaava abstrakti luokka Kurssi ja sen kaksi aliluokkaa Johdantokurssi ja Jatkokurssi. Johdantokurssilla ei ole esitietovaatimuksia. Jatkokurssilla on tässä tasan yksi välitön esitietokurssi.

Luokista voi luoda ilmentymiä esimerkiksi näin:

val johdOp = new Johdantokurssi("Johdatus opiskeluun", 2)johdOp: o1.kurssi.Johdantokurssi = Johdatus opiskeluun (2op)
val ohj1 = new Jatkokurssi("Ohjelmointi 1", 5, johdOp)ohj1: o1.kurssi.Jatkokurssi = Ohjelmointi 1 (5op)
val ohj2 = new Jatkokurssi("Ohjelmointi 2", 5, ohj1)ohj2: o1.kurssi.Jatkokurssi = Ohjelmointi 2 (5op)
val trak = new Jatkokurssi("Tietorakenteet ja algoritmit", 5, ohj2)trak: o1.kurssi.Jatkokurssi = Tietorakenteet ja algoritmit (5op)
val kannat = new Jatkokurssi("Tietokannat", 5, ohj1)kannat: o1.kurssi.Jatkokurssi = Tietokannat (5op)

kokonaisOp-metodin pitäisi toimia näin:

johdOp.kokonaisOpres0: Int = 2
kannat.kokonaisOpres1: Int = 12
trak.kokonaisOpres2: Int = 17

Tässä toteutus yliluokalle Kurssi:

abstract class Kurssi(val nimi: String, val op: Int) {

  def kokonaisOp: Int

  override def toString = this.nimi + " (" + this.op + "op)"

}
Abstraktin metodin kokonaisOp toteutusta ei ole määritelty kursseille yleisesti. Aliluokat toteuttavat sen eri tavoin.

Johdantokurssi on kurssiluokan äärimmäisen yksinkertainen aliluokka. Johdantokurssiolion ei tarvitse ihmeemmin selvitellä esitietojensa pistemäärää, koska esitietoja ei ole. Se voi vain palauttaa oman opintopistemääränsä:

class Johdantokurssi(nimi: String, op: Int) extends Kurssi(nimi, op) {

  def kokonaisOp = this.op

}

Monimutkainen ei ole jatkokurssiluokkakaan. Jatkokurssiolion kokonaisOp-algoritmin voi ilmaista suomeksi hyvin yksinkertaisesti: "Laske yhteen esitietokurssisi kokonaispisteet ja omat pisteesi." Käyttämällä rekursiota voi tämän kääntää suoraan Scalaksi:

class Jatkokurssi(nimi: String, op: Int, val esitieto: Kurssi) extends Kurssi(nimi, op) {

  def kokonaisOp = this.esitieto.kokonaisOp + this.op

}
kokonaisOp-metodin toteutuksessa on rekursiivinen metodikutsu: kutsutaan juuri samaista kokonaisOp-metodia.

Rekursion toiminta

Taikuuttako?

Joskus rekursiivisista metoditoteutuksista tulee niin yksinkertaisia ja elegantteja (verrattuna esimerkiksi vastaaviin toistokäskyihin), että ne voivat näyttää lähes yliluonnollisilta. Pidetään kuitenkin jalat maassa.

Rekursiivisen metodin koodi voi olla petollisen lyhyt. Vaikkapa kokonaisOp-metodin viaton summalauseke aiheuttaa kurssiolioiden välisen viestinnän ja yhteenlaskennan toistumisen kunkin olion kohdalla. Nämä suoritusvaiheet eivät näy suoraan koodista, vaan niiden hahmottaminen jää ohjelmoijan mielessään tehtäväksi.

Rekursiivisen ohjelman muodostamiseen ei tarvita mitään uusia ohjelmointikielen käskyjä. Se tapahtuu ihan tavallisia metodikutsuja käyttäen. Tämä näkyy hyvin äskeisestä animaatiosta, jossa uutta on ainoastaan se, että kutsupinossa on päällekkäin useita samaan metodiin liittyviä kehyksiä (kohdistuen eri olioihin eli käyttäen eriarvoisia this-muuttujia).

Jo kurssin alussa näit, että metodit voivat kutsua toisiaan. Kun metodi A kutsuu metodia B, niin A jää odottamaan, että B lopettaa toimintansa. Tämän jälkeen A jatkaa siitä mihin jäi. Rekursiiviset metodikutsut toimivat täsmälleen samoin. Erona on vain se, että metodi kutsuu itseään, ja yhdestä metodista on yhtaikaisesti kesken useita suorituskertoja.

Kunhan ymmärrät, miten metodikutsut toimivat kutsupinossa, pystyt järkeilemään myös, miten rekursiivinen ohjelma vaiheittain toimii.

Rekursio ilman rekursiivista rakennetta

Esimerkki: palindromit

Tutkitaan funktiolla, onko annettu merkkijono palindromi eli samanlainen etu- ja takaperin.

onPalindromi("saippuakauppias")res3: Boolean = true
onPalindromi("saapas")res4: Boolean = false

Metodin voi toteuttaa silmukkaa käyttämällä (siis iteraatiolla) tai rekursiolla. Laaditaan vertailun vuoksi molemmanlaiset toteutukset.

Palindromeista

Tässä luvussa laadittavat onPalindromi-metodit vaativat, että myös välilyönnit ja -merkit menevät täsmälleen samoin etu- ja takaperin. Tätähän ei yleensä palindromeilla sanaillessa edellytetä. Jos haluat, niin löydät Recursion-projektista myös metodiversion, joka huomioi vain kirjaimet. Sitä emme käsittele tässä tarkemmin, koska se ei tuo lisäarvoa rekursion opetteluun.

Palindromit iteraatiolla

Tässä eräs palindromiudenselvittämisalgoritmi pseudokoodina:

def onPalindromi(merkkijono: String): Boolean = {
  Käy merkkijonoa yhtaikaa alusta ja lopusta läpi, merkkipari kerrallaan.
  Jokaisen merkkiparin kohdalla:
    1. Jos merkit ovat erilaiset, ei kyseessä ole palindromi ja voidaan lopettaa.
    2. Jos kaikki merkkiparit käytiin läpi, on kyseessä palindromi.
        (Jos merkkejä oli pariton määrä, voi keskimmäisen jättää huomiotta.)
}

Tarkennettu versio:

def onPalindromi(merkkijono: String): Boolean = {
  Askeltajamuuttuja alkuindeksi on aluksi 0, ja loppuindeksi on merkkijonon pituus miinus yksi.
  Toistetaan alkuindeksiä aina yhdellä kasvattaen ja loppuindeksiä aina yhdellä vähentäen niin
  kauan kuin alkuindeksi pysyy loppuindeksiä pienempänä. Kullakin kierroksella:
    1. Katsotaan merkkijonosta merkit kohdista alkuindeksi ja loppuindeksi.
    2. Jos ne ovat erilaiset, palautetaan false ja lopetetaan metodin suorittaminen.
  Jos kaikki merkkiparit käytiin läpi (eikä siis palautettu false), niin palautetaan true.
}

Tämä iteratiivinen algoritmi perustuu ajatukseen toimenpiteiden toistamisesta yhden metodikutsun aikana, kunnes tietty ehto lakkaa olemasta voimassa kasvavan alkuindeksin ja vähenevän loppuindeksin kohdatessa. while-toistokäskyä käyttäen algoritmi kirjoittuu suoraan Scalaksi:

def onPalindromi(merkkijono: String): Boolean = {
  var alkuindeksi = 0
  var loppuindeksi = merkkijono.length - 1
  while (alkuindeksi < loppuindeksi) {
    if (merkkijono(alkuindeksi) != merkkijono(loppuindeksi)) {
      return false
    }
    alkuindeksi += 1
    loppuindeksi -= 1
  }
  true
}
Muista luvusta 8.3: funktioon voi kirjoittaa return-käskyn, joka päättää funktion suorituksen välittömästi ja palauttaa return-sanan perään kirjoitetun lausekkeen arvon. Tässä siis katkaistaan silmukan suoritus siihen paikkaan, jos havaitaan erilaiset merkit. (Jatkaminen on tällöin turhaa.)
Kuten luvussa 8.3 myös jo todettiin, Scalassa on aina return-käskyä käytettäessä kirjoitettava metodille palautusarvon tyyppi erikseen.
true päädytään palauttamaan vain siinä tapauksessa, että silmukan sisältä ei palautettu arvoa false.

Palindromit rekursiolla

Tässä toinen pseudokoodialgoritmi palindromiuden selvittämiseen:

def onPalindromi(merkkijono: String): Boolean = {
  Mikä tahansa nollan tai yhden merkin mittainen merkkijono on palindromi.
  Merkkijono, jonka ensimmäinen ja viimeinen merkki ovat erilaiset, ei ole palindromi.
  Muissa tapauksissa merkkijono on palindromi, jos ja vain jos:
    - Se pienempi merkkijono, joka saadaan poistamalla merkkijonosta ensimmäinen
      ja viimeinen kirjain, on palindromi.
}

Huomaa:

  • Tämä pseudokoodi ei kuvaa toistettavia käskyjä ja suoritusvaiheita suoraan. Se on enemmänkin kuvaus siitä, mikä palindromi on. (Tällaista määrittelyä voi sanoa deklaratiiviseksi.)
  • Esitetty määritelmä on rekursiivinen: se viittaa viimeisessä kohdassa itseensä.

Tämänkin ratkaisumallin voi kyllä kirjoittaa myös "käskymuotoon":

def onPalindromi(merkkijono: String): Boolean = {
  Jos merkkijonon pituus on 0 tai 1, palauta true.
  Muuten jos merkkijonon ensimmäinen ja viimeinen merkki ovat erilaiset, palauta false.
  Muissa tapauksissa ota jonon keskiosa, josta puuttuvat ensimmäinen ja viimeinen merkki,
    selvitä rekursiivisella metodikutsulla, onko keskiosa palindromi, ja
    palauta sama totuusarvo, jonka rekursiivinen kutsukin palautti.
}

Sama Scalalla:

def onPalindromi(merkkijono: String): Boolean = {
  if (merkkijono.length <= 1)
    true
  else if (merkkijono.head != merkkijono.last)
    false
  else
    onPalindromi(merkkijono.substring(1, merkkijono.length - 1))
}
Funktiossa on kaksi perustapausta (base case) eli tapausta, jossa tulos saadaan ilman rekursiivista kutsua. (Vrt. esitiedoton johdantokurssi edellisessä esimerkissä.)
Merkkijono-olioiden head-metodilla saadaan ensimmäinen merkki (luku 4.5), last-metodilla vastaavasti viimeinen.
Funktiossa on yksi rekursiivinen "haara", jossa se kutsuu itseään eri parametriarvolla. Funktio huolehtii itse rekursiivisen kutsun parametriarvoksi sopivan merkkijono-olion muodostamisesta.
Huom. Tällekin onPalindromi-toteutukselle on pakko kirjata erikseen palautusarvon tyyppi. Palautusarvon tyyppi nimittäin pitää Scalassa kirjata myös rekursiivisille metodeille.

Tutustu animaatioon funktion toiminnasta:

Kuten animaatiosta näit, samaa algoritmia sovelletaan kussakin kehyksessä eri parametriarvoon. Nämä arvot ovat algoritmin itsensä muodostamia: algoritmiin kuuluu, että substring-käskyllä muodostetaan uusi merkkijono ja sovelletaan algoritmia siihen. Merkkijonoilla ei lähtökohtaisesti ole rekursiivista rakennetta, mutta algoritmi luo uusia merkkijonoja — pienempiä ongelmia — ja soveltaa itseään niihin.

Olettaen, että ohjelma toimii animaatiossa esitetyllä tavalla, montako onPalindromi-kutsuun liittyvää kehystä tulee luoduksi kutsupinoon, kun suoritetaan käsky onPalindromi("imaami") ?
Entä kutsuttaessa onPalindromi("avustava") ?

Entäs reverse?

Eikö merkkijonoilla ole myös reverse-metodi, jota olisi voinut käyttää?

Totta. Yllä kätevästi unohdimme tämän, jotta pääsimme vertaamaan iteratiivista ja rekursiivista toteutustapaa. Koodiltaan tiiviimmän ja palindromien olemusta suoraan heijastavan ratkaisun olisi saanut näinkin:

def onPalindromi(merkkijono: String) = merkkijono == merkkijono.reverse

Huomaa kuitenkin: reverse ei ole varsinaisesti vaihtoehto iteraatiolle ja rekursiolle vaan korkeamman abstraktiotason työkalu spesifisempään tarkoitukseen (eli varsin korkealla luvun alun kaaviossa). Nurinpäinkääntämismetodin itsensä voi toteuttaa joko iteraatiolla tai rekursiolla.

Vaikka tällä kertaa sattui olemaan tarjolla korkeamman tason työkalu ongelman ratkaisemiseen, näin ei aina ole.

Toistokäskyt vs. rekursio

Rekursion hyödyntäminen ei siis edellytä rakenteellista rekursiota. Minkä tahansa iteratiivisesti ratkaistavissa olevan ohjelmointiongelman voi ratkaista myös rekursiivisesti — ja toisin päin. Eroja on ratkaisujen kirjoittamisen helppoudessa, luettavuudessa ja tehokkuudessa. Riippuu ongelmasta, käytetyistä työkaluista ja myös ohjelman lukijasta, onko iteratiivinen vai rekursiivinen ratkaisu parempi.

Seuraavassa taulukossa on nostettu esille eräitä iteratiivisten ja rekursiivisten ratkaisujen ominaispiirteitä.

  Toistokäsky Rekursio
Eteneminen:

Käydään ongelma läpi toistamalla jotakin toimenpidettä. Kukin toistokerta jatkaa siitä, mihin edellinen jäi.

Esimerkki: toistetaan kirjainparien tarkastamiskäskyjä ja seuraavaan pariin siirtymistä kullekin merkkijonon osalle.

Esimerkki: toistetaan opintopistemäärän katsomista ja summaamista sekä seuraavaan kurssiin siirtymistä kullekin esitietoketjun kurssille.

Lohkaistaan ongelmasta pieni helposti ratkeava pala pois ja sovelletaan samaa algoritmia näin pienennetylle ongelmalle.

Esimerkki: Otetaan ensimmäinen ja viimeinen merkki (osa ongelmasta, jonka osalta vastaus on helppo selvittää). Sovelletaan samaa algoritmia merkkijonon keskiosaan (pienennetty ongelma).

Esimerkki: otetaan kurssin omat opintopisteet (osa ongelmasta) ja sovelletaan samaa algoritmia esitietoketjuun (pienennetty ongelma).
Muuttujista:

Käytetään tarvittaessa myös var-muuttujia ja muuttuvatilaisia kokoelmia tilakirjanpitoon.

Esimerkki: pidetään kirjainparien indeksit askeltajamuuttujissa.

Esimerkki: Pidetään var-muuttujassa tieto siitä, mitä esitietoketjun kurssia parhaillaan käsitellään. Vaihdetaan tämä kurssi sen esitietoon joka kierroksella. Käytetään toista muuttujaa kokoojana, johon päivitetään pistesummaa sitä mukaa kuin kursseja käydään läpi.

Parametreilla ja muilla paikallisilla val-muuttujilla pärjää.

Esimerkki: tieto käsittelemättä olevasta osamerkkijonosta välittyy parametriksi seuraavaan, ylempään kehykseen.

Esimerkki: Käsiteltävät kurssit ovat kunkin kehyksen erillisissä this-muuttujissa. Välituloksiksi saadut pistesummat ovat myös tallessa eri kehyksissä; minkään muuttujan arvoa ei tarvitse vaihtaa.
Lopettaminen:

Päätetään toisto, kun on saatu valmista.

Esimerkki: poistutaan silmukasta, kun alusta päin kasvatettu ja lopusta vähennetty indeksi kohtaavat.

Esimerkki: poistutaan silmukasta, kun käsiteltävällä kurssilla ei ole esitietoa.

Kun ongelmaksi on jäänyt enää pieni murunen alkuperäisestä (perustapaus), on sen ratkaisu ilmeinen eikä tarvita enää rekursiivista kutsua.

Esimerkki: jos kyseessä on korkeintaan merkin mittainen jono, on ratkaisu ilmeinen.

Esimerkki: jos kyseessä on johdantokurssi, on ratkaisu ilmeinen.
Ratkaisun muodostaminen:

Toiston päätyttyä tiedossa on koko ongelman ratkaisu.

Esimerkki: kun jono on käyty läpi, on sen palindromius tiedossa.

Esimerkki: Pidetään kokoojamuuttujassa kirjaa esitietojen pistesummasta ja kasvatetaan sitä jokaisen kurssin kohdalla. Lopuksi muuttujassa on kokonaissumma.

Muodostetaan kokonaisratkaisu lohkaistun palasen ja pienennetyn ongelman ratkaisujen perusteella. Usein se on jonkinlainen yhdistelmä näistä (esim. summa).

Esimerkki: Jos ensimmäinen ja viimeinen merkki eroavat (palasen ratkaisu), niin kyseessä ei ole palindromi. Muuten vastaus on sama kuin keskiosalle (pienennetyn ongelman ratkaisu).

Esimerkki: kurssiketjun pistesumma on kurssin omien pisteiden (palasen ratkaisun) ja esitietojen pisteiden (pienennetyn ongelman ratkaisun) summa.

Rekursio ja induktio

Onko induktio tuttu matematiikasta? Se on todistusmenetelmä, joka on läheistä sukua rekursiolle.

Rekursiivisen metodin laatimisesta

Käsitellään vielä yksi esimerkki siitä, miten rekursiolla ja iteraatiolla voidaan saavuttaa samoja tavoitteita: otetaan pieni silmukkaa käyttävä funktio ja tehdään siitä rekursiivinen versio. Samalla pohdimme, mitä rekursiivista metodia laatiessa pitää muistaa.

Tämä funktio käyttää silmukkaa tulostaakseen positiivisten kokonaislukujen neliöt parametriksi annettuun ylärajaan asti:

def tulostaNelioita(ylaraja: Int) = {
  for (luku <- 1 to ylaraja) {
    println(luku * luku)
  }
}

Toteutus perustuu taulukossa mainittuun iteraation ideaan: toistetaan neliön laskemista ja tulostamista sekä seuraavaan lukuun siirtymistä luku kerrallaan ykkösestä alkaen, kunnes yläraja on saavutettu.

Entä rekursiivinen versio? Ainakin pitäisi olla sellainen perustapaus, jossa ongelma on niin pieni, että se ratkeaa triviaalisti. Isommasta ongelmasta pitäisi "lohkaista ongelmasta helposti ratkeava palanen" ja "ratkaista pienennetty ongelma samalla tavalla", kunnes päädytään perustapaukseen.

Hahmotellaan ensin pseudokoodina. Aloitetaan perustapauksesta, jossa lukuja ei tarvitse tulostaa lainkaan, koska parametriarvoa pienempiä kokonaislukuja ei ole lainkaan:

def tulostaNelioita(ylaraja: Int) = {
  if (ylaraja == 0) {
    Perustapaus: ei positiivisia lukuja. Ei tarvitse tehdä mitään.
  } else {
    Isompi ongelma: Lohkaise ongelmasta palanen ja kutsu
    tulostaNelioita-funktiota pienennetylle ongelmalle.
  }
}

Koska perustapauksessa ei tässä tarvitse tehdä yhtään mitään, voimme kirjoittaa tämän lyhyemminkin:

def tulostaNelioita(ylaraja: Int) = {
  if (ylaraja > 0) {
    Lohkaise ongelmasta palanen ja kutsu tulostaNelioita-funktiota pienennetylle ongelmalle.
  }
}

Ongelmaa "tulosta N neliötä" vähän pienempi ongelma on "tulosta N-1 neliötä". "Tulosta N-1 neliötä" on täsmälleen sama ongelma kuin alkuperäinenkin, mutta siitä on "lohkaistu pois" viimeinen osa eli luvun N neliön tulostaminen. Käytetään tätä ajatusta:

def tulostaNelioita(ylaraja: Int) = {
  if (ylaraja > 0) {
    Tulosta kaikkien paitsi viimeisen luvun neliöt tulostaNelioita-funktiolla.
    Tulosta viimeisenkin luvun neliö.
  }
}

Ja Scalalla:

def tulostaNelioita(ylaraja: Int): Unit = {
  if (ylaraja > 0) {
    tulostaNelioita(ylaraja - 1)
    println(ylaraja * ylaraja)
  }
}
Rekursiivisessa kutsussa käytetään pienempää parametriarvoa. Riittävän monen rekursiivisen kutsun jälkeen saavutetaan perustapaus, jossa parametriarvo on nolla.

Rekursiivista metodia laatiessa on yleensäkin huolellisesti varmistettava, että rekursio etenee tavalla tai toisella kohti perustapausta ja saadaan joskus valmistakin. (Vrt. silmukan eteneminen; luku 8.3.)

Muistamme taas kirjata rekursiiviselle Scala-metodille palautusarvon tyypin.

Sama animaationa:

Mieti, mitä tapahtuu, kun seuraavaa funktiota kutsutaan vaikkapa parametriarvolla 10.

def tulostaNelioita(ylaraja: Int): Unit = {
  if (ylaraja > 0) {
    tulostaNelioita(ylaraja)
    println(ylaraja * ylaraja)
  }
}

Mikä tai mitkä seuraavista kuvaavat tilannetta?

Entä jos koodi on tällainen?

def tulostaNelioita(ylaraja: Int): Unit = {
  tulostaNelioita(ylaraja - 1)
  println(ylaraja * ylaraja)
}

Muista aina perustapaus

Ellei rekursio palaudu johonkin perustapaukseen, seurauksena on ns. päättymätön rekursio kuten tämän luvun aloittaneessa muinaisvitsissä. Sekin määritelmä olisi käytännöllisempi, jos siihen kirjattaisiin perustapaus:

rekursio (substantiivi): Jos tiedät, mitä on rekursio, niin miksi luet tätä? Muussa tapauksessa: katso rekursio.

Pikkutehtävä: kertomafunktio

Laaditaan funktio kertoma, joka palauttaa parametriksi annetun positiivisen kokonaisluvun kertoman:

kertoma(3)res5: Int = 6
kertoma(6)res6: Int = 720

Yksi tapa ratkaista ongelma on pohjustettu alle. Siitä kuitenkin puuttuu tärkeä osa.

Miten ???-merkitty kohta voidaan täydentää yksinkertaisesti rekursiota käyttäen?

// Oletetaan tässä, että n on positiivinen luku.
def kertoma(n: Int): Int = if (n <= 2) n else ???

Löydät vastauksen myös alla olevaa animaatiota tutkimalla. Animaatio kannattaa muutenkin katsoa, jos koet tarvitsevasi lisäesimerkin rekursion toiminnasta.

Kirjoita vastauksesi tähän:

A+ esittää tässä kohdassa tehtävän palautuslomakkeen.

Pikkutehtävä: lahjavero

Ajatellaan hieman yksinkertaistettua versiota suomalaisesta lahjaverojärjestelmästä. Oletetaan, että lahjavero määräytyy seuraavasti.

  • Ensimmäisestä 4000 eurosta ei mene veroa.
  • 4000 euroa ylittävästä osasta menee veroa 20 %.
  • Jos lahjoittaja antaa myös veron maksamiseen käytettävät rahat, niin koko tästä lisäsummasta peritään myös 20 % veroa.

Esimerkki:

  • Annetaan 54000 euroa. Lahjoittaja haluaa, että vastaanottaja saa tämän summan "puhtaana käteen". Niinpä hänen on annettava suurempi summa, joka kattaa verotkin.
  • 54000 euron verotettava osuus on 50000 euroa. Tästä pitää maksaa 20 % eli 10000 euroa veroa.
  • Lahjoittaja haluaa antaa lisäksi myös nämä 10000 euroa, joten veroa tulee lisäksi 2000 euroa.
  • Lahjoittaja haluaa antaa lisäksi myös nämä 2000 euroa, joten veroa tulee lisäksi 400 euroa.
  • Lahjoittaja haluaa antaa lisäksi myös nämä 400 euroa, joten veroa tulee lisäksi 80 euroa.
  • Lahjoittaja haluaa antaa lisäksi myös nämä 80 euroa, joten veroa tulee lisäksi 16 euroa.
  • Jne.
  • Jotta vastaanottaja saisi 54000 euroaan "verottomana", on lahjoittajan annettava yhteensä 54000 + 10000 + 2000 + 400 + 80 + 16 + ... euroa eli yhteensä 66500 euroa.

Mikä rivi ???-merkittyyn kohtaan pitäisi kirjoittaa, jotta maksettava-funktio laskisi, paljonko lahjoittajan pitää maksaa antaakseen tietynkokoisen lahjan vastaanottajan kannalta "verottomana"? Käytä rekursiota. Likiarvo riittää.

def maksettava(lahjanSuuruus: Double) = lahjanSuuruus + veronMaara(lahjanSuuruus - 4000)

def veronMaara(verotettava: Double): Double =
  if (verotettava < 0.001) {
    0
  } else {
    val vero = verotettava * 0.2
    ???
  }

Kirjoita vastauksesi tähän:

A+ esittää tässä kohdassa tehtävän palautuslomakkeen.

Tehtävä: tehokkaampaa viinaharavointia

Ota esille luvussa 7.4 kohtaamasi Viinaharava-projekti. Muuta Glass-luokan drink-metodia siten, että kun juoduksi tulee vesilasillinen, jonka vaarallisuustaso on nolla (eli naapurissa ei ole viinoja), niin samalla juontikäskyllä tulevat juoduiksi myös kaikki naapurivedet. Naapurin ollessa myös vaaraton siemaistaan senkin naapurit, ja niin edelleen.

Ohjeita ja vinkkejä:

  • Käytä rekursiota: kutsu drink-metodia sen itsensä sisältä.
  • Varo loputonta rekursiota: juodaan lasin A naapurit, joihin kuuluu lasi B, sitten B:n naapurit mukaan lukien A, sitten A:n naapurit mukaan lukien B, jne.

A+ esittää tässä kohdassa tehtävän palautuslomakkeen.

Apufunktiomenetelmä ja rekursiivinen favorite

Otetaan vielä viimeisen kerran tarkasteluun GoodStuff-projektin Category-luokan suosikkikirjanpito, jota on versioitu pitkin kurssia. Tehdään siitä rekursiivinen versio.

Olet jo nähnyt (esimerkiksi luvussa 9.2) tälle metodille lyhyempiä korkeamman abstraktiotason toteutuksia kuin pian nähtävä rekursiivinen versio. Tämä uusi toteutuskin kannattaa kuitenkin tutkia. Paitsi että se toimii lisäesimerkkinä siitä, miten rekursiota voi käyttää silmukoihin vertautuvana suhteellisen matalan abstraktiotason yleisenä toteutustekniikkana, niin tämä esimerkki myös tutustuttaa yleisesti käytettyyn kikkaan: teemme rekursiivisen "apufunktion", jota kutsumme tiety(i)llä lähtöarvo(i)lla.

Kerrataan tavoite. favorite-metodin pitäisi palauttaa kyseisen kategoriaolion experiences-puskurin sisältämistä kokemuksista se, jolla on paras arvosana. Tämä suosikkikokemus palautetaan Option-kääreessä. Jos kokemuksia ei ole, ei ole suosikkiakaan ja palautetaan None.

Tässä ensin vertailukohdaksi yksi iteratiivinen tapa toteuttaa metodi:

class Category(val name: String, val unit: String) {

  private val experiences = Buffer[Experience]()

  def favorite = {
    if (this.experiences.isEmpty) {
      None
    } else {
      var fave = this.experiences(0)
      for (currentIndex <- 1 until this.items.size) {
        fave = this.items(currentIndex).chooseBetter(fave)
      }
      Some(fave)
    }
  }

}

Kuten yllä olevan iteratiivisen version, myös rekursiivisen toteutuksen olisi käsiteltävä kutakin experiences-puskurin alkiota. Samalla on pystyttävä pitämään kirjaa siitä, mitä puskurin osaa milloinkin käsitellään, sekä siitä, mikä on paras toistaiseksi löydetty kokemus. Iteratiivisessa versiossa, jossa kaikki tapahtuu yhden kutsupinon kehyksen sisällä, näitä asioita varten on määritelty omat paikalliset muuttujansa. Paikallisia muuttujia voi käyttää rekursiivisessakin versiossa, mutta koska kukin rekursiivinen kutsu toimii omassa kehyksessään omine paikallisine muuttujineen, on kunkin kutsun tarvitsemat tiedot syytä välittää metodille parametreiksi.

Kuitenkin favorite-metodi on parametriton, ja sellaiseksi se on tarkoitus jättääkin.

Määritellään siis apufunktio, joka on rekursiivinen, ottaa parametriarvon ja on tarkoitettu nimenomaan favorite-metodin käyttöön. Olkoon sen nimi findBest. Määrittelemme sen paikalliseksi funktioksi favorite-funktion sisään:

class Category(val name: String, val unit: String) {

  private val experiences = Buffer[Experience]()

  def favorite = {
    def findBest(start: Int): Experience = {
      Tutki this.experiences-puskurin sisältö alkaen indeksistä start.
      Palauta paras löydetyistä kokemuksista.
    }
    if (this.experiences.isEmpty) None else Some(this.findBest(0))
  }

Tässä siis favorite huolehtii itse tapauksesta, jossa kokemuksia on nolla; muuten delegoidaan homma findBest-metodille: "Etsi alkaen indeksistä 0, ja palauta paras löydetty."

Tarvitaan vielä toteutus findBestille. Tarkennetaan ensin sen pseudokoodia:

def findBest(start: Int): Experience = {
  Jos start on viimeinen indeksi, palauta kyseinen viimeinen kokemus.
  Muussa tapauksessa etsi "paras seuraavista" eli niistä, joiden indeksi on vähintään start + 1.
  Palauta joko startin osoittama alkio tai paras seuraavista, kumpi vain niistä on parempi.
}

Scalaksi:

def findBest(start: Int): Experience = {
  if (start == this.experiences.size - 1) {
    this.experiences(start)
  } else {
    val bestOfRest = findBest(start + 1)
    this.experiences(start).chooseBetter(bestOfRest)
  }
}
Perustapaus: jos ollaan puskurin viimeisen alkion kohdalla, paras startista alkaen on tietysti juuri tuo viimeinen alkio.
"Pienennetty ongelma", joka ratkaistaan rekursiivisella kutsulla: startin jälkeiset kokemukset.
"Lohkaistu helposti ratkeava pala" eli täsmälleen kohdassa start oleva kokemus.
Edellisten yhdistäminen: valitaan parempi ja palautetaan se.
Mitkä seuraavista pitävät paikkansa, kun yllä kuvattua favorite-metodia kutsutaan siten, että this.experiences sisältää kolme kokemusoliota, joiden arvosanat ovat 3, 7 ja 2 tässä järjestyksessä?

Tehtävä: sukupolvia

Tehtävänanto

Tutustu Recursion-projektin pakkaukseen o1.family. Siellä on yksi luokka, FamilyMember. Toteuta tuon luokan puuttuvat metodit rekursiota käyttäen.

Ohjeita ja vinkkejä

  • Yksi toteutustapa on yhdistää rekursioon map-metodi: käsittele lapset kussakin kohdassa map-kutsulla, jolla etenet syvemmälle sukupuuhun rekursiivisesti. Muitakin tapoja on.

  • Pienen testiohjelman laatiminen voi olla hyvä ajatus.

  • Jos teet testiohjelman, niin varo luomasta käynnistysoliossa perheenjäseniä siten, että viittaat vasta jäljempänä määriteltyyn muuttujaan. Siis ei näin:

    object FamilyTest extends App {
  val maria = new FamilyMember("Maria", Vector(jeesus))
  val jeesus = new FamilyMember("Jeesus")
  println(maria.numberOfDescendants)
}

    Tämä koodi menee Scala-kääntäjästä läpi (joskin varoituksen saattelemana), mutta se kaatuu ajonaikaiseen virheilmoitukseen NullPointerException. Kun vaihdamme kahden ensimmäisen rivin paikkaa keskenään, Jeesus on olemassa jo Mariaa luotaessa ja homma toimii. Sivuutamme esimerkin biologisen erikoisuuden sekä mahdolliset teologiset ja etiologiset tulkinnat.

Tarkempi selitys mainitusta NullPointerExceptionista

Miten voi olla, että tuo FamilyTest tuottaa ajonaikaisen virhetilanteen? Eikö ollut niin, että muuttuja on määritelty vasta siitä eteenpäin, mihin se valilla kirjataan, joten jeesus-muuttujan määrittelemättömyydestä pitäisi tuossa annetussa koodissakin tulla käännösaikainen ilmoitus?

Tosiaan, jos koodi olisi jonkin metodin sisällä ja muuttujat tuon metodin paikallisia muuttujia, niin saisimme käännösaikaisen virheilmoituksen. Mutta kun koodi on kirjoitettu suoraan yksittäisolioon, niin maria ja jeesus ovat tämän olion muuttujia. Ja olion muuttujat ovat määriteltyjä koko olion koodissa; ne saavat oletusarvot välittömästi olion luomisen yhteydessä jo ennen kuin olion tila varsinaisesti alustetaan. (Syyt tälle joskus kiusalliselle toiminnalle liittyvät siihen, miten Scalasta on tehty yhteensopiva Javan kanssa.) Oletusarvot ovat samat kuin taulukon alkioiden oletusarvot, joista mainittiin luvussa 11.2.

Esimerkissämme käy siis niin, että jo silloin, kun FamilyTest-olion sisältämää koodia ryhdytään suorittamaan, ovat olion muuttujat maria ja jeesus olemassa. Niillä ei ole kunnollisia arvoja vaan vain null-arvot. Homma menee päin seimiä siinä vaiheessa, kun Maria-nimistä oliota luodaan: jeesus-muuttujalla on tällöin vielä null-oletusarvo, ja null siis tallentuu Marian jälkeläiseksi. Vaikka jeesus-muuttuja saakin seuraavalla rivillä arvokseen viittauksen toiseen FamilyMember-olioon, niin Maria ei siitä enää miksikään muutu. Niinpä kutsu maria.numberOfDescendants kaatuu ristiriitaiseen osatehtävään: pitäisi selvittää Marian olemattoman lapsen jälkeläisten lukumäärä.

Tämä olkoon teille merkiksi siitä, että Option-tyypin olemassaolosta huolimatta Scala-kieltä käyttäessäkin täytyy olla tietyissä tilanteissa varuillaan välttääkseen NullPointerException-virheet, joita vastaan luvussa 4.2 saarnattiin. Niiltä Scala-koodarikin pelastuu yksin huolellisuudesta.

Palauttaminen

A+ esittää tässä kohdassa tehtävän palautuslomakkeen.

Lisää rekursiotehtäviä

Kaikki tämän kappaleen tehtävät ovat täysin vapaaehtoisia.

Lisätehtävä: esineitä sisäkkäin

Luvussa 7.3 oli esimerkki, jossa Container oli Itemin aliluokka ja esineitä saattoi laittaa sisäkkäin. Bongaa rekursio. Muokkaa aiemmin laadittua koodia niin, että esimerkiksi laukun sisältämiä esineitä laskettaessa myös laukun sisältämien esineiden sisällöt (ja niiden sisällöt jne.) tulevat laskuun mukaan.

Lisätehtävä: versioita esitietoteemasta

  1. Yllä käytettiin kahta eri aliluokkaa Jatkokurssi ja Johdantokurssi kuvaamaan tapauksia, joissa kurssilla on ja ei ole esitietoja. Toinen vaihtoehto olisi ollut käyttää vain yhtä konkreettista Kurssi-luokkaa, jolla olisi ilmentymämuuttuja esitieto ja sen tyyppinä Option[Kurssi]. Esitiedottoman kurssiolion esitieto-muuttujan arvo on siis None. Osaatko toteuttaa tällaisen version? Millainen rekursiivisesta kokonaisOp-metodista tulee? (Voit katsoa erään ratkaisutavan Recursion-ohjeisprojektista.)
  2. Osaatko toteuttaa tämän Option-pohjaisen kurssiluokan silmukalla, ilman rekursiota? Tuliko kaunista jälkeä?
  3. Miten mallintaisit tilanteen, jossa kurssilla voi olla mikä tahansa määrä esitietokursseja?
  4. Mitä jos esitiedoissa esiintyy sama kurssi moneen kertaan? Mitä jos esitietoketjussa on sykli eli A on B:n esitieto ja toisinpäin?

Lisätehtäviä: reverse

  1. (Helpompi:) Millä tavoin ylempänä kuvattu reverse-metodiin perustuva palindromiongelman ratkaisu syyllistyy tarpeettomaankin arvojen vertailemiseen?
  2. (Haastavampi:) Mieti, miten toteuttaisit reverse-metodia muistuttavan funktion, joka palauttaa parametriksi annetun merkkijonon takaperin. Älä käytä reverse-metodia tai muita vastaavia merkkijonometodeita. Osaatko tehdä sekä iteratiivisen että rekursiivisen toteutuksen?
  3. (Sopii lähinnä sellaisille, joilla on kurssia edeltävää ohjelmointikokemusta ja jotka haluavat perehtyä Scala-kielen toteutuksen syövereihin tarkemmin:) Scala-peruskirjastojen lähdekoodi löytyy kirjastojen Scaladoc-dokumentaation ohesta. Selvitä lähdekoodia penkomalla, onko merkkijonojen reverse-metodi toteutettu iteraatiolla vai rekursiolla. Varoitus: Tämä tehtävä ei ole lainkaan niin yksinkertainen kuin voisi kuvitella. Vinkki: Googleta aluksi, mikä on StringOps ja mitä ovat implicit conversions.

Lisätehtävä: rahan rikkominen

Käytetään luokkaa Currency, joka kuvaa valuuttoja ja erityisesti valuutan kolikkotyyppejä. Esimerkiksi näin voi luoda valuutan, jossa on 10 pennin, 50 pennin, 1 markan, 5 markan ja 10 markan kolikot:

val mummonmarkat = new Currency(Vector(10, 50, 100, 500, 1000))mummonmarkat: o1.money.Currency = 10,50,100,500,1000

Luokan Currency kumppaniolioon on valmiiksi määritelty pari valuuttaa:

Currency.EURres7: o1.money.Currency = 1,2,5,10,20,50,100,200
Currency.USDres8: o1.money.Currency = 1,5,10,25,50

Haluttaisiin laatia luokalle Currency metodi, joka laskee, monellako eri tavalla annettu rahasumma voidaan jakaa kolikoiksi. Esimerkki:

Currency.EUR.waysToSplit(5)res9: Int = 4

Vastaus on neljä, koska viisi eurosenttiä voidaan jakaa neljällä tavalla: 1+1+1+1+1, 1+1+1+2, 1+2+2 tai 5.

Toteuta metodi waysToSplit ja selvitä vaikkapa, monellako tavalla yksi Yhdysvaltain dollari voidaan jakaa kolikoiksi (Currency.USD.waysToSplit(100)). Projektin Recursion pakkauksesta o1.money löytyy hieman pohjakoodia, jonka voit täydentää.

Ohjeita ja vinkkejä:

  • Laadi rekursiivinen apufunktio, joka ottaa parametreikseen jaettavan rahasumman sekä tiedon siitä, mitä kolikkotyyppejä summan jakamiseen käytetään.

  • Kutsu tätä apufunktiota waysToSplit-metodista siten, että summana on (aluksi) koko jaettava rahasumma ja kaikki kolikkotyypit ovat käytössä.

  • Muista, että rekursiivisen metodin olisi pienennettävä ongelmaa jotenkin. Tässä "pienennettäviä asioita" on kaksi: jaettava rahasumma sekä jakamisessa käytettävät kolikkotyypit.

  • Koeta ensin miettiä itse, ja katso lisävinkkejä alta, jos homma ei etene.

    Vinkki rekursiivisista kutsuista

    Näytä vinkkiPiilota vinkki

    Olkoon alkuperäinen summa S. Valitaan mielivaltainen kolikkotyyppi K, jonka arvo on A.

    Mieti:

    • Monellako tavalla S:n voi jakaa, jos K:ta ei käytetä lainkaan?
    • Entä monellako tavalla pienemmän rahamäärän S-A voi jakaa?
    • Onko olemassa muita tapoja jakaa S?

    Jatkovinkki rekursiivisista kutsuista

    Näytä vinkkiPiilota vinkki

    S:n voi jakaa täsmälleen näin monella eri tavalla:

    1. Montako kertaa S:n voi jakaa ilman kolikkotyypin K käyttöä, plus...
    2. ... montako kertaa pienemmän rahamäärän S-A voi jakaa käyttäen kaikkia kolikkotyyppejä.

    Muotoile näistä kahdesta tapauksesta rekursiiviset apufunktion kutsut.

    Miten perustapaukset?

    Näytä vinkkiPiilota vinkki

    Nollan voi jakaa kolikoiksi tasan yhdellä tavalla.

    Negatiivista lukua ei voi jakaa yhdelläkään tavalla.

    Nollalla kolikkotyypillä ei voi jakaa mitään summaa yhdelläkään tavalla.

A+ esittää tässä kohdassa tehtävän palautuslomakkeen.

Koodinlukutehtävä: rekursiivinen järjestämisalgoritmi

Seuraava koodi järjestää parametriksi annetun kokoelman. Tutki koodia, ja pohdi, miten se toimii.

Koodissa on käytetty pareja ja partition-metodia (luku 8.4) sekä operaattoria ++, jolla laitetaan kokoelmien alkiot peräkkäin (luku 4.1).

def sort(data: Vector[Int]): Vector[Int] =
  if (data.isEmpty) {
    data
  } else {
    val (pivot, rest) = (data.head, data.tail)
    val (smaller, larger) = rest.partition( _ <= pivot )
    sort(smaller) ++ Vector(pivot) ++ sort(larger)
  }

Kyseessä on eräs toteutus pikalajittelu-nimiselle algoritmille (quicksort), josta kertoo lisää vaikkapa Wikipedia.

Vähän tehokkuudesta

Fibonacci-luvut

Fibonaccin lukujono on 0, 1, 1, 2, 3, 5, 8, 13, jne. siten, että:

  • Fibonacci-luku numero nolla on 0 ja Fibonacci-luku numero yksi on 1.
  • Loput luvut saadaan kaavalla: Fibonaccin = Fibonaccin-2 + Fibonaccin-1

Määritelmä on rekursiivinen: kukin Fibonacci-luku määräytyy edellisten Fibonacci-lukujen perusteella.

Sivistävää katsottavaa

Eräs tapa määrittää Fibonacci-lukuja Scalalla

Kaunis rekursiivinen Scala-koodi n:nnen Fibonacci-luvun laskemiseen saadaan suoraan määritelmästä:

def fibo(n: Int): Long = if (n <= 1) n else fibo(n - 1) + fibo(n - 2)

Tämä ratkaisu toimii siinä mielessä, että palautusarvot ovat parametriarvon mukaisia Fibonacci-lukuja. Se on kuitenkin ongelmallinen.

fibo-funktion ongelma

Jotkut rekursiiviset ratkaisut ovat hyvin tehottomia tietokoneen muistin- ja/tai ajankäytön suhteen. (Toki on myös tehottomia iteratiivisia ratkaisuja.) Vaikka tehokkuusasioita käsitellään lähinnä jatkokursseilla, niin tutustutaan nyt esimerkkiimme yleissivistävästi tästäkin näkökulmasta:

Montako kertaa tämä funktio tulee kutsutuksi, kun sillä etsitään Fibonacci-luku numero 7?
Saako funktiolla tietokoneen polvilleen?

Tehokkaampaa rekursiota

Tämä ei tarkoita, että rekursio on väistämättä tehoton tapa toteuttaa fibo-funktio. Yllä esitelty sinisilmäisen yksinkertainen tapa kylläkin on huono. Pari parempaa rekursiivista toteutusta on esitelty alla; voit tutustua niihin, jos haluat.

Eräs parempi ratkaisu ongelmaan

Seuraava koodi ei ole läheskään yhtä kaunis tai tiivis kuin alkuperäinen, mutta ratkaisevasti tehokkaampi se on.

def fibo(n: Int) = {

  def fiboapu(tamaFibo: Int, seuraavaFibo: Int, montakoEdetaan: Int): Long = {
    if (montakoEdetaan <= 0)
      tamaFibo
    else
      fiboapu(seuraavaFibo, tamaFibo + seuraavaFibo, montakoEdetaan - 1)
  }

  fiboapu(0, 1, n)
}
Tämä ratkaisu käyttää rekursiivista apufunktiota nimeltä fiboapu. (Vrt. favorite-toteutuksen findBest edellä.)
fiboapu pitää kirjaa peräkkäisistä Fibonacci-luvuista, joten se ei joudu laskemaan samoja lukuja uudestaan. Sille annetaan parametreiksi kaksi peräkkäistä Fibonacci-lukua sekä tieto siitä, montako lukua pitäisi vielä edetä Fibonacci-lukujonossa ennen kuin on saavutettu lopullinen tavoiteluku.
fibo kutsuu fiboapua: "Aloita Fibonacci-luvusta, joka on nolla ja jota seuraava on ykkönen. Etene n Fibonacci-lukua ja palauta luku, johon päädyt."

Tämäntyyppistä ratkaisua, jossa pienten osaongelmien ratkaisuja pannaan muistiin ja hyödynnetään sitten isompien osaongelmien ratkaisuissa sanotaan dynaamiseksi ohjelmoinniksi (dynamic programming). Dynaamista ohjelmointia voi harjoittaa rekursiivisilla funktiokutsuilla (kuten yllä) tai silmukoilla.

Lisäharjoite: Kirjoita iteratiivinen toteutus fibo-funktiolle silmukalla. Käytä inspiraationa tätä parempaa rekursiivista toteutusta.

Rekursiivinen virta ja laiska Fibonacci

Luvussa 7.1 esiteltiin virtoja: rajaamattoman kokoisia alkiokokoelmia.

Virroilla voi kuvata myös Fibonaccin lukujonon:

def fibonacciSequence = {
  def fiboFrom(first: BigInt, second: BigInt): Stream[BigInt] = first #:: fiboFrom(second, first + second)
  fiboFrom(0, 1)
}fibonacciSequence: Stream[BigInt]
fibonacciSequence.take(10).toVectorres10: Vector[BigInt] = Vector(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)
fibonacciSequence(9)res11: BigInt = 34
fibonacciSequence(100)res12: BigInt = 354224848179261915075
fibonacciSequence(10000)res13: BigInt = 3364476487643178326662161200510754331030214846068006390656476997468008144216666236815559551
363373402558206533268083615937373479048386526826304089246305643188735454436955982749160660209988418393386465
273130008883026923567361313511757929743785441375213052050434770160226475831890652789085515436615958298727968
29875106312005754287834... [Jne. Fibonaccin luku numero 10000 on reilut 2000 numeroa pitkä.]
Apufunktio muodostaa virran, joka kattaa kaikki Fibonaccin luvut alkaen kahdesta peräkkäisestä luvusta, jotka annetaan parametreina.
Muodostetaan lukujen virta rekursiivisesti laittamalla alkuun parametrin perusteella tiedetty ensimmäinen luku ja perään sellainen Fibonaccin lukujen virta, jonka alussa on toinen tiedetty luku.

Tämä ratkaisu on melko elegantti ja tehokkuusominaisuuksiltaankin hyvä. Koska virta on laiska (luku 7.1), se ei laske aiempia Fibonaccin lukuja toistuvasti, kuten alkuperäinen ratkaisumme, vaan pitää edelliset luvut tallessa sen aikaa, kun niitä tarvitaan. Esimerkiksi kymmenennentuhannennen Fibonaccin luvun laskeminen sujuu pienessä hetkessä.

Häntärekursiosta

Usein kysytty kysymys: eikö rekursio kuitenkin aina syö iteraatiota enemmän resursseja — tarvitaanhan muistia päällekkäisille kehyksille kutsupinossa?

On totta, että rekursiivisuus voi johtaa muistisyöppöihin ohjelmiin. On kuitenkin paljon tilanteita, joissa rekursiivisiin kutsuihin liittyvistä kehyksistä ei aiheudu käytännön haittaa. Lisäksi ongelmaa pienentävät häntärekursioon (tail recursion) nojautuvat optimoinnit. Häntärekursiiviseksi laaditussa funktiossa jokainen rekursiivinen kutsu suoritetaan aivan viimeisenä ennen funktiokutsun päättymistä ja mahdollista arvon palauttamista.

Esimerkiksi yllä laadittu onPalindromi-funktio on häntärekursiivinen, koska rekursiivisen kutsun palauttama totuusarvo palautetaan heti sellaisenaan eteenpäin. Toisaalta esimerkiksi tulostaNelioita ei ole häntärekursiivinen, koska siinä suoritetaan kertolasku ja tulostaminen aina rekursiivisen kutsun jälkeen.

Häntärekursiivisen funktion suorittamiseen ei välttämättä tarvita useita kehyksiä, ja niinpä ohjelmointityökalut (kuten kääntäjät) voivat optimoida kehyksien luonnin pois suoritettavasta ohjelmaversiosta. Alla on esitetty optimoitu esimerkki onPalindromi-metodin suorituksesta:

Esimerkiksi Scala-työkalut mahdollistavat tämänkaltaisen optimoinnin.

Voidaan sanoa: vaikka häntärekursiivisen funktion koodi on rekursiivinen, sen määrittelemä prosessi on iteratiivinen. Tällaiselle iteratiiviselle prosessille on aina olemassa myös silmukkapohjainen funktiototeutus, joka on tuotettavissa yksinkertaisella automaattisella muunnoksella häntärekursiivisesti toteutetusta ohjelmasta.

Lisäharjoitus: Miksei esimerkiksi yllä laadittu kertomafunktio ole häntärekursiivinen? Mitkä tässä luvussa esiintyneistä rekursiivisista funktioista ovat?

Lisäharjoitus: laadi häntärekursiivinen versio kertoma-funktiosta. Käytä apufunktiota.

Aiheeseen palataan Ohjelmointi 2 -kurssin materiaalissa Voit lukea lisää myös Wikipediasta.

Lisätehtävä: Levenšteinin etäisyys ja tehokkuus

Alla on elegantti mutta tehoton Scala-toteutus Levenšteinin etäisyyden laskemiseksi. Luku 1.6 mainitsi tämän etäisyyden olevan kokonaisluku, joka kertoo, montako yhden merkin lisäystä, poistoa tai toiseksi merkiksi vaihtamista vähintään tarvitaan muuntamaan tietty merkkijono tietyksi toiseksi merkkijonoksi.

def editDistance(text1: String, text2: String): Int = {
  if (text1.isEmpty || text2.isEmpty) {
    math.max(text1.length, text2.length)
  } else if (text1.head == text2.head) {
    editDistance(text1.tail, text2.tail)
  } else {
    val deletion     = editDistance(text1.tail, text2     )
    val insertion    = editDistance(text1,      text2.tail)
    val substitution = editDistance(text1.tail, text2.tail)
    Vector(deletion, insertion, substitution).min + 1
  }
}
Perustapaus: tyhjän merkkijonon etäisyys mistä tahansa toisesta merkkijonosta on tuon toisen merkkijonon pituus.
Rekursiivinen tapaus: samalla merkillä alkavien jonojen etäisyys on sama kuin noiden jonojen loppujen merkkien keskinäinen etäisyys.
Toinen rekursiivinen tapaus: Kun kyse on eri merkillä alkavista merkkijonoista, kokeillaan ensimmäisen merkin poistoa, lisäystä ja vaihtamista kutakin. Lasketaan kolme etäisyyttä näin yhdellä operaatiolla muokattujen merkkijonojen perusteella, ja ...
... valitaan lyhin etäisyys, johon lisätään yksi, koska suoritettiin yksi poisto, lisäys tai vaihto.

Lue Levenšteinin etäisyyttä käsittelevä Wikipedia-artikkeli ja pohdi yllä annetun ratkaisun tehokkuutta. Selvitä, miten ongelmaa voidaan rajata sen helpottamiseksi, sekä mitä tehostuskeinoja voi käyttää joko rekursiivisuuden säilyttäen tai muuten.

Yhteenvetoa

  • Rekursiivinen funktio kutsuu itseään.
  • Rekursiivinen algoritmi lohkaisee ongelmasta pienen helposti ratkeavan palan ja soveltaa itseään jäljelle jäävään osaan ongelmasta. Lopulta ongelma palautuu triviaalisti ratkeavaan perustapaukseen.
    • Rekursiota voi käyttää funktioiden toteutustekniikkana vastaavasti kuin toistokäskyjä. Moniin ongelmiin on hyvin elegantteja rekursiivisia ratkaisuja.
  • Rekursiossa kutsupinoon syntyy periaatteessa useita samaan metodiin liittyviä kehyksiä päällekkäin, yksi kullekin kutsukerralle.
    • (Tietyissä tilanteissa ohjelmointityökalut voivat optimoida tätä käyttämällä samaa kehystä toistuvasti.)
  • Ohjelma voi olla rakenteellisesti rekursiivinen: tietotyyppiä käytetään osana itseään. Tällöin myös rekursiivisten funktioiden käyttö on hyvin usein perusteltua.
    • Rekursion käyttö ei kuitenkaan edellytä rekursiivista rakennetta: funktio voi luoda uusia arvoja ja soveltaa itseään niihin.
  • Lukuun liittyviä termejä sanastosivulla: rekursio, rakenteellinen rekursio, perustapaus; iteraatio.

Palaute

Huomaathan, että tämä on henkilökohtainen osio! Vaikka olisit tehnyt lukuun liittyvät tehtävät parin kanssa, täytä palautelomake itse.

Tekijät

Tämän oppimateriaalin kehitystyössä on käytetty apuna tuhansilta opiskelijoilta kerättyä palautetta. Kiitos!

Kierrokset 1–13 ja niihin liittyvät tehtävät ja viikkokoosteet on laatinut Juha Sorva.

Kierrokset 14–20 on laatinut Otto Seppälä. Ne eivät ole julki syksyllä, mutta julkaistaan ennen kuin määräajat lähestyvät.

Liitesivut (sanasto, Scala-kooste, usein kysytyt kysymykset jne.) on kirjoittanut Juha Sorva sikäli kuin sivulla ei ole toisin mainittu.

Tehtävien automaattisen arvioinnin ovat toteuttaneet Riku Autio, Jaakko Kantojärvi, Teemu Lehtinen, Timi Seppälä, Teemu Sirkiä ja Aleksi Vartiainen.

Lukujen alkuja koristavat kuvat ja muut vastaavat kuvituskuvat on piirtänyt Christina Lassheikki.

Yksityiskohtaiset animaatiot Scala-ohjelmien suorituksen vaiheista ovat suunnitelleet Juha Sorva ja Teemu Sirkiä. Niiden teknisen toteutuksen ovat tehneet Teemu Sirkiä ja Riku Autio käyttäen Teemun toteuttamia Jsvee- ja Kelmu-työkaluja.

Muut diagrammit ja materiaaliin upotetut vuorovaikutteiset esitykset on laatinut Juha Sorva.

O1Library-ohjelmakirjaston ovat kehittäneet Aleksi Lukkarinen ja Juha Sorva. Useat sen keskeisistä osista tukeutuvat Aleksin SMCL-kirjastoon.

Opetustapa, jossa käytämme O1Libraryn työkaluja (kuten Pic) yksinkertaiseen graafiseen ohjelmointiin on saanut vaikutteita tekijöiden Flatt, Felleisen, Findler ja Krishnamurthi oppikirjasta How to Design Programs sekä Stephen Blochin oppikirjasta Picturing Programs.

Oppimisalusta A+ on luotu Aallon LeTech-tutkimusryhmässä pitkälti opiskelijavoimin. Pääkehittäjänä toimii tällä hetkellä Jaakko Kantojärvi, jonka lisäksi järjestelmää kehittävät useat tietotekniikan ja informaatioverkostojen opiskelijat.

Kurssin tämänhetkinen henkilökunta on kerrottu luvussa 1.1.

Lisäkiitokset tähän lukuun

Rahanrikkomistehtävä on Scala-kielinen variaatio ohjelmointiongelmasta, joka on esitetty legendaarisessa tietojenkäsittelyopin oppikirjassa Structure and Interpretation of Computer Programs.

Fibonaccista ja kultaisesta leikkauksesta kertovan videon päätekijä on Beau Janzen.

../_images/imho11.png
Palautusta lähetetään...