Rekursioon matemaatikas ja rekurrentsed arvujadad

Matemaatikas kasutatakse rekursiooni rekurrentsetes arvujadades. Arvujada on rekurrentne siis, kui jada mingi väärtus sõltub eelmisest väärtusest.

Näited:

Aritmeetiline jada: Iga järgmine väärtus on eelmisest d võrra suurem.

[d] näitab, et d on alamindeks.

Üldvalem: A[n] = A[n-1] + d

Olgu A[0] = 1, d = 3, siis jada näeb välja selline:
1 4 7 10 13 16 ...

Geomeetriline jada: Iga järgmine väärtus on eelmisest q korda suurem.

Üldvalem: A[n] = A[n-1] * q

Olgu A[0] = 1, q = 2, siis jada näeb välja nii:
1 2 4 8 16 32 ...

Fibonacci arvud: Iga järgnev liige on kahe eelneva liikme summa. (F[1] = 1, F[2] = 1)

Üldvalem: F[n] = F[n-1] + F[n-2]

F[1] = 0
F[2] = 1
F[3] = F[2] + F[1] = 1 + 0 = 1
F[4] = F[3] + F[2] = 1 + 1 = 2
F[5] = F[4] + F[3] = 1 + 2 = 3
...

Kus siin rekursioon on? See üldvalem on ju funktsioon. Et leida viiendat väärtust, tuli meil funktsiooni uuesti kasutada, aga seekord eelmiste väärtustega. Ja nii tegimegi, kuni saime valemi, kus on ainult meile teadaolevad väärtused (F[1], F[0]). Kui neid ei oleks, siis me ei saaks väärtust arvutada, sest oleks vaja lõpmatult palju eelmisi väärtusi otsida. Seda juhtumit võib julgelt rekursiooniks kutsuda.