Ohjelmoinnin perusteita: iterointi ja rekursio

Iterointi on toistoa silmukassa (for, while, do) kunnes lopetusehto tulee vastaan. Esimerkiksi taulukon läpikäyminen toteutetaan usein juuri silmukassa ennen kaikkea sen helppouden takia. Yksinkertainen esimerkki iteroinnista on silmukka joka tulostaa omaa arvoaan.

// aloitetaan silmukka
for(int i = 0; i < 100; i++) {
        // tulostetaan silmukan arvo
	System.out.println(i);
}

Jos taasen halutaan kääntää String, senkin toteuttaminen iteroimalla on helppoa.

// yksinkertainen silmukka joka toteutuu niin kauan kunnes
// i:n arvo on alle muuttujan teksti pituus
while(i < teksti.length()) {
	kaannetty = teksti.charAt(i) + kaannetty;
	i++;
}

Rekursio tarjoaa toisenlaisen keinon toteuttaa samoja asioita kuin iterointi. Itse rekursion idea on yksinkertainen, metodi tai funktio kutsuu itse itseään kunnes ollaan tilanteessa jossa ei ole enää tarvetta jatkaa.

Jos ajatellaan tilannetta jossa tarvitsemme luvun 3 kertomaa, on rekursio mainio keino saada tämä laskettua.

public static int kertomaRekursiolla(int n) {
	// jos argumentti on 0, palautamme 1
	if(n == 0) { 
		return 1;
	} else {
	// muussa tapauksessa jatkamme rekursiota ja vähennämme
	// argumentin arvoa yhdellä
		return n * kertomaRekursiolla(n - 1);
	}
}

Hyvä käytännön esimerkki rekursion eduista iterointiin nähden on hakemistojen läpi käyminen. Jos kutsumme metodia lueHakemisto(String polku) joka taas löytää alihakemiston, voi se kutsua itseään ja näin päästä lukemaan myös alihakemiston tietoja. Myös alihakemiston tapauksessa toimitaan samoin, eli jos löytyy uusi alihakemisto, metodi kutsuu itseään. Kun alihakemistoja ei enää löydy, tulostaa metodi hakemiston tiedostot ja ohjelma palaa ylemmälle hakemistotasolla olevalle metodille.

Alla vielä esimerkkikoodi ohjelmasta joka kääntää tekstin sekä iteroiden, että rekursiolla.

public class IterointiJaRekursio {

	public static String kaannaIteroiden(String teksti) {
		String kaannetty = "";
		int i = 0;
		
		while(i < teksti.length()) {
			kaannetty = teksti.charAt(i) + kaannetty;
			i++;
		}
		return kaannetty;
	}
	
	public static String kaannaRekursiolla(String teksti) {
		if(teksti.length() > 1) {
			return kaannaRekursiolla(teksti.substring(1)) + teksti.substring(0, 1);
		} else {
			return teksti;
		}
	}
	
	public static void main(String[] args) {
		System.out.println(kaannaIteroiden("nedioreti dlroW olleH"));
		System.out.println(kaannaRekursiolla("alloisruker dlroW olleH"));
	}

}
Advertisements

Vastaa

Täytä tietosi alle tai klikkaa kuvaketta kirjautuaksesi sisään:

WordPress.com-logo

Olet kommentoimassa WordPress.com -tilin nimissä. Log Out / Muuta )

Twitter-kuva

Olet kommentoimassa Twitter -tilin nimissä. Log Out / Muuta )

Facebook-kuva

Olet kommentoimassa Facebook -tilin nimissä. Log Out / Muuta )

Google+ photo

Olet kommentoimassa Google+ -tilin nimissä. Log Out / Muuta )

Muodostetaan yhteyttä palveluun %s