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 n-de getal van Fibonacci Fn wordt zo gegeven door:

F0=0,   F1=1

en

Fn=Fn1+Fn2

voor n>1.

Het begin van de reeks is dus

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Opgave

Schrijf een recursieve functie fib waaraan een getal nN moet doorgegeven worden. De functie moet het n-de Fibonaccigetal Fn teruggeven.  

Voorbeeld

>>> fib(0)
0
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3