Pour aller plus loin : récursivité et complexité

Une fonction récursive est une fonction qui s'appelle elle-même sur un problème plus petit, jusqu'à un cas simple résolu directement ; la complexité d'un algorithme mesure comment son temps d'exécution (ou sa mémoire) augmente avec la taille des données. Ces deux notions sont hors du programme de l'épreuve E3 du BTS SIO, mais elles servent en SLAM et dans toute poursuite d'études : ce chapitre en donne l'essentiel, avec des exemples en Python.

Une fonction qui s'appelle elle-même

La factorielle de n vaut n! = n × (n − 1) × … × 1. On remarque que n! = n × (n − 1)! : pour calculer 5!, il suffit de savoir calculer 4!, puis de multiplier par 5. Et 1! vaut 1, sans calcul. C'est une définition récursive : elle se sert d'elle-même, sur un nombre plus petit.

Fonction Factorielle(n : entier) : entier
// Précondition : n ≥ 1
    Si n = 1 Alors
        Retourner 1                       // cas de base
    Sinon
        Retourner n × Factorielle(n - 1)  // appel récursif
    FinSi
FinFonction

def factorielle(n):
    if n <= 1:
        return 1                        # cas de base
    return n * factorielle(n - 1)       # appel récursif


print(factorielle(5), factorielle(20))

120 2432902008176640000

Toute fonction récursive a deux parties, et il en faut absolument deux :

1. Un cas de base, résolu sans appel récursif. Le programme dit « nécessité d'un test » et « nécessité de cas particuliers résolus sans appel à la récursivité ».
2. Un appel récursif sur un problème plus petit, qui se rapproche du cas de base. C'est ce qui garantit la finitude.

La pile d'appels

Quand factorielle(4) appelle factorielle(3), le premier appel n'est pas fini : il attend le résultat pour faire sa multiplication. Python garde chaque appel en attente, avec ses variables locales, sur une pile d'appels. Les appels s'empilent jusqu'au cas de base, puis se dépilent en renvoyant leurs résultats.

Cette pile a une taille limitée. Par défaut, Python refuse d'empiler plus de 1 000 appels environ : factorielle(5000) lève RecursionError: maximum recursion depth exceeded. Une fonction récursive sans cas de base (ou dont l'appel ne se rapproche pas du cas de base) provoque la même erreur : c'est l'équivalent récursif de la boucle infinie.

Récursif ou itératif ?

Tout algorithme récursif peut s'écrire avec une boucle, et inversement. La factorielle itérative est le produit du chapitre 4. Le programme de maths cite d'ailleurs la « conversion en algorithme non récursif ».

La récursivité brille quand les données sont imbriquées. Une arborescence de dossiers contient des fichiers et des sous-dossiers, qui contiennent eux-mêmes des fichiers et des sous-dossiers… Calculer sa taille totale avec des boucles est pénible ; en récursif, c'est quatre lignes :

def taille(element):
    """Taille d'un fichier (un entier, en Ko) ou d'un dossier (un dictionnaire)."""
    if isinstance(element, int):      # cas de base : un fichier
        return element
    total = 0
    for contenu in element.values():  # un dossier : la somme de ses contenus
        total = total + taille(contenu)
    return total


partage = {
    "compta": {"bilan.xlsx": 820, "factures": {"f1.pdf": 120, "f2.pdf": 95}},
    "rh": {"contrats": {"modele.docx": 45}},
    "lisezmoi.txt": 2,
}
print(taille(partage), "Ko")

1082 Ko

isinstance(element, int) teste si l'élément est un entier. La fonction ne sait pas à l'avance combien de niveaux de dossiers il y a : chaque appel traite un niveau et délègue les sous-dossiers à d'autres appels.

Attention en revanche aux récursions qui recalculent la même chose. La suite de Fibonacci écrite naïvement, fib(n) = fib(n - 1) + fib(n - 2), fait 21 891 appels pour fib(20) et 2 692 537 pour fib(30), car fib(28) est calculé deux fois, fib(27) trois fois, et ainsi de suite. La version itérative du chapitre 4 fait 30 tours de boucle.

La complexité d'un algorithme

Deux programmes peuvent donner le même résultat avec des temps très différents. Mesurer le temps en secondes dépend de la machine ; on compte plutôt le nombre d'opérations significatives (comparaisons, affectations, tours de boucle) en fonction de la taille n des données. C'est ce que tu as fait pour les tris.

On s'intéresse surtout au pire cas, qui donne une garantie, et à la façon dont le coût grandit quand n grandit, pas au nombre exact d'opérations.

La notation O

La notation O (« grand O ») décrit l'ordre de grandeur du nombre d'opérations, en ignorant les constantes et les termes secondaires : n(n − 1)/2 comparaisons s'écrit O(n²), 3n + 2 s'écrit O(n).

À raison de cent millions d'opérations par seconde (un ordre de grandeur pour un programme simple), O(n²) sur un million d'éléments représente plus de deux heures et demie de calcul ; O(n log n), une fraction de seconde. Le choix de l'algorithme compte bien plus que la vitesse de la machine.

Pour estimer la complexité d'un algorithme, trois règles suffisent :

• des instructions sans boucle coûtent O(1) ;
• une boucle de n tours qui contient un corps en O(1) coûte O(n) ; deux boucles imbriquées de n tours coûtent O(n²) (on multiplie) ; deux boucles successives coûtent O(n) + O(n) = O(n) (on additionne, et on garde le plus grand terme) ;
• une boucle qui divise la taille par 2 à chaque tour coûte O(log n).

On parle aussi de complexité en mémoire (ou spatiale) : la place occupée en plus des données. Trier sur place coûte O(1) en mémoire ; construire une nouvelle liste de n éléments, O(n) ; une récursion de profondeur n, O(n) pour la pile d'appels.

Exercices

def somme_chiffres(n):
    if n < 10:                               # cas de base
        return n
    return n % 10 + somme_chiffres(n // 10)  # appel sur un nombre plus petit


print(somme_chiffres(2026))

def puissance(x, n):
    if n == 0:
        return 1
    return x * puissance(x, n - 1)

# A
total = 0
for i in range(n):
    total = total + i
for j in range(n):
    total = total - j

# B
nb = 0
for i in range(n):
    for j in range(i):
        nb = nb + 1

# C
k = n
while k > 1:
    k = k // 2

# D
x = t[0] + t[n - 1]

def dicho_rec(t, x, deb, fin):
    if deb > fin:
        return -1
    milieu = (deb + fin) // 2
    if t[milieu] == x:
        return milieu
    if t[milieu] < x:
        return dicho_rec(t, x, milieu + 1, fin)
    return dicho_rec(t, x, deb, milieu - 1)


t = [3, 8, 15, 23, 42, 56, 91]
print(dicho_rec(t, 42, 0, len(t) - 1), dicho_rec(t, 10, 0, len(t) - 1))