Rekursio

Rekursio tarkoittaa sitä, että metodi kutsuu itseään (joko suoraan tai jonkun toisen metodin välityksellä).

Monien ongelmien ratkaiseminen rekursiivisella ohjelmalla on selvästi helpompaa kuin ei-rekursiivisella. Ohjelmasta tulee lyhyempi ja selvempi.

Rekursio ei tee ohjelmasta tehotonta. Ratkaisevaa on se, mitä rekursiivinen ohjelma tekee.

Kertoma rekursiivisesti

n! = 1 * 2 * 3 * ... * n

0! = 1

näiden avulla voi kirjoittaa kertomalle rekursiivisen kaavan:

n! = n * (n-1)!, jos n >= 1

n! = 1, jos n == 0

Niitä käyttämällä voidaan kirjoittaa rekursiivinen ohjelma kertoman laskemiseen.

public class KertomaRek {

  private static long kertoma(int n) {
    if (n == 0)
      return 1;
    else 
      return n * kertoma(n-1);
  }

  public static void main(String[] args) {
    int luku;
    long tulos;

    System.out.println("Anna luku");
    luku = Lue.kluku();
    if (luku < 0)
      System.out.println("Negatiivisen luvun kertomaa ei voi laskea.");
    else {
      tulos = kertoma(luku);
      System.out.println(luku + "! = " + tulos);
    }
  }
}

Palindromitesti

Kirjoitetaan metodi, joka testaa, onko sille parametrina annettu merkkijono palindromi. Palindromi on merkkijono, joka on sama luettuna vasemmalta oikealle ja oikealta vasemmalle, esimerkiksi "saippuakauppias".

Merkkijono on palindromi, jos sen ensimmäinen ja viimeinen merkki ovat samoja ja niiden välissä oleva merkkijono on palindromi. Myös yhden tai nollan mittainen merkkijono on palindromi.

public class PalindromiRek {
  
  private static boolean palindromi(String sana) {
    int pit;

    pit = sana.length();
    if (pit <= 1)
      return true;
    else if (sana.charAt(0) != sana.charAt(pit-1))
      return false;
    else
      return palindromi(sana.substring(1, pit-1));
  }


  public static void main(String[] args) {
    String mjono;

    System.out.println("Anna merkkijono");
    mjono = Lue.rivi();
    if (palindromi(mjono))
      System.out.println("On palindromi");
    else
      System.out.println("Ei ole palindromi");
  }
}

Potenssiin korotus

Kirjoitetaan aikaisemmin esitetty tehokas potenssiin korotus rekursiivisena metodina

public class PotenssiRek {

  private static double pot(double kanta, int exp) {
    
    if (exp == 0)
      return 1;
    else if (exp % 2 == 0)
      return pot(kanta*kanta, exp / 2);
    else 
      return kanta * pot(kanta, exp - 1);
  }

  
  public static void main(String[] args) {
    double kantaluku, tulos;
    int ekspo;

    System.out.println("Anna kantaluku ja eksponentti");
    kantaluku = Lue.dluku();
    ekspo = Lue.kluku();
    if (ekspo < 1)
      System.out.println("Ohjelma toimii " +
			 "vain positiivisella eksponenetilla!");
    else {
      tulos = pot(kantaluku, ekspo);
      System.out.println("Tulos on " + tulos);
    }
  }
}

Fibonaccin luvut rekursiivisesti

Fibonaccin lukujono on 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... siten, että seuraava luku on aina kahden edellisen luvun summa.

Käytetään suoraan määritelmää

fibo(n) = fibo(n-2) + fibo(n-1)

ja kirjoitetaan rekursiivinen ohjelma Fibonaccin lukujen laskemiseen:

public class FibonacciRek {

  private static long fibo(int n) {
    if (n == 1)
      return 1;
    else if (n == 2)
      return 1;
    else
      return fibo(n-2) + fibo(n-1);
  }

  
  public static void main(String[] args) {
    int luku;

    System.out.println("Anna luku:");
    luku = Lue.kluku();
    if (luku <= 0)
      System.out.println("Ei Fibonaccin lukua");
    else
      System.out.println("Fibonaccin luku: " +
			 fibo(luku));
  }
}

Fibonaccin lukuja laskeva ohjelma on hyvin tehoton. Miksi?

Tämä ei kuitenkaan tarkoita sitä, että kaikki rekursiiviset ohjelmat olisivat tehottomia. Monet rekursiiviset ohjelmat ovat hyvin tehokkaita, esimerkiksi edellä esitetty potenssiin korotus.

Hanoin tornit

Vanhan tarinan mukaan Jumala oli luodessaan maailmaa asettanut erääseen takaintialaiseen temppeliin kolme timanttineulaa pystyyn. Yhdessä neulassa (A) oli 64 erikokoista kultalevyä päällekkäin järjestyksessä siten, että suurin levy oli alimmaisena ja pienin päällimmäisenä. Temppelien pappien tehtävänä oli siirtää levyt neulasta A neulaan C käyttämällä apuna neulaa B. Siirtämisessä piti noudattaa seuraavia sääntöjä:

• Vain yhtä levyä saa siirtää kerrallaan

• Missään neulassa ei suurempi levy saanut olla pienemmän päällä

Tarinan mukaan maailmanloppu koittaa, kun papit ovat saaneet tehtävänsä valmiiksi.

Kirjoitetaan ohjelma, joka antaa ohjeet, miten levyjä pitää siirtää, esim. "Siirrä levy neulasta A neulaan B."

Koska meillä ei ole aikaa odottaa maailmanloppua, annetaan ohjelmalle syötteenä levyjen määrä.

Perusidea: jos on siirrettävä N levyä lähtöneulasta tuloneulaan, niin

1. Siirretään N-1 levyä lähtöneulasta apuneulaan.

2. Siirretään yksi levy lähtöneulasta tuloneulaan.

3. Siirretään N-1 levyä apuneulasta tuloneulaan.

N-1:n levyn siirto tehdään rekursiivisesti samalla algoritmilla. Yksi levy voidaan siirtää suoraan.

public class Hanoi {

  private static void siirrot(char mista, char mihin, char apu, int maara) {
    if (maara == 1)
      System.out.println("Siirrä levy neulasta " + mista + 
			 " neulaan " + mihin);
    else {
      siirrot(mista, apu, mihin, maara-1);
      System.out.println("Siirrä levy neulasta " + mista + 
			 " neulaan " + mihin);
      siirrot(apu, mihin, mista, maara-1);
    }
  }


  public static void main(String[] args) {
    int lkm;

    System.out.println("Anna levyjen määrä");
    lkm = Lue.kluku();
    if (lkm >= 1)
      siirrot('A', 'C', 'B', lkm);
  }
}

Esimerkiksi kolmelle levylle ohjelma tulostaa seuraavat ohjeet:

Anna levyjen määrä

3

Siirrä levy neulasta A neulaan C

Siirrä levy neulasta A neulaan B

Siirrä levy neulasta C neulaan B

Siirrä levy neulasta A neulaan C

Siirrä levy neulasta B neulaan A

Siirrä levy neulasta B neulaan C

Siirrä levy neulasta A neulaan C

Oletetaan, että maailma luotiin noin vuonna 7000 eKr, papit aloittivat välittömästi levyjen siirtämisen ja he pystyvät siirtämään yhden levyn sekunnissa. Koska maailmanloppu on tulossa, jos levyjä on 64?

Tehottomuus ei kuitenkaan johdu huonosta ohjelmasta, vaan ongelma on sellainen, että sille ei löydy nopeampaa ratkaisua.

Pikajärjestäminen (Quicksort)

Taulukossa on alkioita mielivaltaisessa järjestyksessä. Halutaan järjestää ne suuruusjärjestykseen (pienin ensin).

Aikaisemmin on esitetty vaihtojärjestäminen ja lisäysjärjestäminen. Pikajärjestäminen on keskimäärin näitä selvästi nopeampi.

Pikajärjestämisen perusidea:

• Valitaan joku taulukon alkioista, k, sarana-alkioksi (pivot).

• Järjestetään taulukko uudelleen siten, että kaikki k:ta pienemmän alkiot ovat taulukon alkuosassa ja suuremmat tai yhtäsuuret alkiot taulukon loppuosassa.

• Jaetaan taulukko kahteen osaan, alkuosaan (jonka kaikki alkiot ovat k:ta pienempiä) ja loppuosaan (jonka kaikki alkiot ovat >= k). Järjestetään osat erikseen samalla menetelmällä (molemmille osille valitaan uusi oma sarana-alkio)

• Taulukon jakaminen k:ta pienempiin ja suurempiin alkioihin tapahtuu seuraavasti: Käydään taulukkoa läpi yhtä aikaa alusta ja lopusta. Kun alussa kohdataan alkio, joka on >= k ja lopussa alkio, joka on < k, vaihdetaan ne keskenään. Läpikäyminen päättyy, kun alku- ja loppuosoittimet kohtaavat toisensa.

public class Pikajarjesta {
  private static void pikajarjesta(int[] taulu, int alku, int loppu) {
    int sarana, vasen, oikea, apu;

    vasen = alku;
    oikea = loppu;
    sarana = taulu[(alku+loppu) / 2];
    do {
      while (taulu[vasen] < sarana)
	vasen++;
      while (sarana < taulu[oikea])
	oikea--;
      if (vasen <= oikea) {
	apu = taulu[vasen];
	taulu[vasen] = taulu[oikea];
	taulu[oikea] = apu;
	vasen++;
	oikea--;
      }
    } while (vasen < oikea);
    if (alku < oikea)
      pikajarjesta(taulu, alku, oikea);
    if (vasen < loppu)
      pikajarjesta(taulu, vasen, loppu);
  }


  public static void main(String[] args) {
    int[] taulukko = {20, 60, 30, 10, 90,
		      80, 70,  0, 40, 50};
    int i, koko;

    koko = taulukko.length;
    pikajarjesta(taulukko, 0, koko-1);
    System.out.println("Taulukko nyt:");
    for (i = 0; i < koko; i++)
      System.out.print(taulukko[i] + "  ");
    System.out.println();
  }
}
      

Viestinvälitystä olioiden välillä

Tarkastellaan kauppaesimerkkiä. Kaupalla on varasto, jossa on erilaisia tuotteita. Jokaisesta tuotteesta on vastuussa yksi työntekijä, joka tilaa tuotetta tarvittaessa lisää.

Luokat

Tyontekija

Kentät

• String nimi: työtekijän nimi

Konstruktori ja metodit

• Tyontekija(String nimi): konstruktori

• void tilaa(VarastoTuote tuote): metodi, jolla tuotetta tilataan lisää

VarastoTuote

Kentät

• String tuote: tuotteen nimi

• int maara: tuotteen määrä varastossa

• Tyontekija tilaaja: tuotteesta vastuussa oleva työntekijä

Konstruktori ja metodit

• VarastoTuote(Tyontekija tilaaja, String tuote): konstruktori

• String annaTuote(): palauttaa tuotteen nimen

• boolean osta(int paljonko): metodi, jolla tuotetta voi ostaa, jos sitä on tarpeeksi. Jos tuotetta ei ole tarpeeksi, vastaava työntekijä tilaa sitä lisää

• void vieVarastoon(int paljonko): lisää tuotteen määrää varastossa.

class Tyontekija {

  private String nimi;

  public Tyontekija(String nimi) {
    this.nimi = nimi;
  }

  public void tilaa(VarastoTuote tuote1) {
    System.out.println(nimi + " tilaa lisää " + tuote1.annaTuote());
    tuote1.vieVarastoon(10);
  }
}


class VarastoTuote {
  
  private String tuote;
  private int maara;
  private Tyontekija tilaaja;

  public VarastoTuote(Tyontekija tilaaja, String tuote) {
    this.maara = 0;
    this.tilaaja = tilaaja;
    this.tuote = tuote;
  }

  public String annaTuote() {
    return tuote;
  }

  public boolean osta(int montako) {
    boolean onnistui = false;
    if (montako <= maara) {
      maara = maara - montako;
      System.out.println(tuote + " ostettiin " + montako);
      onnistui = true;
    }
    else
      tilaaja.tilaa(this);
    return onnistui;
  }

  public void vieVarastoon(int paljonko) {
    maara = maara + paljonko;
  }
}


public class KauppaEsim{

  public static void main(String[] args) {
    final int MAX_MYYNNIT = 30;
    int myynnit = 0;
    Tyontekija matti, ulla;
    VarastoTuote leipaa, kaljaa;

    matti = new Tyontekija("Matti Mainio");
    ulla = new Tyontekija("Ulla Virtanen");
    leipaa = new VarastoTuote(matti, "leipää");
    kaljaa = new VarastoTuote(ulla, "kaljaa");
    while (myynnit < MAX_MYYNNIT) {
      if (leipaa.osta(2))
	myynnit++;
      if (kaljaa.osta(5))
	myynnit++;
    }
  }
}
    

Ohjelman tuloste:

Matti Mainio tilaa lisää leipää

Ulla Virtanen tilaa lisää kaljaa

leipää ostettiin 2

kaljaa ostettiin 5

leipää ostettiin 2

kaljaa ostettiin 5

leipää ostettiin 2

Ulla Virtanen tilaa lisää kaljaa

leipää ostettiin 2

kaljaa ostettiin 5

leipää ostettiin 2

kaljaa ostettiin 5

Matti Mainio tilaa lisää leipää

Ulla Virtanen tilaa lisää kaljaa

leipää ostettiin 2

kaljaa ostettiin 5

leipää ostettiin 2

kaljaa ostettiin 5

leipää ostettiin 2

Ulla Virtanen tilaa lisää kaljaa

leipää ostettiin 2

kaljaa ostettiin 5

leipää ostettiin 2

kaljaa ostettiin 5

Matti Mainio tilaa lisää leipää

Ulla Virtanen tilaa lisää kaljaa

leipää ostettiin 2

kaljaa ostettiin 5

leipää ostettiin 2

kaljaa ostettiin 5

leipää ostettiin 2

Ulla Virtanen tilaa lisää kaljaa

leipää ostettiin 2

kaljaa ostettiin 5

leipää ostettiin 2

kaljaa ostettiin 5

Matti Mainio tilaa lisää leipää

Ulla Virtanen tilaa lisää kaljaa

leipää ostettiin 2

kaljaa ostettiin 5

leipää ostettiin 2

kaljaa ostettiin 5

Ilmentymämuuttujat ja luokkamuuttujat

Muuttujia voidaan määritellä metodeissa ja luokissa.

Metodissa määritelty muuttuja on olemassa vain metodin suorituksen ajan eikä sillä ole oletusalkuarvoa

Luokassa määritellyillä muuttujilla on oletusalkuarvo ja ne ovat olemassa metodien suorituksesta riippumatta.

Aikaisemmissa esimerkeissä luokassa määritellyt muuttujat ovat olleet sellaisia, jotka syntyvät, kun olio syntyy. Näitä muuttujia sanotaan ilmentymämuuttujiksi. Jokaisella oliolla on omat ilmentymämuuttujien arvot.

On myös mahdollista määritellä luokan kaikille olioille yhteisiä muuttujia, luokkamuuttujia. Tämä tehdään static-määreellä. Jos esimerkiksi määritellään

public class Opiskelija {

private String nimi;

private int pisteet;

private static int lkm = 0;

niin kaikki Opiskelija-oliot jakavat saman

lkm-muuttujan. Muuttujan lkm arvo on siis sama jokaisella Opiskelija-oliolla. Eri olioilla ei ole omaa kopiotaan

lkm-muuttujan arvosta, vaan arvo on tallennettu vain yhteen kertaan.

Luokkamuuttujaa kutsutaan staattiseksi muuttujaksi.

Luokkametodit

Miten luokkamuuttujiin päästään käsiksi?

Luokkamuuttujan arvoa voidaan tutkia ja muuttaa luokan tavallisilla metodeilla. Esimerkiksi luokan Opiskelija konstruktori voitaisiin kirjoittaa

public Opiskelija(String nimi) {

this.nimi = nimi;

this.pisteet = 0;

lkm++;

}

Sen lisäksi voidaan kirjoittaa erityisiä luokkametodeja, jotka voivat käsitellä vain luokkamuuttujia, mutta eivät ilmentymämuuttujia. Esimerkiksi Opiskelija-luokalle voitaisiin kirjoitttaa luokkametodi annaLkm(). Se, että kysymyksessä on luokkametodi, kerrotaan static-määreellä.

public static int annaLkm() {

return lkm;

}

Toisessa luokassa olevasta metodista luokkametodia kutsutaan syntaksilla Luokka.metodi(), esimerkiksi yo. metodia kutsuttaisiin

int maara;

maara = Opiskelija.annaLkm();

Luokkametodit eivät voi käyttää ilmentymämuuttujia eivätkä kutsua ilmentymämetodeja.

class Opiskelija {
  private String nimi; // opiskelijan nimi
  private int pisteet; // voi olla vain 0-100
  private static int lkm = 0;

  public Opiskelija(String nimi) {
    this.nimi = nimi;
    this.pisteet = 0;
    lkm++;
  }

  public String mikaNimi() {
    return nimi;
  }

  public int mitkaPisteet() {
    return pisteet;
  }

  public static int annaLkm() {
    return lkm;
  }


  public boolean asetaPisteet(int uudetPisteet) {
    if (uudetPisteet >= 0 && uudetPisteet <= 100 ) {
       pisteet = uudetPisteet;
       return true;    // onnistui
    }
    else return false; // virheelliset pisteet
  }

 public String toString() {
   return this.nimi + "\t\t" + this.pisteet;
 }
}     

public class OpiskelijaEsim {

  public static void main(String[] args) {

    Opiskelija aila, arto, vilma;
    int maara;

    maara = Opiskelija.annaLkm();
    System.out.println("Opiskelijoita " + maara);
    aila = new Opiskelija("Aila A");
    maara = Opiskelija.annaLkm();
    System.out.println("Opiskelijoita " + maara);
    arto = new Opiskelija("Arto B");
    maara = Opiskelija.annaLkm();
    System.out.println("Opiskelijoita " + maara);
    vilma = new Opiskelija("Vilma V");
    maara = Opiskelija.annaLkm();
    System.out.println("Opiskelijoita " + maara);
    aila = new Opiskelija("Aila C");
    maara = Opiskelija.annaLkm();
    System.out.println("Opiskelijoita " + maara);
  }
}

Luokkamuuttujat vakioina

Myös kaikille olioille yhteiset vakiot kannattaa usein määritellä luokkamuuttujiksi. Esimerkiksi aikaisemmin esitetyssä LimsaAutomaatti-luokassa limsapullon hinta voidaan määritellä luokkamuuttujana:

public class LimsaAutomaatti {

private int limsojenLkm;

private double rahat;

private final static double HINTA = 5.0;

// ----- konstruktori: ------------

public LimsaAutomaatti() {

limsojenLkm = 0;

rahat = 0;

}

// ----- aksessorit: -----------

public void lisaaLimsoja(int maara) {

limsojenLkm = limsojenLkm + maara;

}

public void ostaLimsa(double annettuRaha) {

if ( limsojenLkm >= 1 &&

annettuRaha >= HINTA) {

rahat = rahat + annettuRaha;

limsojenLkm--;

}

}

// muiden metodien määrittelyt

// ...

}