Rekursioon

Programmeerimises nimetatakse rekursiooniks seda, kui funktsioon kutsub välja iseennast.

Kanooniline näide: faktoriaali arvutamine

Sageli tutvustatakse rekursiooni faktoriaali arvutamise näitel. Arvu n faktoriaal (n!) on defineeritud järgnevalt:

n! = 1 · 2 · 3 · ... · n

Näiteks arvu 3 faktoriaal on:

3! = 1 · 2 · 3 = 6

Ja arvu 4 faktoriaal on:

4! = 1 · 2 · 3 · 4 = 24

Kui me sedasi nende faktoriaalide arvutamist jätkame, siis märkame, et järgmise arvu faktoriaali saame kergesti kätte, kui teame talle eelneva arvu faktoriaali. Näiteks arvu 5 faktoriaali arvutamiseks piisab sellisest tehtest:

5! = 4! · 5 = 120

Seega võime nüüd defineerida, et et arvu n faktoriaal on arvu n enda ja talle eelneva arvu faktoriaali korrutis (välja arvatud see juhtum, et arvu 1 faktoriaaliks on alati 1). Ehk matemaatiliselt väljendudes:

n! = 1, kui n = 1

n! = (n - 1)! · n, kui n > 1

Siin definitsioonis aga ongi meil juba rekursioon - defineerimaks faktoriaali olemust, kasutame me faktoriaali ennast.

Selle matemaatilise definitsiooni põhjal saame me nüüd kirjutada faktoriaali arvutava funktsiooni mõnes programmeerimiskeeles:

 function faktoriaal(n) {
     if (n == 1)
         return 1;
     else
         return faktoriaal(n-1) * n;
  }