Récursivité et diviser pour régner

Une fonction est récursive lorsque son corps contient au moins un appel à elle-même. Sa définition comporte deux parties : un ou plusieurs cas de base, traités sans aucun appel récursif, et un ou plusieurs cas récursifs, où le résultat cherché est assemblé à partir du résultat de la même fonction sur des données strictement plus petites. Écrire une fonction récursive, c'est traduire une définition par récurrence, par exemple $0! = 1$ et $\forall n \in \mathbb{N}^*,\ n! = n \times (n-1)!$ (voir le thème Définir un objet par récurrence du bloc Fondamental).

def factorielle(n):
    """Renvoie n!, pour n entier naturel.
    Précondition : n >= 0."""
    if n == 0:
        return 1
    return n * factorielle(n - 1)

L'appel factorielle(5) renvoie 120 et factorielle(0) renvoie 1. Rien n'est circulaire ici : chaque appel porte sur un entier strictement plus petit que le précédent, et la descente s'arrête au cas de base n == 0.

Deux fonctions sont mutuellement récursives lorsque chacune appelle l'autre, sans qu'aucune ne s'appelle nécessairement elle-même. Le mécanisme et les preuves sont identiques au cas d'une seule fonction : il faut des cas de base et une quantité qui décroît strictement à chaque appel, celui-ci passant d'une fonction à l'autre.

def est_pair(n):
    """Dit si l'entier naturel n est pair.
    Précondition : n >= 0."""
    if n == 0:
        return True
    return est_impair(n - 1)


def est_impair(n):
    """Dit si l'entier naturel n est impair.
    Précondition : n >= 0."""
    if n == 0:
        return False
    return est_pair(n - 1)

Pour n de $0$ à $5$, est_pair renvoie [True, False, True, False, True, False]. En Python, l'ordre des définitions dans le fichier est sans importance : est_pair ne cherche est_impair qu'au moment de l'appel.

Chaque appel de fonction possède son propre environnement : ses paramètres et ses variables locales, distincts de ceux des autres appels. Ces environnements sont rangés dans la pile d'appels : un appel qui en déclenche un autre reste ouvert, en attente, tant que l'appel déclenché n'a pas renvoyé sa valeur. La profondeur de récursion d'un calcul est le nombre maximal d'appels ouverts simultanément ; la mémoire occupée par la pile lui est proportionnelle. Ainsi factorielle(3) ouvre quatre appels avant que le premier return ne se produise.

def factorielle_trace(n, profondeur):
    """Renvoie n! en affichant la pile d'appels ; profondeur est le niveau courant."""
    print("|   " * profondeur + "appel factorielle(" + str(n) + ")")
    if n == 0:
        resultat = 1
    else:
        resultat = n * factorielle_trace(n - 1, profondeur + 1)
    print("|   " * profondeur + "retour " + str(resultat))
    return resultat


factorielle_trace(3, 0)

L'appel factorielle_trace(3, 0), qui termine ce programme, affiche :

appel factorielle(3)
|   appel factorielle(2)
|   |   appel factorielle(1)
|   |   |   appel factorielle(0)
|   |   |   retour 1
|   |   retour 1
|   retour 2
retour 6

La descente se lit de haut en bas, la remontée de bas en haut : les multiplications ne sont faites qu'au retour.

L'interpréteur Python limite la profondeur de la pile d'appels : au-delà d'un seuil, de l'ordre de $1000$ par défaut, il interrompt le calcul en levant l'erreur RecursionError: maximum recursion depth exceeded. Sur la machine de test, une descente de profondeur $998$ passe et une descente de profondeur $100\,000$ échoue. Deux conséquences pratiques : une récursion dont la profondeur croît linéairement avec la taille des données (parcourir une liste de $5000$ éléments par appels successifs) est inutilisable, alors qu'une récursion de profondeur logarithmique ne pose jamais de problème (un tri fusion sur un million d'éléments descend à la profondeur $21$). De plus, Python n'élimine pas la récursion terminale : écrire l'appel récursif en dernière instruction ne fait rien gagner sur la pile.

Propriété : soit f une fonction récursive et $A$ l'ensemble de ses arguments valides. On suppose qu'il existe une application $\varphi : A \to \mathbb{N}$, appelée variant, telle que :
(i) tout appel récursif déclenché par f(x) porte sur un argument $y$ encore dans $A$, donc $\varphi(y)$ est bien un entier naturel ;
(ii) pour tout $x \in A$, chaque appel récursif f(y) déclenché directement par f(x) vérifie $\varphi(y) < \varphi(x)$ ;
(iii) en dehors de ses appels récursifs, le corps de f ne contient que des instructions qui terminent.
Alors, pour tout $x \in A$, l'appel f(x) termine.
Démonstration : par récurrence forte sur $n = \varphi(x)$ (voir le thème Récurrence forte du bloc Fondamental). Si $\varphi(x) = 0$, aucun appel récursif n'est possible d'après (ii), car il faudrait un variant entier naturel strictement inférieur à $0$ ; l'appel se réduit alors à des instructions qui terminent. Si $\varphi(x) = n$ et si tout appel de variant strictement inférieur à $n$ termine, alors chaque appel récursif déclenché par f(x) termine par hypothèse de récurrence, donc f(x) aussi.
L'hypothèse (i) est celle que l'on oublie : c'est elle qui interdit une descente qui saute le cas de base.

Propriété : soit f une fonction récursive munie d'un variant $\varphi : A \to \mathbb{N}$ au sens précédent, et soit $S$ la spécification de f, c'est-à-dire l'application qui à chaque $x \in A$ associe la valeur attendue $S(x)$. On suppose :
(i) pour tout $x \in A$ traité par un cas de base, l'appel f(x) renvoie $S(x)$ ;
(ii) pour tout $x \in A$ traité par un cas récursif, si chaque appel récursif f(y) déclenché par f(x) renvoie $S(y)$, alors f(x) renvoie $S(x)$.
Alors, pour tout $x \in A$, l'appel f(x) termine et renvoie $S(x)$.
Démonstration : la terminaison est acquise. Pour la correction, on raisonne par récurrence forte sur $n = \varphi(x)$ : l'hypothèse (i) traite les cas de base, et dans un cas récursif tous les appels déclenchés portent sur des arguments de variant strictement inférieur, donc corrects par hypothèse de récurrence ; l'hypothèse (ii) transporte alors la correction à f(x).
La preuve d'une fonction récursive est donc exactement une récurrence forte : on a le droit de supposer que l'appel récursif fait ce qu'il promet, à condition de l'avoir écrit sur un argument plus petit.

Quand l'utiliser : l'énoncé définit un objet par récurrence, ou la donnée se décompose naturellement en une donnée de même nature mais plus petite (un entier et son prédécesseur, une liste et sa fin, un ensemble privé d'un élément, un intervalle et ses deux moitiés).
1) Écrire la spécification avant le code, en une phrase qui dit ce que renvoie la fonction en fonction de ses arguments, et une ligne de précondition : « Renvoie la somme des éléments de valeurs d'indice i à la fin. Précondition : $0 \leq i \leq$ len(valeurs). » Sans elle, il n'y a rien à prouver.
2) Choisir le variant : la quantité entière positive qui doit décroître. C'est souvent n, len(valeurs) ou len(valeurs) - i.
3) Traiter les cas de base : toutes les valeurs de l'argument pour lesquelles la réponse se donne sans appel. Vérifier qu'ils sont atteints par la descente (descendre de $2$ en $2$ depuis un entier impair ne rencontre jamais $0$).
4) Écrire le cas récursif : supposer que l'appel sur plus petit renvoie déjà la bonne valeur (c'est l'hypothèse de récurrence), puis écrire l'assemblage qui en déduit la valeur cherchée. Ne jamais oublier le return devant l'assemblage.
5) Vérifier sur les cas limites : argument nul, liste vide, liste à un élément.
6) Rédiger la preuve en deux temps : terminaison par le variant, correction par récurrence forte sur ce même variant.

Écrire une fonction récursive qui renvoie la somme des éléments d'une liste de nombres, puis démontrer qu'elle termine et qu'elle est correcte.
Spécification : somme(valeurs, i) renvoie la somme des éléments de valeurs d'indice i à len(valeurs) - 1, la somme vide valant $0$. Précondition : $0 \leq i \leq$ len(valeurs).

def somme(valeurs, i):
    """Renvoie la somme des éléments de valeurs d'indice i à len(valeurs) - 1.
    Précondition : 0 <= i <= len(valeurs)."""
    if i == len(valeurs):
        return 0
    return valeurs[i] + somme(valeurs, i + 1)

Terminaison. Posons $n =$ len(valeurs) et $\varphi(i) = n - i$. La précondition donne $0 \leq i \leq n$, donc $\varphi(i) \in \mathbb{N}$.
Si $i < n$, le seul appel récursif porte sur $i + 1$, qui vérifie encore $0 \leq i+1 \leq n$, et $\varphi(i+1) = n - i - 1 < \varphi(i)$.
Le variant est donc un entier naturel qui décroît strictement à chaque appel, donc la fonction termine.
Correction. Montrons par récurrence forte sur $k = n - i$ la propriété $P(k)$ : « pour tout indice $i$ tel que $n - i = k$, l'appel somme(valeurs, i) renvoie $\sum_{j=i}^{n-1}$ valeurs[j] ».
Initialisation. Si $k = 0$, alors $i = n$, le test i == len(valeurs) est vrai et l'appel renvoie $0$, qui est bien la somme vide.
Hérédité. Soit $k \geq 1$, supposons $P(0), \dots, P(k-1)$ vraies et soit $i$ tel que $n - i = k$. Alors $i < n$, donc l'appel exécute valeurs[i] + somme(valeurs, i + 1).
Or $n - (i+1) = k - 1$, donc l'hypothèse de récurrence $P(k-1)$ s'applique à l'appel récursif : il renvoie $\sum_{j=i+1}^{n-1}$ valeurs[j].
Donc l'appel somme(valeurs, i) renvoie valeurs[i] $+ \sum_{j=i+1}^{n-1}$ valeurs[j] $= \sum_{j=i}^{n-1}$ valeurs[j], ce qui établit $P(k)$.
Conclusion. Pour tout $i$ vérifiant la précondition, somme(valeurs, i) termine et renvoie la somme voulue ; en particulier somme(valeurs, 0) renvoie la somme de tous les éléments. L'exécution donne somme([3, 1, 4, 1, 5], 0) égal à 14 et somme([], 0) égal à 0.
À retenir : le variant sert deux fois, d'abord pour la terminaison, puis comme entier sur lequel porte la récurrence forte de la correction.

Ligne fautive : valeurs[i] + somme(valeurs, i + 1), écrite sans return devant.
L'expression est bien calculée, puis jetée : la fonction se termine sans instruction return, donc elle renvoie None. L'appel somme([3], 0) renvoie alors None, et somme([3, 1, 4], 0) s'interrompt sur TypeError: unsupported operand type(s) for +: 'int' and 'NoneType', parce que l'appel de niveau supérieur essaie d'ajouter un entier à ce None.
Ce message d'erreur est la signature de l'oubli : dès qu'un TypeError mêle un type usuel et NoneType dans une fonction récursive, c'est un return qui manque, ou un print mis à sa place.
Version correcte : return valeurs[i] + somme(valeurs, i + 1). Règle de relecture : dans une fonction récursive, toute branche doit se terminer par un return, cas de base compris.

Ligne fautive : print(n * factorielle(n - 1)) à la place de return n * factorielle(n - 1).
Le résultat s'affiche à l'écran, ce qui donne l'illusion que la fonction marche, mais elle renvoie None : l'appel suivant reçoit None et l'exécution s'arrête sur TypeError: unsupported operand type(s) for *: 'int' and 'NoneType' après avoir affiché 1. Même quand l'affichage semble complet, la valeur est inutilisable : on ne peut ni la stocker dans une variable, ni la comparer, ni la renvoyer.
print parle à l'utilisateur, return parle au programme, et un appel récursif est un programme, pas un utilisateur.
Version correcte : la fonction renvoie sa valeur, et c'est l'appelant qui décide de l'afficher : print(factorielle(5)). Si l'on veut voir la descente, on ajoute un print en plus du return, jamais à sa place.

Quand l'utiliser : dès que l'énoncé demande de justifier qu'une fonction récursive termine, et systématiquement au brouillon avant de croire à un code récursif.
1) Repérer l'argument (ou la combinaison d'arguments) qui change d'un appel au suivant.
2) Proposer une quantité $\varphi$ à valeurs entières positives ou nulles construite sur cet argument : n, len(valeurs), len(valeurs) - i, b - a, le nombre de cases encore libres.
3) Vérifier que la précondition garantit $\varphi \geq 0$ pour tout appel effectivement déclenché : c'est ici que se voient les descentes qui manquent le cas de base.
4) Écrire, pour chaque appel récursif du corps, l'inégalité stricte : « l'appel porte sur $i+1$, et $n - (i+1) < n - i$ », « l'appel porte sur une liste de longueur $\lfloor n/2 \rfloor < n$ pour $n \geq 2$ ».
5) Conclure par la phrase type : « Le variant est un entier naturel qui décroît strictement à chaque appel récursif ; une suite strictement décroissante d'entiers naturels étant finie, la fonction termine. »
6) Si aucun variant ne vient, c'est le plus souvent que le code est faux : vérifier que le cas de base est atteignable et que l'appel se fait bien sur une donnée plus petite.

Les deux fonctions suivantes terminent-elles pour tout entier naturel donné en argument ?

def factorielle(n):
    """Renvoie n!, pour n entier naturel.
    Précondition : n >= 0."""
    if n == 0:
        return 1
    return n * factorielle(n - 1)


def pair_faux(n):
    """Cherche à dire si n est pair, pour n entier naturel."""
    if n == 0:
        return True
    return pair_faux(n - 2)

Première fonction. Posons $\varphi(n) = n$, et soit $n \in \mathbb{N}$.
Si $n = 0$, l'appel renvoie $1$ sans appel récursif.
Si $n \geq 1$, le seul appel récursif porte sur $n - 1$, qui est encore un entier naturel, et $\varphi(n-1) = n - 1 < n = \varphi(n)$.
Le variant est donc un entier naturel qui décroît strictement à chaque appel récursif ; une suite strictement décroissante d'entiers naturels étant finie, factorielle(n) termine pour tout $n \in \mathbb{N}$.
Seconde fonction. La quantité $\varphi(n) = n$ décroît bien, de $2$ à chaque appel, mais elle ne reste pas positive : partant de $n = 7$, les appels portent sur $5$, $3$, $1$, puis $-1$, $-3$, et ainsi de suite.
Autrement dit, l'hypothèse (i) de la propriété de terminaison est en défaut : l'argument sort de l'ensemble $\mathbb{N}$ sur lequel le variant est défini, et le cas de base n == 0 n'est jamais atteint.
Donc pair_faux(6) termine et renvoie True, tandis que pair_faux(7) ne termine pas : l'exécution s'arrête sur RecursionError: maximum recursion depth exceeded.
On corrige en rendant le cas de base atteignable depuis tout entier naturel, par exemple en ajoutant if n == 1: return False.
À retenir : un variant qui décroît ne suffit pas, il doit rester un entier naturel, c'est-à-dire que la descente doit rencontrer un cas de base.

Ligne fautive : def factorielle(n): return n * factorielle(n - 1), écrite sans le cas n == 0.
L'appel factorielle(5) descend vers $4$, $3$, $2$, $1$, $0$, $-1$, $-2$, sans jamais s'arrêter, et l'exécution s'interrompt sur RecursionError: maximum recursion depth exceeded. La même erreur se produit avec un cas de base présent mais inatteignable : pair_faux(n) qui s'arrête à n == 0 et appelle pair_faux(n - 2) termine pour $6$ et ne termine pas pour $7$, car la descente $7, 5, 3, 1, -1, -3$ saute le zéro.
Version correcte : écrire le cas de base avant le cas récursif, et vérifier que la descente le rencontre depuis toute donnée valide : ici if n == 0: return 1 pour la factorielle, et l'ajout de if n == 1: return False pour la parité. La vérification s'écrit toujours de la même façon : le variant est un entier naturel qui décroît strictement et ne peut donc pas passer sous le cas de base sans l'atteindre.

Quand l'utiliser : une question de concours du type « que renvoie f(4) ? », « combien d'appels sont effectués ? », ou pour trouver l'erreur dans un code récursif que l'on croit juste.
1) Écrire l'arbre des appels : la racine est l'appel initial, les fils d'un appel sont les appels récursifs qu'il déclenche, dans l'ordre d'écriture du code.
2) Descendre jusqu'aux feuilles, qui sont les cas de base, et n'écrire à ce stade aucun résultat : à la descente, rien n'est encore calculé.
3) Remonter en écrivant la valeur renvoyée par chaque nœud, obtenue en appliquant l'assemblage aux valeurs de ses fils.
4) Pour compter les appels, compter les nœuds de l'arbre ; pour la profondeur de pile, mesurer la hauteur de l'arbre ; pour l'ordre d'affichage, lire les print dans l'ordre où ils sont rencontrés.
5) Se méfier des arbres où deux nœuds portent le même argument : ils sont recalculés, et c'est là que naissent les coûts exponentiels.

On définit fib par le code ci-dessous. Dessiner l'arbre des appels de fib(4), donner la valeur renvoyée et le nombre d'appels effectués.

def fib(n):
    """Renvoie le terme d'indice n de la suite de Fibonacci.
    Précondition : n >= 0. Convention : F(0) = 0, F(1) = 1."""
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

L'appel fib(4) déclenche fib(3) puis fib(2), et ainsi de suite jusqu'aux cas de base, ce qui donne l'arbre suivant, où chaque ligne est un niveau :

fib(4)
|-- fib(3)
|   |-- fib(2)
|   |   |-- fib(1) -> 1
|   |   |-- fib(0) -> 0
|   |-- fib(1) -> 1
|-- fib(2)
|   |-- fib(1) -> 1
|   |-- fib(0) -> 0

Remontée. fib(2) renvoie $1 + 0 = 1$, donc fib(3) renvoie $1 + 1 = 2$, et le second fib(2) renvoie de nouveau $1$.
Donc fib(4) renvoie $2 + 1 = 3$, ce qui est bien $F(4)$.
L'arbre compte $9$ nœuds, donc $9$ appels à fib sont effectués, dont trois appels de fib(1) et deux de fib(2) : le même calcul est refait plusieurs fois.
Ses nœuds se répartissent sur quatre niveaux, donc la pile contient au plus quatre appels de fib ouverts en même temps.
Vérification. On fait dessiner le même arbre par la machine, en affichant chaque appel à son entrée, décalé de sa profondeur.

def fib_trace(n, profondeur):
    """Renvoie F(n) en dessinant l'arbre des appels ; profondeur est le niveau courant."""
    prefixe = "|   " * (profondeur - 1) + "|-- " if profondeur > 0 else ""
    if n <= 1:
        print(prefixe + "fib(" + str(n) + ") -> " + str(n))
        return n
    print(prefixe + "fib(" + str(n) + ")")
    return fib_trace(n - 1, profondeur + 1) + fib_trace(n - 2, profondeur + 1)


fib_trace(4, 0)

L'affichage obtenu est exactement l'arbre ci-dessus, ligne pour ligne.
À retenir : les nœuds comptent le temps, la hauteur compte la mémoire, et les nœuds répétés annoncent une explosion du coût.

Un appel récursif est terminal lorsque rien ne reste à faire après lui : sa valeur est immédiatement renvoyée, sans être combinée à quoi que ce soit. Dans return valeurs[i] + somme(valeurs, i + 1), l'appel n'est pas terminal, car il reste une addition à effectuer à la remontée ; dans return somme_acc(valeurs, i + 1, accumulateur + valeurs[i]), il l'est, car le résultat de l'appel est renvoyé tel quel. On rend une récursion terminale en transportant dans un paramètre supplémentaire, l'accumulateur, le travail qui devait être fait à la remontée. Une récursion terminale se transforme mécaniquement en boucle, et c'est la seule raison pratique de s'y intéresser en Python, qui ne l'optimise pas de lui-même.

Quand l'utiliser : la profondeur de récursion croît avec la taille des données (risque de RecursionError), ou l'énoncé demande explicitement une version itérative, ou le même sous-calcul est refait plusieurs fois.
1) Regarder le nombre d'appels récursifs dans le corps.
2) Un seul appel, terminal : la traduction est mécanique. Les paramètres deviennent des variables, le cas de base devient la condition d'arrêt du while, et le corps devient la mise à jour des variables. Phrase à écrire : « Les paramètres de l'appel récursif deviennent les variables mises à jour à chaque tour de boucle. »
3) Un seul appel, non terminal : introduire un accumulateur qui porte le travail de la remontée, vérifier que la version à accumulateur renvoie la même chose, puis appliquer l'étape 2.
4) Plusieurs appels (arbre) : il n'y a pas de boucle simple. Deux issues : remplir de proche en proche une liste ou un dictionnaire des valeurs déjà calculées, du plus petit argument vers le plus grand (méthode ascendante), ou gérer soi-même une pile explicite avec une liste, append pour empiler et pop pour dépiler (voir le thème Python : listes, tuples, chaînes et dictionnaires).
5) Vérifier la version itérative sur les cas limites et la comparer à la version récursive sur quelques valeurs : elles doivent coïncider exactement.
6) Annoncer le gain, en séparant les deux. La pile ne grandit plus, donc la profondeur cesse d'être un obstacle : c'est acquis dans tous les cas. Le coût en temps, lui, reste inchangé quand la traduction est mécanique (étapes 2 et 3, un tour de boucle pour un appel), mais il peut chuter d'une classe entière quand on est passé par la table ascendante de l'étape 4, qui supprime au passage les recalculs : Fibonacci passe ainsi de $\Theta(\varphi^n)$ à $\Theta(n)$. Ce sont deux gains distincts, et il faut les annoncer séparément.

Transformer la fonction récursive somme en une fonction itérative, en passant par une version à accumulateur.
Étape 1 : rendre la récursion terminale. Le travail de la remontée est l'addition de valeurs[i] ; on le fait à la descente, dans un paramètre accumulateur.

def somme_acc(valeurs, i, accumulateur):
    """Renvoie accumulateur augmenté de la somme des éléments d'indice >= i.
    Précondition : 0 <= i <= len(valeurs)."""
    if i == len(valeurs):
        return accumulateur
    return somme_acc(valeurs, i + 1, accumulateur + valeurs[i])

L'appel somme_acc(valeurs, 0, 0) renvoie la somme de tous les éléments : sur [3, 1, 4, 1, 5], il renvoie 14.
Étape 2 : lire le passage d'un appel au suivant. L'appel sur $(i, a)$ déclenche l'appel sur $(i+1,\ a +$ valeurs[i] $)$, et le calcul s'arrête quand $i =$ len(valeurs), en renvoyant $a$.
Étape 3 : écrire la boucle. Les deux paramètres deviennent deux variables, la condition d'arrêt devient la condition de la boucle, et la mise à jour devient le corps.

def somme_boucle(valeurs):
    """Renvoie la somme des éléments de valeurs."""
    accumulateur = 0
    for i in range(len(valeurs)):
        accumulateur = accumulateur + valeurs[i]
    return accumulateur

Vérification sur les cas limites : somme_boucle([]) renvoie 0, somme_boucle([7]) renvoie 7, et somme_boucle([3, 1, 4, 1, 5]) renvoie 14 comme la version récursive.
Gain. Sur une liste de $5000$ éléments, somme_boucle renvoie 12497500 sans difficulté, tandis que somme_acc(grande, 0, 0) s'interrompt sur RecursionError: maximum recursion depth exceeded : la récursion, même terminale, empile $5000$ appels que Python refuse.
À retenir : on rend d'abord la récursion terminale avec un accumulateur, puis on traduit l'appel terminal en un tour de boucle, paramètre par paramètre.

Ligne fautive : « cet appel est terminal, donc il ne coûte rien en pile ».
Certains langages remplacent un appel terminal par un saut, ce qui garde la pile constante. Python ne le fait pas : chaque appel empile un environnement, terminal ou non. Contre-exemple : la fonction somme_acc, pourtant parfaitement terminale, échoue avec RecursionError: maximum recursion depth exceeded sur une liste de $5000$ éléments, là où la boucle équivalente calcule 12497500 sans difficulté.
Version correcte : en Python, rendre une récursion terminale n'est pas une optimisation, c'est une étape vers la boucle, qui, elle, ne consomme rien en pile. Un algorithme dont la profondeur de récursion croît proportionnellement à la taille des données doit être dérécursivé ; un algorithme de profondeur logarithmique, comme le tri fusion, n'a pas ce problème.

Le nombre total d'opérations élémentaires d'un calcul récursif est la somme, sur tous les nœuds de l'arbre des appels, du coût propre de chaque appel, c'est-à-dire de ce qu'il exécute en dehors de ses appels récursifs. Si ce coût propre ne dépend que de la taille $n$ de la donnée, en notant $C(n)$ le coût total d'un appel sur une donnée de taille $n$, on obtient une relation de récurrence : $C(n) = \sum_{i} C(n_i) + c(n)$, où les $n_i$ sont les tailles des données des appels directs et $c(n)$ le coût propre. Rappel hors ligne (bloc Analyse 2, thème Négligeabilité, domination et équivalents) : $C = O(g)$ signifie qu'il existe une constante $K > 0$ et un rang à partir duquel $C(n) \leq K\,g(n)$, et $C = \Theta(g)$ que l'on a à la fois $C = O(g)$ et $g = O(C)$ ; les classes usuelles et le décompte des opérations élémentaires sont traités dans le thème Complexité des algorithmes.

Propriété : soit $(F_n)$ la suite de Fibonacci définie par $F_0 = 0$, $F_1 = 1$ et $F_{n+2} = F_{n+1} + F_n$, et soit fib la fonction récursive qui la calcule en suivant littéralement cette définition. Le nombre $C(n)$ d'appels à fib effectués par le calcul de fib(n) vaut exactement $C(n) = 2F_{n+1} - 1$ pour tout $n \in \mathbb{N}$.
Comme $F_n = \dfrac{\varphi^n - \psi^n}{\sqrt{5}}$ avec $\varphi = \dfrac{1+\sqrt{5}}{2}$ et $\psi = \dfrac{1-\sqrt{5}}{2}$ (voir le thème Suites récurrentes linéaires du bloc Analyse 1), on a $C(n) = \Theta(\varphi^n)$ avec $\varphi \approx 1{,}618$ : le coût est exponentiel, alors que la suite elle-même se calcule en $n$ additions.
La cause se lit sur l'arbre des appels : $F_{n-2}$ y est calculé deux fois, $F_{n-3}$ trois fois, et ainsi de suite. Mesure effective : $C(10) = 177$, $C(20) = 21\,891$, $C(30) = 2\,692\,537$, à comparer aux $29$ additions de la version itérative.

Quand l'utiliser : l'énoncé demande le nombre d'appels, le nombre de comparaisons, le nombre de multiplications, ou la complexité d'une fonction récursive.
1) Nommer la quantité comptée et le paramètre dont elle dépend : « Soit $C(n)$ le nombre d'appels à fib effectués par le calcul de fib(n). » Sans ce nommage, la récurrence ne veut rien dire.
2) Écrire les valeurs initiales en lisant les cas de base : « Pour $n \leq 1$, l'appel ne déclenche aucun appel récursif, donc $C(n) = 1$ (l'appel lui-même). »
3) Écrire la relation en lisant le cas récursif, sans rien oublier du coût propre : « Pour $n \geq 2$, l'appel fib(n) s'exécute lui-même, puis déclenche fib(n-1) et fib(n-2), donc $C(n) = 1 + C(n-1) + C(n-2)$. »
4) Deviner la forme close sur les premières valeurs, calculées à la main ou par programme, puis la démontrer par récurrence, simple, double ou forte selon le nombre de valeurs utilisées (voir les thèmes Récurrence simple, Récurrence double et Récurrence forte du bloc Fondamental).
5) Si la forme close est hors de portée, se contenter d'un encadrement : majorer et minorer $C$ par des suites géométriques ou par une comparaison avec $n$, $n\log_2(n)$, $n^2$.
6) Conclure par la classe de complexité, avec la notation $\Theta$ si l'on a l'ordre exact, $O$ si l'on n'a qu'une majoration.

Soit fib la fonction récursive naïve calculant la suite de Fibonacci. Démontrer que le calcul de fib(n) effectue exactement $2F_{n+1} - 1$ appels à fib.
Soit $C(n)$ le nombre d'appels à fib effectués lors du calcul de fib(n), l'appel initial compris.
Pour $n \leq 1$, le test n <= 1 est vrai, l'appel renvoie n sans déclencher d'appel récursif, donc $C(0) = C(1) = 1$.
Pour $n \geq 2$, l'appel fib(n) compte pour lui-même, puis déclenche le calcul complet de fib(n-1) et celui de fib(n-2), donc $C(n) = 1 + C(n-1) + C(n-2)$.
Montrons par récurrence double la propriété $P(n)$ : « $C(n) = 2F_{n+1} - 1$ » (voir le thème Récurrence double du bloc Fondamental).
Initialisation. $2F_1 - 1 = 2 \times 1 - 1 = 1 = C(0)$ et $2F_2 - 1 = 2 \times 1 - 1 = 1 = C(1)$, donc $P(0)$ et $P(1)$ sont vraies.
Hérédité. Soit $n \geq 2$ tel que $P(n-2)$ et $P(n-1)$ soient vraies.
Alors $C(n) = 1 + C(n-1) + C(n-2) = 1 + (2F_n - 1) + (2F_{n-1} - 1)$.
Or $F_n + F_{n-1} = F_{n+1}$ par définition de la suite de Fibonacci, donc $C(n) = 2(F_n + F_{n-1}) - 1 = 2F_{n+1} - 1$, ce qui est $P(n)$.
Conclusion. Pour tout $n \in \mathbb{N}$, $C(n) = 2F_{n+1} - 1$. Comme $F_{n+1} \sim \dfrac{\varphi^{n+1}}{\sqrt{5}}$, le nombre d'appels est équivalent à $\dfrac{2\varphi}{\sqrt{5}}\varphi^{n}$ : il croît exponentiellement.
Vérification numérique : la formule donne $C(25) = 2F_{26} - 1 = 242\,785$, et l'exécution compte bien $242\,785$ appels.
À retenir : on nomme la quantité comptée, on lit la relation de récurrence dans le code cas par cas, puis on démontre la forme close par la récurrence qui a le bon nombre de valeurs initiales.

Ligne fautive : « fib(30) empile $2\,692\,537$ appels, c'est pour cela que c'est lent ».
Les deux quantités sont différentes : le nombre d'appels est le nombre de nœuds de l'arbre des appels et mesure le temps ; la profondeur est sa hauteur et mesure la mémoire de pile. Pour fib(30), il y a bien $2\,692\,537$ appels au total, mais jamais plus de $30$ ouverts en même temps : la pile ne déborde pas, c'est le temps qui explose. À l'inverse, somme_acc sur $5000$ éléments ne fait que $5001$ appels, ce qui est peu, mais tous sont ouverts en même temps, et c'est la pile qui déborde.
Version correcte : « fib(30) effectue $2\,692\,537$ appels, d'où un coût en temps exponentiel, pour une profondeur de pile seulement égale à $30$ ». On retient la règle : les nœuds comptent le temps, la hauteur compte la mémoire.

Quand l'utiliser : l'arbre des appels contient plusieurs nœuds portant le même argument, donc le même sous-calcul est refait. Signal dans l'énoncé : « proposer une version efficace », « éviter de recalculer », ou un coût exponentiel constaté alors que le nombre de valeurs distinctes est petit.
1) Repérer l'ensemble des arguments distincts qui peuvent apparaître dans l'arbre, et vérifier qu'il est petit (ici, les entiers de $0$ à $n$).
2) Ajouter un dictionnaire memo qui associe à un argument déjà traité la valeur renvoyée (voir le thème Python : listes, tuples, chaînes et dictionnaires).
3) Lui donner la valeur par défaut None, jamais {} : une valeur par défaut mutable est créée une seule fois et survit d'un appel à l'autre. Première ligne du corps : if memo is None: memo = {}.
4) Avant de calculer, consulter : if n in memo: return memo[n]. Après avoir calculé, enregistrer : memo[n] = valeur, puis renvoyer.
5) Transmettre memo à tous les appels récursifs : c'est le partage de la table qui fait le gain.
6) Recompter : chaque argument distinct n'est calculé qu'une fois, donc le coût devient le nombre d'arguments distincts multiplié par le coût propre d'un appel. Annoncer la nouvelle classe et le prix payé en mémoire.

Proposer deux versions efficaces du calcul de $F_n$ et évaluer leur coût.
Version mémoïsée. On conserve la structure récursive et on ajoute une table des valeurs déjà calculées.

def fib_memo(n, memo=None):
    """Renvoie F(n) en mémorisant les valeurs déjà calculées.
    Précondition : n >= 0."""
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Coût. Pour chaque entier $k$ compris entre $2$ et $n$, la ligne memo[k] = ... n'est exécutée qu'une fois, puisque tout appel ultérieur sur $k$ trouve la valeur dans la table et renvoie aussitôt.
Donc le nombre d'additions est au plus $n - 1$ et le nombre d'appels est en $O(n)$ : le coût en temps est linéaire, contre exponentiel pour la version naïve.
Le prix est une mémoire en $O(n)$ pour la table, à laquelle s'ajoute une pile d'appels de profondeur $n$ : sur cette machine, fib_memo(2000) dépasse la limite de récursion et s'interrompt sur RecursionError.
Version itérative. On calcule de proche en proche, du plus petit indice vers le plus grand, en ne gardant que les deux derniers termes.

def fib_boucle(n):
    """Renvoie F(n) par une boucle, en mémoire constante."""
    precedent = 0
    courant = 1
    if n == 0:
        return 0
    for _ in range(n - 1):
        precedent, courant = courant, precedent + courant
    return courant

Coût. La boucle fait exactement $n - 1$ tours pour $n \geq 1$, chacun à coût constant, donc le coût est en $\Theta(n)$ et la mémoire en $\Theta(1)$, sans aucune pile.
Vérification. Les trois fonctions coïncident sur les indices de $0$ à $30$, et fib_boucle(200) renvoie 280571172992510140037611932413038677189525, les entiers de Python n'étant pas bornés.
À retenir : mémoïser garde la forme récursive et supprime les recalculs, itérer supprime en plus la pile ; on annonce toujours le coût gagné et la mémoire payée.

Ligne fautive : def puissance_memo(x, n, memo={}):, avec une table indexée par n seul.
En Python, la valeur par défaut d'un paramètre est évaluée une seule fois, à la définition de la fonction : le même dictionnaire sert donc à tous les appels ultérieurs, y compris ceux qui portent sur un autre x. Contre-exemple chiffré : puissance_memo(2, 10) renvoie 1024, puis puissance_memo(3, 10) renvoie encore 1024, alors que $3^{10} = 59049$. Le second appel a lu une table remplie pour un autre nombre. Le même piège existe avec une liste : def ajouter(x, liste=[]) accumule d'un appel à l'autre.
Version correcte : def puissance_memo(x, n, memo=None): puis, en première ligne du corps, if memo is None: memo = {}, ce qui crée une table neuve à chaque appel extérieur. Deuxième correction, indépendante : la clé doit contenir tout ce dont le résultat dépend, ici le couple (x, n) si l'on tient à partager la table.

Un appel récursif est un appel d'une fonction à elle-même ; le cas de base est la branche qui n'en contient aucun. L'arbre des appels a pour racine l'appel initial et pour fils de chaque nœud les appels qu'il déclenche : ses nœuds comptent le temps, sa hauteur compte la mémoire. La pile d'appels contient les appels ouverts, en attente d'un retour ; la profondeur de récursion est leur nombre maximal. Un appel est terminal quand rien ne reste à faire après lui, et l'accumulateur est le paramètre qui transporte le travail de la remontée. Mémoïser signifie retenir les résultats déjà calculés pour ne pas les recalculer. Dérécursiver, c'est réécrire la fonction sans appel récursif, avec une boucle ou une pile explicite.

Relations de récurrence rencontrées en analysant une fonction récursive, avec le coût total qu'elles donnent. Ici $c > 0$ est une constante et $n$ la taille de la donnée ; les valeurs initiales sont supposées constantes. Les trois premières décrivent une descente cran par cran, les suivantes une découpe en parts égales. La quatrième et la cinquième diffèrent par un seul facteur dans le nombre d'appels, et pourtant l'une est logarithmique et l'autre linéaire : c'est le nombre d'appels, plus que la taille des parts, qui décide.

La stratégie diviser pour régner résout un problème sur une donnée de taille $n$ en trois temps : diviser la donnée en $a$ sous-données de taille de l'ordre de $n/b$ (avec $b > 1$), régner en résolvant chaque sous-problème par un appel récursif, puis combiner les résultats obtenus en la solution du problème initial. Les cas de base sont les tailles pour lesquelles la réponse est immédiate, typiquement $0$ ou $1$. Toute la difficulté est dans la phase de combinaison : c'est elle qui porte le coût propre, et c'est elle que l'on prouve séparément avant de faire la récurrence. Le tri fusion, le tri rapide et la recherche dichotomique (voir le thème Algorithmes élémentaires et preuve de programmes) suivent ce schéma.

Propriété : si un algorithme de type diviser pour régner, sur une donnée de taille $n$, effectue $a$ appels récursifs sur des données de taille $n/b$ et un travail de coût $f(n)$ pour découper puis combiner, alors son coût $T$ vérifie, pour $n$ assez grand, $T(n) = a\,T(n/b) + f(n)$, les petites valeurs de $T$ étant bornées par une constante. Le nombre $a$ d'appels et le facteur $b$ de réduction sont des constantes indépendantes de $n$ : c'est ce qui distingue ce schéma d'une récursion qui descendrait de $n$ à $n-1$. Sur l'arbre des appels, le niveau $i$ contient $a^i$ nœuds portant chacun une donnée de taille $n/b^i$, et le coût total est la somme des $f$ sur tous les nœuds ; la profondeur est $\log_b(n)$, ce qui explique l'apparition systématique d'un logarithme.

Quand l'utiliser : on a obtenu $T(n) = a\,T(n/b) + f(n)$ et l'énoncé demande la complexité, sans autoriser le théorème maître ou en demandant la constante exacte.
1) Se placer sur les puissances de $b$ : poser $n = b^k$, c'est-à-dire $k = \log_b(n)$, et écrire $u_k = T(b^k)$. Phrase à écrire : « Supposons d'abord $n$ de la forme $b^k$ avec $k \in \mathbb{N}$. »
2) Réécrire la relation en $u_k = a\,u_{k-1} + f(b^k)$, qui est une suite récurrente d'ordre $1$.
3) Normaliser en divisant par le facteur dominant : pour $a = b$ et $f(n) = n$, poser $v_k = \dfrac{u_k}{b^k}$, ce qui donne $v_k = v_{k-1} + 1$, donc une suite arithmétique.
4) Résoudre la suite obtenue, puis revenir à $T$ en remplaçant $k$ par $\log_b(n)$.
5) Vérifier sur une petite valeur calculée à la main, puis conclure en $\Theta$ : « Donc $T(n) = \Theta(n\log n)$ sur les puissances de $2$. »
6) Pour $n$ quelconque, invoquer la croissance de $T$ et encadrer $n$ par deux puissances consécutives de $b$, ce qui ne change pas la classe ; en concours, cette dernière étape est le plus souvent admise, mais il faut savoir qu'elle manque.

Soit $T$ définie par $T(1) = 1$ et, pour tout entier $n \geq 2$ pair, $T(n) = 2\,T(n/2) + n$. Donner une expression de $T(n)$ pour $n$ puissance de $2$, puis sa classe de complexité.
Supposons $n = 2^k$ avec $k \in \mathbb{N}$, et posons $u_k = T(2^k)$.
La relation s'écrit alors $u_k = 2u_{k-1} + 2^k$ pour tout $k \geq 1$, avec $u_0 = T(1) = 1$.
Divisons par $2^k$ et posons $v_k = \dfrac{u_k}{2^k}$ : on obtient $v_k = \dfrac{2u_{k-1}}{2^k} + 1 = \dfrac{u_{k-1}}{2^{k-1}} + 1 = v_{k-1} + 1$.
Donc $(v_k)$ est arithmétique de raison $1$ et de premier terme $v_0 = u_0 = 1$, d'où $v_k = k + 1$ pour tout $k \in \mathbb{N}$.
Or $u_k = 2^k v_k$, donc $u_k = 2^k(k+1)$.
En revenant à $n = 2^k$, c'est-à-dire $k = \log_2(n)$, on obtient $T(n) = n\log_2(n) + n$.
Vérification. Pour $n = 16$, la formule donne $16 \times 4 + 16 = 80$, et le calcul direct de la récurrence donne également $80$.
Conclusion. Sur les puissances de $2$, $T(n) = n\log_2(n) + n$, donc $T(n) = \Theta(n\log n)$ : le terme $n\log_2(n)$ domine le terme $n$.
À retenir : on pose $n = 2^k$, on divise par le facteur dominant $2^k$ pour tomber sur une suite arithmétique, et on ne conclut en $\Theta$ qu'après être revenu à la variable $n$.

Théorème maître (admis) : soient $a \geq 1$ et $b > 1$ deux constantes, $f : \mathbb{N} \to \mathbb{R}_+$ une fonction, et $T$ une fonction positive croissante vérifiant $T(n) = a\,T(n/b) + f(n)$ pour $n$ assez grand, avec $T$ bornée sur les petites valeurs. On pose $c = \log_b(a)$. Alors :
Cas 1 : s'il existe $\varepsilon > 0$ tel que $f(n) = O(n^{c - \varepsilon})$, alors $T(n) = \Theta(n^{c})$ ;
Cas 2 : si $f(n) = \Theta(n^{c})$, alors $T(n) = \Theta(n^{c}\log n)$ ;
Cas 3 : s'il existe $\varepsilon > 0$ tel que $f(n) = \Omega(n^{c + \varepsilon})$, et s'il existe une constante $k < 1$ telle que $a\,f(n/b) \leq k\,f(n)$ pour $n$ assez grand (condition de régularité), alors $T(n) = \Theta(f(n))$.
La lecture est toujours la même : on compare le coût de la combinaison $f(n)$ au coût $n^{c}$ des feuilles de l'arbre des appels. Si les feuilles l'emportent, on est dans le cas 1 ; s'il y a égalité, chaque niveau coûte autant et l'on paie un facteur $\log n$ ; si la racine l'emporte, c'est le cas 3, et la condition de régularité est la seule hypothèse que l'on oublie. Le théorème ne couvre pas toutes les récurrences, par exemple $T(n) = 2T(n/2) + n\log n$, qui n'entre dans aucun des trois cas.

Donner la classe de complexité des algorithmes dont le coût vérifie, respectivement, $T(n) = 2T(n/2) + \Theta(n)$, $T(n) = T(n/2) + \Theta(1)$, $T(n) = 3T(n/2) + \Theta(n)$ et $T(n) = 2T(n/2) + \Theta(n^2)$.
Première récurrence (tri fusion). Ici $a = 2$ et $b = 2$, donc $c = \log_2(2) = 1$.
Le coût de combinaison vérifie $f(n) = \Theta(n) = \Theta(n^{c})$, donc on est dans le cas 2 du théorème maître.
Donc $T(n) = \Theta(n^{1}\log n) = \Theta(n\log n)$.
Deuxième récurrence (recherche dichotomique, voir le thème Algorithmes élémentaires et preuve de programmes). Ici $a = 1$ et $b = 2$, donc $c = \log_2(1) = 0$.
Le coût de combinaison vérifie $f(n) = \Theta(1) = \Theta(n^{0}) = \Theta(n^{c})$, donc on est encore dans le cas 2.
Donc $T(n) = \Theta(n^{0}\log n) = \Theta(\log n)$.
Troisième récurrence (multiplication de deux entiers à la manière de Karatsuba). Ici $a = 3$ et $b = 2$, donc $c = \log_2(3) \approx 1{,}585$.
En prenant $\varepsilon = 0{,}5$, on a $f(n) = \Theta(n) = O(n^{c - \varepsilon})$ car $c - \varepsilon > 1$, donc on est dans le cas 1.
Donc $T(n) = \Theta\big(n^{\log_2 3}\big)$, ce qui est bien meilleur que $\Theta(n^2)$ et moins bon que $\Theta(n\log n)$.
Quatrième récurrence. Ici $a = 2$, $b = 2$ et $c = 1$, et $f(n) = \Theta(n^2) = \Omega(n^{c + 1})$ : le cas 3 est le seul possible.
Vérifions sa condition de régularité : $a\,f(n/b) = 2 \times \left(\dfrac{n}{2}\right)^2 = \dfrac{n^2}{2} = \dfrac{1}{2}f(n)$, donc l'inégalité $a\,f(n/b) \leq k\,f(n)$ est vérifiée avec $k = \dfrac{1}{2} < 1$.
Donc le cas 3 s'applique et $T(n) = \Theta(n^2)$ : ici tout le coût est dans la combinaison, au premier niveau.
À retenir : on calcule $c = \log_b(a)$, on compare $f(n)$ à $n^{c}$, et dans le cas 3 on écrit explicitement la vérification de la condition de régularité.

Quand l'utiliser : la donnée est une liste, un intervalle ou un ensemble que l'on peut couper en parts de taille comparable, et l'on sait recoller les solutions des parts. Signal dans l'énoncé : « en $O(n\log n)$ », « par dichotomie », « diviser pour régner ».
1) Écrire la spécification de la fonction, puis celle de la fonction de combinaison, séparément : ce sont deux fonctions, on les prouve et on les teste l'une après l'autre.
2) Traiter les cas de base : taille $0$ et taille $1$. Une liste vide ou à un élément est déjà triée, ce qui donne if len(valeurs) <= 1: return list(valeurs).
3) Découper en parts de taille $\lfloor n/2 \rfloor$ et $n - \lfloor n/2 \rfloor$ avec milieu = len(valeurs) // 2, et vérifier que chaque part est strictement plus petite que la donnée : c'est le variant, et il est en défaut dès qu'une part peut valoir la donnée entière, par exemple quand on oublie d'exclure le pivot du tri rapide.
4) Régner : un appel récursif par part, en supposant qu'il renvoie déjà la bonne valeur.
5) Combiner et renvoyer, sans oublier le return.
6) Prouver : terminaison par le variant len(valeurs), correction par récurrence forte sur len(valeurs) avec la correction de la combinaison comme lemme, coût par la relation $T(n) = a\,T(n/b) + f(n)$.
7) Compter la mémoire : chaque niveau de l'arbre recopie la donnée dans les tranches, donc le coût mémoire n'est pas nul, contrairement à un algorithme en place.

Le tri fusion trie une liste en la coupant en deux moitiés, en triant chacune par un appel récursif, puis en fusionnant les deux listes triées obtenues.

def fusion(gauche, droite):
    """Renvoie la liste triée obtenue en fusionnant deux listes triées."""
    resultat = []
    i = 0
    j = 0
    while i < len(gauche) and j < len(droite):
        if gauche[i] <= droite[j]:
            resultat.append(gauche[i])
            i = i + 1
        else:
            resultat.append(droite[j])
            j = j + 1
    return resultat + gauche[i:] + droite[j:]


def tri_fusion(valeurs):
    """Renvoie une nouvelle liste contenant les éléments de valeurs triés
    par ordre croissant ; la liste valeurs n'est pas modifiée."""
    if len(valeurs) <= 1:
        return list(valeurs)
    milieu = len(valeurs) // 2
    return fusion(tri_fusion(valeurs[:milieu]), tri_fusion(valeurs[milieu:]))

fusion([1, 4, 7], [2, 3, 8]) renvoie [1, 2, 3, 4, 7, 8], et tri_fusion([5, 3, 8, 1, 9, 2, 7]) renvoie [1, 2, 3, 5, 7, 8, 9] en laissant la liste de départ inchangée. Le tri fusion est stable : à valeurs égales, le test gauche[i] <= droite[j] prend d'abord dans la moitié gauche, donc l'ordre initial des égaux est conservé. Il n'est pas en place : il construit de nouvelles listes et occupe une mémoire supplémentaire en $\Theta(n)$.

Démontrer que tri_fusion termine et renvoie la liste triée des éléments de valeurs.
Lemme (correction de la fusion). Soient gauche et droite deux listes triées par ordre croissant. Montrons que fusion(gauche, droite) renvoie la liste triée de leurs éléments réunis.
Considérons l'invariant suivant de la boucle while : « resultat est trié et contient exactement les i premiers éléments de gauche et les j premiers de droite, et tout élément de resultat est inférieur ou égal à gauche[i] et à droite[j] lorsque ces éléments existent » (voir le thème Raisonnement par invariant du bloc Fondamental).
Il est vrai avant le premier tour, où resultat est vide.
S'il est vrai en début de tour, l'élément ajouté est le plus petit des deux candidats gauche[i] et droite[j], donc il est supérieur ou égal à tous les éléments déjà placés et inférieur ou égal à tous ceux qui restent, puisque les deux listes sont triées ; l'invariant est donc encore vrai après le tour.
À la sortie, l'une des deux listes est épuisée, et la concaténation resultat + gauche[i:] + droite[j:] ajoute la fin de l'autre, déjà triée et supérieure ou égale à tout ce qui précède.
Donc fusion renvoie bien la liste triée des éléments réunis, et la boucle termine car i + j augmente de $1$ à chaque tour sans dépasser la somme des deux longueurs.
Terminaison de tri_fusion. Le variant est $n =$ len(valeurs), entier naturel. Si $n \geq 2$, les deux appels récursifs portent sur des listes de longueurs $\lfloor n/2 \rfloor$ et $n - \lfloor n/2 \rfloor$, toutes deux comprises entre $1$ et $n-1$, donc strictement plus petites que $n$.
Le variant décroît donc strictement à chaque appel, et le tri fusion termine.
Correction. Montrons par récurrence forte sur $n$ la propriété $P(n)$ : « pour toute liste valeurs de longueur $n$, tri_fusion(valeurs) renvoie la liste triée de ses éléments ».
Initialisation. Pour $n \leq 1$, l'appel renvoie une copie de valeurs, qui est triée puisqu'elle a au plus un élément.
Hérédité. Soit $n \geq 2$, supposons $P(m)$ vraie pour tout $m < n$ et soit valeurs de longueur $n$.
Les deux moitiés ont des longueurs strictement inférieures à $n$, donc par hypothèse de récurrence les deux appels récursifs renvoient les listes triées de leurs éléments respectifs.
Or le lemme s'applique à ces deux listes triées, donc fusion renvoie la liste triée de la réunion de leurs éléments, c'est-à-dire de tous les éléments de valeurs, chacun avec sa multiplicité.
Donc $P(n)$ est vraie, et par récurrence forte, tri_fusion est correcte pour toute liste.
À retenir : un algorithme diviser pour régner se prouve en deux morceaux, un lemme d'invariant pour la combinaison, puis une récurrence forte sur la taille pour la fonction elle-même.

Propriété : le tri fusion d'une liste de $n$ éléments effectue, dans le pire des cas, $C(n) = n\log_2(n) - n + 1$ comparaisons entre éléments lorsque $n$ est une puissance de $2$, et son coût total en temps est $\Theta(n\log n)$ dans tous les cas, meilleur comme pire. Sa mémoire supplémentaire est en $\Theta(n)$ et sa profondeur de récursion en $\Theta(\log n)$, ce qui la laisse très loin de la limite de récursion de Python.
Deux remarques pour ne pas se tromper de compte. D'abord, la fusion de deux listes non vides de longueurs $p$ et $q$ effectue au plus $p + q - 1$ comparaisons, et elle n'en effectue aucune si l'une des deux est vide. Ensuite, le découpage valeurs[:milieu] recopie les éléments, donc coûte lui aussi $\Theta(n)$ à chaque niveau, ce qui ne change pas la classe. Le tri fusion est optimal en ordre de grandeur parmi les tris par comparaison, puisque tout tri par comparaison exige au moins de l'ordre de $n\log_2(n)$ comparaisons (borne inférieure établie dans le thème Algorithmes élémentaires et preuve de programmes).

Soit $C(n)$ le nombre maximal de comparaisons entre éléments effectuées par tri_fusion sur une liste de $n$ éléments. Démontrer que $C(2^k) = k\,2^k - 2^k + 1$ pour tout $k \in \mathbb{N}$, et en déduire la complexité du tri fusion.
Établissons d'abord la relation de récurrence. Pour $n = 1$, aucun appel récursif n'a lieu et aucune comparaison entre éléments n'est faite, donc $C(1) = 0$.
Pour $n \geq 2$, l'appel trie deux moitiés, ce qui coûte au plus $C(\lfloor n/2 \rfloor) + C(\lceil n/2 \rceil)$ comparaisons, puis fusionne.
Or chaque comparaison de la fusion place définitivement un élément dans resultat, et le dernier élément placé, lui, l'est sans comparaison puisque la boucle s'arrête dès qu'une des deux listes est épuisée : la fusion coûte donc au plus $n - 1$ comparaisons.
Donc $C(n) \leq C(\lfloor n/2 \rfloor) + C(\lceil n/2 \rceil) + n - 1$, avec égalité dans le pire des cas.
Plaçons-nous sur $n = 2^k$ et posons $u_k = C(2^k)$ : la relation devient $u_k = 2u_{k-1} + 2^k - 1$ pour $k \geq 1$, avec $u_0 = 0$.
Montrons par récurrence sur $k$ la propriété $P(k)$ : « $u_k = k\,2^k - 2^k + 1$ ».
Initialisation. Pour $k = 0$ : $0 \times 1 - 1 + 1 = 0 = u_0$, donc $P(0)$ est vraie.
Hérédité. Soit $k \geq 0$ tel que $P(k)$ soit vraie.
Alors $u_{k+1} = 2u_k + 2^{k+1} - 1 = 2\big(k\,2^k - 2^k + 1\big) + 2^{k+1} - 1$.
Donc $u_{k+1} = k\,2^{k+1} - 2^{k+1} + 2 + 2^{k+1} - 1 = k\,2^{k+1} + 1$.
Or $(k+1)2^{k+1} - 2^{k+1} + 1 = k\,2^{k+1} + 1$, donc $u_{k+1} = (k+1)2^{k+1} - 2^{k+1} + 1$, ce qui est $P(k+1)$.
Conclusion sur les puissances de $2$ : $C(n) = n\log_2(n) - n + 1$.
Comme $C$ est croissante et que tout entier $n$ est encadré par deux puissances consécutives de $2$, on en déduit $C(n) = \Theta(n\log n)$ pour tout $n$.
Vérification numérique. Pour $n = 1024$, la formule donne $1024 \times 10 - 1024 + 1 = 9217$ comparaisons au plus, et le tri d'une liste tirée au hasard en a effectué $8931$, ce qui est bien inférieur.
À retenir : on majore d'abord le coût de la combinaison par $n-1$ en disant pourquoi, puis on résout la récurrence sur les puissances de $2$ avant de conclure en $\Theta$.

Ligne fautive : tri_fusion(a_trier) écrit seul, puis l'utilisation de a_trier comme si elle était triée.
La fonction renvoie une nouvelle liste et ne modifie pas son argument : après tri_fusion(a_trier) avec a_trier valant [5, 3, 8, 1], la liste a_trier vaut toujours [5, 3, 8, 1]. C'est l'inverse de la méthode a_trier.sort(), qui trie sur place et renvoie None.
Version correcte : a_trier = tri_fusion(a_trier), qui donne bien [1, 3, 5, 8].
Le fond du piège est le coût en mémoire : le tri fusion recopie les tranches valeurs[:milieu] et valeurs[milieu:] à chaque appel, donc il n'est pas gratuit en espace, et sa mémoire supplémentaire est en $\Theta(n)$. Croire qu'une tranche ne coûte rien fausse aussi les calculs de complexité : valeurs[:milieu] est une copie, en temps proportionnel à sa longueur.

Le tri rapide choisit un pivot dans la liste, répartit les autres éléments en ceux qui lui sont strictement inférieurs et les autres, trie chaque part par un appel récursif, puis concatène. Contrairement au tri fusion, tout le travail est dans la division et la combinaison est une simple concaténation.

def partition(valeurs):
    """Renvoie (petits, pivot, grands) où pivot est valeurs[0], petits la liste
    des éléments suivants strictement inférieurs au pivot et grands celle des autres.
    Précondition : la liste valeurs est non vide."""
    pivot = valeurs[0]
    petits = []
    grands = []
    for element in valeurs[1:]:
        if element < pivot:
            petits.append(element)
        else:
            grands.append(element)
    return petits, pivot, grands


def tri_rapide(valeurs):
    """Renvoie une nouvelle liste contenant les éléments de valeurs triés
    par ordre croissant ; la liste valeurs n'est pas modifiée."""
    if len(valeurs) <= 1:
        return list(valeurs)
    petits, pivot, grands = partition(valeurs)
    return tri_rapide(petits) + [pivot] + tri_rapide(grands)

Propriété : tri_rapide termine et renvoie la liste triée des éléments donnés. Le variant est len(valeurs) : le pivot étant retiré, les deux parts ont chacune au plus $n-1$ éléments. La partition effectue exactement $n-1$ comparaisons, d'où $C(n) = n - 1 + C(p) + C(n-1-p)$ où $p$ est le nombre d'éléments strictement inférieurs au pivot. Le pire des cas est celui où le pivot est à chaque fois le minimum ou le maximum : $C(n) = \dfrac{n(n-1)}{2}$, donc $\Theta(n^2)$, avec de surcroît une profondeur de récursion $n$. En moyenne, sur les $n!$ permutations équiprobables d'éléments deux à deux distincts, le nombre de comparaisons vaut $2(n+1)H_n - 4n \sim 2n\ln(n)$, soit $\Theta(n\log n)$ (résultat admis), où $H_n = \sum_{i=1}^{n} \frac{1}{i}$.

Démontrer que tri_rapide effectue $\dfrac{n(n-1)}{2}$ comparaisons sur une liste de $n$ éléments deux à deux distincts déjà rangée par ordre croissant, et conclure.
Soit valeurs une liste de $n$ éléments deux à deux distincts, rangés par ordre croissant.
Le pivot choisi est valeurs[0], donc le minimum de la liste, puisque la liste est croissante.
Donc aucun des $n-1$ autres éléments ne lui est strictement inférieur : la partition renvoie petits vide et grands égal à la liste des $n-1$ éléments suivants, encore rangée par ordre croissant.
La partition a effectué exactement $n - 1$ comparaisons, une par élément parcouru.
En notant $C(n)$ le nombre de comparaisons effectuées sur une telle liste, on obtient donc $C(n) = n - 1 + C(0) + C(n-1)$, c'est-à-dire $C(n) = C(n-1) + n - 1$ pour $n \geq 2$, avec $C(0) = C(1) = 0$.
Montrons par récurrence sur $n$ la propriété $P(n)$ : « $C(n) = \dfrac{n(n-1)}{2}$ ».
Initialisation. $C(1) = 0 = \dfrac{1 \times 0}{2}$, donc $P(1)$ est vraie.
Hérédité. Soit $n \geq 1$ tel que $P(n)$ soit vraie. Alors $C(n+1) = C(n) + n = \dfrac{n(n-1)}{2} + n = \dfrac{n(n-1) + 2n}{2} = \dfrac{n(n+1)}{2}$, ce qui est $P(n+1)$.
Conclusion. Pour tout $n \geq 1$, $C(n) = \dfrac{n(n-1)}{2}$, donc le tri rapide est en $\Theta(n^2)$ sur une liste déjà triée : le cas le plus favorable en apparence est le pire en réalité.
Vérification. Pour $n = 200$, la formule donne $19\,900$ comparaisons, et le comptage effectif sur list(range(200)) en donne exactement $19\,900$, contre une moyenne mesurée de $1570$ comparaisons sur des listes tirées au hasard.
De plus, la profondeur de récursion vaut alors $n$ : sur une liste croissante de $3000$ éléments, l'appel s'interrompt sur RecursionError: maximum recursion depth exceeded.
À retenir : le pire des cas du tri rapide s'obtient en exhibant une entrée explicite pour laquelle une part est toujours vide, et l'on conclut par la récurrence $C(n) = C(n-1) + n - 1$.