Aller au contenu

Suite définie par récurrence⚓︎

La présentation des suites factorielle et de Fibonacci est incontournable.

  • Elles sont les plus simples (sans être triviales) de leur genre,
  • elles permettent de comprendre des phénomènes profonds, des algorithmes qui se généralisent,
  • leur utilisation est importante en dénombrement.

Factorielle⚓︎

Pour \(n\in \mathbb N\), la factorielle de \(n\), notée \(n!\) est le produit des entiers de \(1\) à \(n\).

  • \(0! = 1\), comme tout produit vide ;
  • \(1! = 1\) ;
  • \(2! = 1\times 2 = 2\) ;
  • \(3! = 1\times 2 \times 3 = 6\) ;
  • \(4! = 1\times 2 \times 3 \times 4 = 24\) ;

Avec NumWorks⚓︎

  • Le symbole ! est accessible avec alpha＋.
  • On peut l'utiliser dans une définition explicite pour une suite. C'est facile.

Avec Python⚓︎

C'est facile aussi, la fonction factorial est incluse dans le module math :

🐍 Script Python
from math import factorial
for n in range(20):
    print(n, "-->", factorial(n))
📤 Sortie
0 --> 1
1 --> 1
2 --> 2
3 --> 6
4 --> 24
5 --> 120
6 --> 720
7 --> 5040
8 --> 40320
9 --> 362880
10 --> 3628800
11 --> 39916800
12 --> 479001600
13 --> 6227020800
14 --> 87178291200
15 --> 1307674368000
16 --> 20922789888000
17 --> 355687428096000
18 --> 6402373705728000
19 --> 121645100408832000

Fabrication⚓︎

Il est cependant intéressant de comprendre comment la fabriquer. Voici plusieurs méthodes avec des critiques :

🐍 Script Python
def factorielle(n):  # (1)!
    "factorielle de n, version récursive"
    if n == 0:  # (2)!
        return 1  # (3)!
    else:
        return n * factorielle(n - 1)  # (4)!
  1. On définit une fonction, ne pas oublier les deux points à la fin.
  2. Un test d'égalité, ne pas oublier les deux = ; ce n'est pas une affectation.
  3. On renvoie un résultat, ne pas oublier d'indenter correctement le code (le décalage).
  4. La formule dans le cas général, si \(n>0\), alors \(n! = n × (n-1)!\)
🐍 Console Python
>>> factorielle(5)
120
  • Tous les exemples Python peuvent être testés avec NumWorks.
  • La récursivité permet d'écrire du code élégant.
  • Cette méthode est simple et efficace pour le calcul d'une unique factorielle.
  • Cette méthode sera mauvaise pour de nombreux appels ; il vaut mieux stocker les résultats dans une liste.
🐍 Script Python
limit = 1000
f_n = 1
factorielle = [f_n]  # (1)!
for n in range(1, 1000):  # (2)!
    f_n = f_n * n  # (3)!
    factorielle.append(f_n)  # (4)!
  1. On définit une liste, ici avec un seul élément, égal à 1.
  2. On répète pour (for) \(n\) variant dans l'intervalle (range) \(1\) inclus à \(1000\) exclu.
  3. On calcule le terme suivant.
  4. On ajoute (append) à la fin de la liste le nouveau terme
🐍 Console Python
>>> factorielle[5]
120
  • Une liste permet d'avoir un accès rapide à factorielle[i] pour tout i dans l'intervalle \([\![0..1000[\![\)
  • Une liste peut-être étendue au besoin.
  • ⚠ Notez-bien que l'on utilise ici des crochets pour accéder aux valeurs de la liste ; factorielle n'est plus une fonction !

Fibonacci⚓︎

Avec la calculatrice NumWorks, il suffit d'utiliser le menu suite récurrente d'ordre deux, c'est facile.

En modifiant la définition, on peut fabriquer d'autres suites récurrentes d'ordre deux...