Rekursio

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:

${\displaystyle f(n)=\left\{{\begin{matrix}1,&{\mbox{jos }}n{\mbox{ = 0}}\\n\cdot f(n-1)&{\mbox{muulloin}}\end{matrix}}\right.}$

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

${\displaystyle F_{1}=F_{2}=1}$

${\displaystyle F_{n}=F_{n-2}+F_{n-1}}$ kun n > 2.