Correction

Version récursive :

1
2
3
4
5
6
7
def fibonacci(n):
    if n == 0 :
        return 0   
    elif n == 1 :
        return 1
    else :
        return fibonacci(n-1) + fibonacci(n-2)

Version impérative : 

1
2
3
4
5
6
7
8
def fibonacci(n):
    a = 0
    b = 1
    for k in range(n-1):
        t = b
        b = a + b
        a = t
    return b

Version programmation dynamique :

1
2
3
4
5
6
7
def fibonacci(n):
    d = {}
    d[1] = 1
    d[2] = 1
    for k in range(3, n+1):
        d[k] = d[k-1] + d[k-2]
    return d[n]