Rekursio
From Wikipedia, the free encyclopedia
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ä luonnollisille luvuille rekursiivisesti seuraavaan tapaan:
Rekursioyhtälöllä tarkoitetaan yhtälöä, jossa annetun funktion arvo voidaan laskea käyttäen hyväksi sen edellisissä pisteissä saamia arvoja. Esimerkkinä rekursioyhtälöstä on Fibonaccin jono
kun n > 2.