Pour aller plus loin

Suite de Fibonacci v2

Au début du cours (2 exemples classiques) on implémente une fonction récursive pour calculer la suite de Fibonacci. Malheureusement, on a vu que cette implémentation n'était pas très efficace. En effet, on peut montrer qu'elle est exponentielle : \(O(\phi^n)\).

Or il existe une façon de le faire en temps linéaire.

L'objet de cet exercice est donc d'implémenter une version linéaire (\(O(n)\)) pour calculer la suite de Fibonacci.

Rappel de définition

Pour rappel, la suite de Fibonacci est définie, pour \(n\in\mathbb{N}\), comme suit :

\[fibonacci(n) = \left\{ \begin{array}{l l} 0 & \quad \text{si $n = 0$,}\\ 1 & \quad \text{si $n = 1$,}\\ fibonacci(n - 2) + fibonacci(n - 1) & \quad \text{si $n > 1$}. \end{array} \right. \]

Question

Implémenter un fonction récursive fibonacci telle que :

  • l'entrée est \(n\) un entier positif ;

  • la sortie est le terme \(n\) de la suite de Fibonacci (\(fibonacci(n)\)) ;

  • la complexité est en \(O(n)\).

Les indices sont en ordre décroissant de difficulté. Il est conseillé de les révéler successivement.

Indice

La fonction fibonacci ne va pas être récursive par elle-même, mais plutôt appeler une fonction récursive qui retourne plus de données que demandées.

Indice

On peut facilement remarquer que \(fibonacci(n-2)\) est utilisé à la fois pour calculer \(fibonacci(n)\) et \(fibonacci(n-1)\)

Or \(fibonacci(n-1)\) est aussi utilisé pour \(fibonacci(n)\)

Donc, on calcule deux fois \(fibonacci(n-2)\) pour calculer \(fibonacci(n)\).

On va donc chercher à transmettre à fibonacci(n) à la fois \(fibonacci(n-1)\) et \(fibonacci(n-2)\).

Pour ce faire, on va implémenter une fonction récursive auxiliaire, fibonacci_aux, telle que :

  • l'entrée est \(n\) un entier non nul ;

  • la sortie est le couple \((fibonacci(n), fibonacci(n-1))\) ;

  • la complexité est en \(O(n)\)

Indice

La fonction fibonacci_aux se doit d'être de complexité linéaire.

Elle ne peut donc faire qu'un seul appel récursif à chaque fois.

Indice

Le corps de la fonction fibonacci_aux est très similaire à celui de la version avec une boucle for ou while

Indice

Pour rappel voici la version avec une boucle for

1
def fibonacci(n):
2
    if n == 0:
3
        return 0
4
    if n == 1:
5
        return 1
6
7
    f_i1 = 0
8
    f_i = 1
9
    for _ in range(1, n):
10
        tmp = f_i + f_i1
11
        f_i1 = f_i
12
        f_i = tmp
13
    return f_i

Solution

1
def fibonacci_aux(n):
2
    if n == 1 :
3
        return (0, 1)
4
    # On récupère f(n-1) et f(n-2) grace à l'appel récursif
5
    f_n1, f_n2 = fibonacci_aux(n-1)
6
    f_n = f_n1 + f_n2
7
    return (f_n, f_n1)
8
9
def fibonacci(n):
10
    if n == 0:
11
        return 0
12
    f_n, _f_n1 = fibonacci_aux(n)
13
    return f_n
Question
À l'aide du module time écrire un code qui compare les différentes implémentations de la suite de Fibonacci.
Indice
Dans le module time, on trouve la fonction time.time() qui permet d'obtenir l'heure courante
Indice
En soustrayant l'heure de fin d'execution d'un code par l'heure de début, on obtient la durée d'exécution
1
debut = time.time()
2
3
# On execute notre fonction
4
fn()
5
6
fin = time.time()
7
8
duree = fin - debut