De manier waarop de rij van Fibonacci gedefinieerd is, is een voorbeeld van wat in de wiskunde een recursieve definitie genoemd wordt. De rij begint met 0 en 1 en vervolgens is elk volgende element van de rij steeds de som van de twee voorgaande elementen. Het
en
voor
Het begin van de reeks is dus
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Schrijf een recursieve functie fib
waaraan een getal
>>> fib(0)
0
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3