Rekursio

Mureakuha

Sisällysluettelo 1 Rekursio 1.1 Miten rekursio toimii? 1.2 Rekursion vaarat 1.3 Esimerkkirekursioita 1.3.1 Kertoma 1.3.2 Potenssi 1.3.3 Fibonaccin lukusarja 1.3.4 Binomikerroin

Rekursio

Rekursio eli uudelleen kutsu on hyvin yleisesti käytetty tapa ohjelmoinnissa, kun tarvitaan viittausta edellisestä tuloksesta. Rekursiota käytetään yleensä sellaisissa tilanteissa jossa funktion saamia tietoja käsitellään samalla tavalla kuin funktion tuottamaa tulostakin. Esimerkiksi erilaisten rekursiivisten lukusarjojen laskeminen, ennalta tuntemattoman datamäärän läpikäynti, sekä erilaiset sisällönhallinnan toimenpiteet. Varsinkin puun muodossa (esim. binääripuu) olevaa dataa käsitellään usein rekursiivisesti.

Rekursiivinen kutsu voi olla suora tai epäsuora. Suoralla rekursiolla tarkoitetaan että funktio kutsuu itseään. Epäsuoralla sitä että funktio kutsuu toista funktiota joka vuorostaan kutsuu sitä kutsunutta funktiota.

Miten rekursio toimii?

Rekursion toiminta on hyvin yksinkertainen: aliohjelma tai funktio kutsuu itseään tiettyjen määritelmien mukaisesti. Kun määrittelyn ehdot eivät enää täyty, rekursiivinen aliohjelma tai funktio lopettaa toimintansa.

Rekursion vaarat

Rekursiota käytettäessä tulee olla ehdottoman tarkka kahdesta kohdasta:

1. Aliohjelma tai funktio ei kutsu rekursion sisällä toisia aliohjelmia tai funktioita joissa on ristiviittaus itse rekursiiviseen aliohjelmaan tai funktioon
2. Rekursiivisen aliohjelman tai funktion rekursiokutsulle määritetty ehto täyttyy aina

Nämä molemmat ehdot huomioituna rekursiosta ei tule ikuista, estäen näin pahimmassa tapauksessa koneen kaatumisen muistin loppumiseen.

Esimerkkirekursioita

Kertoma

Kertoma (matematiikassa n!) saadaan laskettua helposti rekursion avulla:

function kertoma (luku)
   if (luku > 1)
      return kertoma (luku - 1) * luku
   else
      return 1

Potenssi

Potenssi (k^p) on käytännössä vain hieman monimutkaisempi kertoma.

function potenssi(k, p)
	a = 0;
        if(potenssi>0)
                a = k
		for(int i=0;i<(potenssi-1);i++)
			a = a*k

	else if(potenssi==0)
		return 1

        else if(potenssi<0)
		a = 1 / (potenssi(k, (-1*p)))

	return a

Fibonaccin lukusarja

Fibonaccin lukusarja (matematiikassa f(n) = f(n − 1) + f(n − 2)) lasketaan kahden edellisen tuloksen summasta. Lukusarja alkaa 1, 1, 2, 3, 5, 8, 13, 21...

function fibonacci (n)

   if (n < 1)
      return 0
   if (n < 3)
      return 1
   else
      return fibonacci (n - 1) + fibonacci (n - 2)

Todellisuudessa ykköstä pienemmät indeksit eivät kuulu Fibonaccin lukusarjaan, mutta pseudokoodin n < 1 lisää virheensietoa. Rekursio on kuitenkin erittäin huono tapa laskea Fibonaccin sarjan alkioita, koska se tekee valtavasti turhaa työtä laskiessaan samoja arvoja moneen kertaan.

Binomikerroin

Binomikerroin n!/(k!(n-k)!):

function binomikerroin (n,k)
	if( n == k && k > 0 )
		return 1
	else
		return binomikerroin( n-1, k )* n /( n-k)