Rekursio
Wikipedia
Rekursio on matemaattinen keino määritellä funktioita niin, että funktion arvo tietyssä pisteessä riippuu funktion arvosta edellisessä pisteessä. Rekursioyhtälö annetaan yleensä kaksiosaisena: toinen osa määrittelee funktion arvon jollain tunnetulla alkuarvolla (alkuarvoja voi olla myös useita) ja toinen osa muulloin. Esimerkiksi kertoma on helppo määritellä rekursiivisesti seuraavaan tapaan:
(kertoma on määritelty vain luonnollisille luvuille n).
Myös tietotekniikassa käytetään rekursiivisia ohjelmarutiineja. Niissä idea on sama kuin matemaattisesti määritellyissä rekursiivisissa funktioissa ja rekursiivisesti lasketut välitulokset tallennetaan useimmiten pinoon. Viimeisellä rekursiokierroksella pinosta kerätään vastaukset käänteisessä järjestyksessä. Pseudokoodina kertoma voitaisiin laskea seuraavaan tapaan:
procedure factorial(integer n):
if n < 2
return 1
else
return n * factorial(n-1)
Yleinen ohjelmointivirhe on nk. ikuinen silmukka, jossa funktiokutsu ei koskaan palaa, vaan etenee yhä toistuvasti saman funktion kautta rekursiivisesti kiertäen.
Mikäli ohjelmakoodin rekursiivinen osa on aina ohjelmakoodin lopussa, voidaan rekursio muuttaa tavalliseksi silmukaksi. Tällöin kyseessä on ns. häntärekursio.
