Exempel

Ange n:te elementet i en rekursiv talföljd

Talföljden $1, \, 1,\, 2,\, 3,\, 5,\, \ldots$ kallas Fibonacciföljden. Varje tal bildas genom att addera de två föregående, och kan därför beskrivas av den rekursiva formeln $a_n = a_{n-1} + a_{n-2} \quad \text{där} \quad a_1=a_2=1.$ Vilket är tal nr $10$ i följden? För att beräkna det tionde talet behöver vi tal nr $9$ och $8$, som kräver att vi vet tal nr $7$ och $6$, som kräver att vi vet tal nr $5$ och $4$, osv. Eftersom följden är rekursiv måste vi veta alla tal fram till det tionde talet.

$n$	$a_{n-2}$	$a_{n-1}$	$a_n$
$6$	$3$	$5$	$3+5 = 8$
$7$	$5$	$8$	$5+8 = 13$
$8$	$8$	$13$	$8+13 = 21$
$9$	$13$	$21$	$13+21 = 34$
$10$	$21$	$34$	$21+34 = 55$

De tio första talen i följden blir alltså $1, \, 1,\, 2,\, 3,\, 5,\, 8,\,13,\,21,\,34,\,55$ och det tionde talet i följden är $55$.