====== Suite de Fibonacci : encore un algorithme ======

Voici le programme complété pour la technique récursive :
<code python fibonacci07_fonction_recursive.py3>
#! /usr/bin/env python
# -*- coding: utf-8 -*-
"""
Calculs des premiers éléments de la suite de Fibonacci.
Référence : http://fr.wikipedia.org/wiki/Suite_de_Fibonacci
Application de la définition par récursivité.
"""
def fibonacci_item_recursive(n):
    """
    Renvoie l'élément d'indice n de la suite de Fibonacci
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci_item_recursive(n-1)+fibonacci_item_recursive(n-2)

if __name__ == '__main__':
    i = input("Suite de Fibonacci. Donnez l'indice de l'élément souhaité ? ")
    print("Élément de la suite : "),
    printfibonacci_item_recursive(i)
    print('Premiers éléments de la suite : ')
    for j in range(10):
        print(j,fibonacci_item_recursive(j))
</code>


La page Wikipedia sur la suite de Fibonacci introduit aussi un [[wp>fr:Suite_de_Fibonacci#Algorithme_logarithmique|algorithme logarithmique]]. Même s'il est très intéressant à décortiquer, on peut se contenter de simplement l'appliquer :

<code python fibonacci08_fonction_algo_log.py3>
#! /usr/bin/env python
# -*- coding: utf-8 -*-
"""
Calculs des premiers éléments de la suite de Fibonacci.
Référence : http://fr.wikipedia.org/wiki/Suite_de_Fibonacci
Application de l'algorithme logarithmique
http://fr.wikipedia.org/wiki/Suite_de_Fibonacci#Algorithme_logarithmique
"""
def fibo2(n):
    """Renvoie F_{n-1}, F_n"""
    if n == 0:  # cas de base
        return 1, 0  # F_{-1}, F_0
    else:         # récurrence
        f_k_1, f_k = fibo2(n//2)        # F_{k-1}, F_k   avec k = n/2
        f2_k = f_k**2                   # F_k^2
        if n%2 == 0:  # n pair
            return f2_k + f_k_1**2,    f_k*f_k_1*2 + f2_k       # F_{2k-1}, F_{2k}
        else:         # n impair
            return f_k*f_k_1*2 + f2_k, (f_k + f_k_1)**2 + f2_k  # F_{2k},   F_{2k+1}
 
def fibonacci_item_logarithmic(n):
    """Renvoie F_n"""
    return fibo2(n)[1]

if __name__ == '__main__':
    i = input("Suite de Fibonacci. Donnez l'indice de l'élément souhaité ? ")
    print("Élément de la suite : "),
    printfibonacci_item_logarithmic(i)
    print('Premiers éléments de la suite : ')
    for j in range(10):
        print(j,fibonacci_item_logarithmic(j))
</code>

Sur la même page wikipedia, on trouve une [[wp>fr:Suite_de_Fibonacci#Expression_fonctionnelle|expression fonctionnelle]], de complexité apparente en temps constant, aussi connue sous le nom de [[wp>fr:Suite_de_Fibonacci#Avec_la_formule_de_Binet|formule de Binet]], mais qui passe par le calcul du nombre irrationnel $\sqrt{5}$, ce qui pose un problème pour conserver une précision des chiffres significatifs par rapport à l'arithmétique entière.

Le langage Python permet également de mettre en œuvre des générateurs (generator) : //cf.// [[http://www.koderdojo.com/blog/python-fibonacci-number-generator]] et [[http://www.bogotobogo.com/python/python_generators.php]]

<code python fibonacci09_generator.py3>
#! /usr/bin/env python
# -*- coding: utf-8 -*-
"""
Calculs des premiers éléments de la suite de Fibonacci.
Référence : http://fr.wikipedia.org/wiki/Suite_de_Fibonacci
"""
def fibonacci_gen(n):
    """
    Renvoie l'élément d'indice n de la suite de Fibonacci
    """
    a, b = 0, 1
    for _ in range(n):
        yield a
        a, b = b, a + b

if __name__ == '__main__':
    i = int(input("Suite de Fibonacci. Donnez l'indice max des éléments souhaités ? "))
    print("Le générateur : "),
    print(fibonacci_gen(i))
    print('Éléments de la suite : ')
    for j in fibonacci_gen(i):
        print(j)
</code>

Nous disposons à présent de plusieurs méthodes/fonctions pour calculer les éléments de la suite de Fibonacci.

Pour rechercher quel est le meilleur algorithme, [[suite_de_fibonacci-5|cliquez ici !]]