Récursivité et diviser pour régner · Information, calcul et communication

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

écrire une définition récursive correcte, reconnaître son cas de base et son cas récursif, et justifier sa terminaison et sa correction par récurrence;
décrire ce qu'est la pile d'appels, ce que contient un cadre, pourquoi la profondeur de récursion est bornée et ce qu'est un débordement de pile;
compter les appels d'une récursion naïve, expliquer pourquoi Fibonacci récursif est catastrophique, et le corriger par mémoïsation ou par itération;
appliquer le schéma diviser pour régner à la recherche dichotomique et au tri fusion, et établir leur invariant, leur correction et leur coût;
poser et résoudre une relation de récurrence $T (n) = a T (n / b) + f (n)$ par l'arbre de récursion, puis par le théorème maître, en sachant quelles hypothèses celui-ci exige;
démontrer qu'aucun tri par comparaisons ne peut descendre sous $Θ (n lo g_{2} n)$ , et situer le tri fusion par rapport à cette borne.

Définitions récursives

Un objet défini à partir de lui-même

Le chapitre 2 a décrit un algorithme comme une suite finie d'instructions non ambiguës, et a mesuré son coût en comptant les opérations élémentaires qu'il exécute. Tous les algorithmes rencontrés jusqu'ici — la recherche séquentielle, le tri par insertion, le tri par sélection — étaient itératifs: une boucle, un invariant, un compteur qui avance. Ce chapitre introduit la seconde manière de construire un algorithme, celle qui donne son nom à la moitié de l'informatique: la récursivité.

L'idée paraît d'abord circulaire. Pour définir une chose, on s'autorise à l'employer. Pour calculer une valeur, on s'autorise à appeler le calcul qu'on est en train de définir. Ce qui empêche la circularité de dégénérer en cercle vicieux est une discipline très simple, et c'est tout le contenu de la notion.

Retenez la forme: un cas de base, un cas récursif, et une taille qui décroît strictement. Une définition récursive à laquelle il manque l'un des trois est fausse, et elle est fausse de trois manières différentes. Sans cas de base, la descente est infinie. Sans cas récursif, la fonction n'est définie qu'en un point. Sans décroissance stricte — par exemple $f (n) = f (n)$ , ou $f (n) = f (n + 1) - 1$ — la définition ne détermine rien du tout, et le programme correspondant ne s'arrête jamais.

La factorielle

L'exemple canonique est la factorielle. La définition habituelle, $n! = 1 \times 2 \times \dots \times n$ , cache une récurrence: le produit des $n$ premiers entiers est le produit des $n - 1$ premiers, multiplié par $n$ . On écrit donc

n! = {1 n \cdot (n - 1)! si n = 0, si n \geq 1. (3.1)

Le cas de base est $n = 0$ (avec la convention $0! = 1$ , qui n'est pas un caprice: c'est le produit vide, et c'est le nombre de façons d'ordonner zéro objet, à savoir une). Le cas récursif fait décroître $n$ de $1$ : partant de $n$ , on atteint le cas de base après exactement $n$ appels. La traduction en pseudocode est littérale.

fonction factorielle(n)
    si n = 0 alors
        retourner 1                  # cas de base
    sinon
        retourner n * factorielle(n - 1)   # cas récursif

et en Python, ligne pour ligne:

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

La suite de Fibonacci

Le second exemple classique a deux cas de base et deux appels récursifs. La suite de Fibonacci est définie par

F_{0} = 0, F_{1} = 1, F_{n} = F_{n - 1} + F_{n - 2} (n \geq 2) . (3.2)

Ses premiers termes sont $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \dots$ Deux cas de base sont ici nécessaires, et non un seul: le cas récursif descend de deux crans, et sans $F_{1}$ la chaîne partant de $F_{3}$ passerait à côté de sans jamais s'arrêter proprement. C'est une vérification à faire systématiquement:

Récursivité et récurrence: le même objet

Le lien entre un algorithme récursif et une démonstration par récurrence n'est pas une analogie: c'est une identité de structure. Une démonstration par récurrence d'une propriété $P (n)$ comporte une initialisation — $P (0)$ est vraie — et une hérédité — si $P (n - 1)$ est vraie alors $P (n)$ l'est. Un algorithme récursif comporte un cas de base et un cas récursif. La correspondance est terme à terme, et elle fournit la méthode de preuve: pour prouver qu'un algorithme récursif est correct, on prouve son cas de base, puis on suppose l'appel récursif correct et on vérifie que le cas récursif en tire le bon résultat. Cette hypothèse est exactement l'hypothèse de récurrence.

Démonstration. Par récurrence sur $n$ .

Terminaison. Le paramètre de l'appel décroît strictement d'une unité à chaque appel récursif et reste entier; la suite des paramètres $n, n - 1, \dots$ atteint donc $0$ après exactement $n$ appels, où le cas de base rend la main sans appeler quoi que ce soit. La chaîne d'appels est de longueur $n + 1$ , donc finie.

Initialisation. Pour $n = 0$ , le test est vrai et la fonction retourne $1 = 0!$ .

Hérédité. Soit $n \geq 1$ et supposons que factorielle(n - 1) retourne $(n - 1)!$ . L'appel factorielle(n) prend la branche récursive et retourne $n \cdot factorielle (n - 1) = n \cdot (n - 1)! = n!$ par (3.1).

Par récurrence, la propriété vaut pour tout $n \geq 0$ . $□$

Remarquez le confort de cette preuve: elle ne suit pas l'exécution. Elle ne descend pas la chaîne d'appels, elle ne tient pas de compte des multiplications en attente. Elle se contente de supposer que l'appel interne fait son travail. C'est le bénéfice principal de la récursivité — et, nous allons le voir, aussi son piège, car une preuve de correction ne dit rien du coût.

Question 3.1

Laquelle de ces définitions récursives est bien fondée, c'est-à-dire termine pour tout entier $n \geq 0$ ?

La pile d'appels

Ce qu'un appel coûte

Un appel de fonction n'est pas gratuit. Lorsqu'une fonction en appelle une autre, la machine doit se souvenir de l'endroit où elle en était: quelle instruction reprendre au retour, quelles valeurs les variables locales avaient. Cette information est rangée dans une zone de mémoire appelée la pile d'appels (call stack).

Ce fonctionnement «dernier entré, premier sorti» est celui d'une pile au sens des structures de données, que le chapitre 4 étudiera pour elle-même. Il suffit ici de retenir ce qu'il implique: les appels en attente occupent de la mémoire, et cette mémoire n'est libérée qu'au retour.

Suivons factorielle(4). L'appel initial empile un cadre où $n = 4$ ; il ne peut pas rendre son résultat avant de connaître factorielle(3), dont le cadre s'empile par-dessus, et ainsi de suite. Quand $n = 0$ est atteint, cinq cadres sont présents simultanément. Le cas de base retourne $1$ , son cadre est dépilé, le cadre $n = 1$ calcule $1 \times 1 = 1$ et se dépile, puis $2 \times 1 = 2$ , , . Les multiplications s'effectuent donc , dans l'ordre inverse des appels. C'est exactement ce que la preuve du théorème 3.1 nous a dispensés de suivre.

La profondeur est bornée

La pile n'est pas extensible. Le système d'exploitation lui alloue une zone de taille fixée à la création du fil d'exécution, de l'ordre de quelques centaines de kibioctets à quelques mébioctets selon la plateforme; l'ordre de grandeur usuel pour le fil principal d'un programme est de 1 Mio à 8 Mio. Si un cadre occupe une centaine d'octets, cela autorise quelques dizaines de milliers à quelques centaines de milliers d'appels imbriqués — pas davantage.

Python place ce garde-fou très bas, précisément pour transformer un plantage en exception propre. Avec la limite par défaut de 1000, la profondeur maximale mesurée sur la machine utilisée pour ce chapitre est de 998 appels imbriqués; en la portant à 3000 avec sys.setrecursionlimit(3000), elle passe à 2998. La somme récursive d'une liste illustre la conséquence:

def somme(a, i=0):
    if i == len(a):        # cas de base: plus rien à additionner
        return 0
    return a[i] + somme(a, i + 1)

Cette fonction renvoie bien $404550$ pour la liste des entiers de $0$ à $899$ , et lève RecursionError: maximum recursion depth exceeded while calling a Python object sur une liste de 5000 éléments. Or additionner 5000 nombres n'est pas une prouesse: une boucle for le fait sans le moindre effort, et sans consommer un octet de pile supplémentaire. Voilà le premier avertissement du chapitre: une récursion dont la profondeur croît linéairement avec la taille de l'entrée est une bombe à retardement, alors qu'une récursion de profondeur logarithmique — celle du tri fusion, celle de la dichotomie — ne posera jamais de problème, car $lo g_{2} (1 0^{6}) \approx 20$ .

Question 3.2

Un tri fusion traite un tableau de $n = 1000000$ éléments. Chaque niveau de récursion coupe le tableau en deux. Combien de cadres d'appel au maximum sont simultanément empilés, si l'on compte le cadre de l'appel initial? (Réponse: $⌈ lo g_{2} n ⌉ + 1$ .)

Fibonacci récursif naïf: l'anatomie d'une catastrophe

Le programme

La traduction littérale de (3.2) tient en trois lignes et elle est correcte — la preuve est celle du théorème 3.1, avec deux cas de base et une récurrence forte.

def fib(n):
    if n <= 1:                    # cas de base: F(0) = 0, F(1) = 1
        return n
    return fib(n - 1) + fib(n - 2)

Elle est aussi inutilisable. Sur la machine utilisée pour ce chapitre, fib(35) demande 1,976 seconde, alors que la même valeur $F_{35} = 9227465$ s'obtient par une boucle en 1,14 microseconde, soit un rapport de l'ordre de $1, 7 \cdot 1 0^{6}$ . Comprendre pourquoi est l'exercice le plus instructif du chapitre.

L'arbre des appels

Chaque appel fib(n) avec $n \geq 2$ en engendre deux, fib(n-1) et fib(n-2), qui en engendrent à leur tour. La structure de l'exécution est donc un arbre d'appels: la racine est l'appel initial, les enfants d'un nœud sont les appels qu'il déclenche, et les feuilles sont les appels qui retournent sans rien appeler, c'est-à-dire les cas de base.

La figure 3.1 rend la catastrophe visible. La branche de gauche descend jusqu'à $f (1)$ en passant par $f (4), f (3), f (2)$ ; mais $f (3)$ apparaît une seconde fois comme fils droit de la racine, et son sous-arbre entier — cinq appels — est recalculé à l'identique. Rien dans le programme ne conserve la moindre valeur d'un appel à l'autre: chaque $f (3)$ rencontré repart de la racine de son propre sous-arbre.

Combien d'appels, exactement

Le décompte n'a pas besoin d'être approché: il est exact et il se démontre par récurrence.

Démonstration. Par récurrence forte sur $n$ .

Initialisation. Pour $n = 0$ et $n = 1$ , l'appel prend le cas de base et n'en déclenche aucun autre: $C (0) = C (1) = 1$ . Or $2 F_{1} - 1 = 2 \cdot 1 - 1 = 1$ et : la formule est vérifiée.

Hérédité. Soit $n \geq 2$ et supposons (3.3) vraie pour tous les indices strictement inférieurs à $n$ . L'appel fib(n) compte pour un appel, puis déclenche fib(n-1) et fib(n-2); les deux sous-arbres sont disjoints, donc

C (n) = 1 + C (n - 1) + C (n - 2) = 1 + (2 F_{n} - 1) + (2 F_{n - 1} - 1) = 2 (F_{n} + F_{n - 1}) - 1 = 2 F_{n + 1} - 1,

en utilisant (3.2). Pour les feuilles: une feuille est un appel avec $n \leq 1$ , un nœud interne en a exactement deux; dans un arbre binaire où tout nœud interne a deux enfants, le nombre de feuilles dépasse d'une unité le nombre de nœuds internes, donc feuilles $= (C (n) + 1) /2 = F_{n + 1}$ et nœuds internes $= F_{n + 1} - 1$ .

Ces valeurs ont été vérifiées en instrumentant la fonction avec un compteur et en comparant, pour $n$ de $0$ à $12$ , le compteur à $2 F_{n + 1} - 1$ : les deux coïncident à chaque ligne. Le tableau ci-dessous donne les valeurs mesurées.

$n$	5	10	20	30	35	40
$F_{n}$	5	55	6 765	832 040	9 227 465	102 334 155
Appels $C (n) = 2 F_{n + 1} - 1$	15	177	21 891	2 692 537	29 860 703

La croissance de $F_{n}$ est exponentielle: on montre (et le chapitre 2 a donné l'outil, la comparaison asymptotique) que $F_{n} \sim φ^{n} / 5$ avec , le nombre d'or. Par conséquent

C (n) = 2 F_{n + 1} - 1 = Θ (φ^{n}), (3.4)

c'est-à-dire une complexité exponentielle. Chaque unité ajoutée à $n$ multiplie le travail par $1, 618$ ; dix unités le multiplient par $φ^{10} \approx 123$ . Le tableau le confirme: de $n = 30$ à $n = 40$ , le nombre d'appels passe de 2,7 millions à 331 millions, soit un facteur 123.

Mémoïsation: se souvenir

Le défaut est identifié — le même sous-problème est résolu de multiples fois — donc le remède aussi: se souvenir. On conserve dans un dictionnaire les valeurs déjà calculées et on les consulte avant de recalculer. C'est la mémoïsation (memoization, sans «r»: le mot vient du latin memorandum).

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:            # déjà calculé: on le relit
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Le changement est minime et l'effet massif. Chaque valeur $F_{k}$ pour $k$ de $0$ à $n$ n'est calculée qu'une fois; les appels supplémentaires se soldent par une lecture du dictionnaire. Le nombre d'appels devient linéaire en $n$ et le coût aussi, au prix d'une mémoire $Θ (n)$ pour le dictionnaire — un compromis temps-mémoire tout à fait typique.

Itération: ne rien empiler du tout

Mieux encore: la récurrence (3.2) ne fait intervenir que les deux valeurs précédentes. Il est donc inutile de mémoriser toute la suite. Deux variables suffisent.

def fib_iter(n):
    a, b = 0, 1              # invariant: a = F(k), b = F(k+1)
    for _ in range(n):       # après k tours, a = F(k)
        a, b = b, a + b
    return a

L'invariant de boucle est écrit dans le commentaire, dans l'esprit du chapitre 2: avant le tour numéro $k$ , on a $a = F_{k}$ et $b = F_{k + 1}$ . Il est vrai au départ ( $a = F_{0} = 0$ , ) et se conserve, puisque le nouveau couple est . Après tours, . Le coût est opérations et mémoire, et la pile ne grandit jamais.

Les trois coûts, mesurés

Les durées ci-dessous ont été mesurées avec time.perf_counter sous CPython 3.9.6, une exécution unique pour la version naïve et une moyenne sur mille exécutions pour les deux autres. Ce sont des mesures, pas des estimations; elles varient de quelques dizaines de pour cent d'une exécution à l'autre, et les ordres de grandeur seuls sont significatifs.

$n$	Appels (naïf)	Naïf	Mémoïsé	Itératif
10	177	0,014 ms	2,07 µs	0,41 µs
20	21 891	1,41 ms	4,44 µs	0,69 µs
30	2 692 537	175 ms	6,93 µs	0,98 µs
35	29 860 703	1 976 ms	8,14 µs	1,14 µs

Lisez ce tableau colonne par colonne. La colonne «naïf» est multipliée par 11 entre $n = 30$ et $n = 35$ , ce qui est bien $φ^{5} \approx 11, 1$ . Les colonnes «mémoïsé» et «itératif» croissent lentement et linéairement. À $n = 35$ , le rapport entre naïf et itératif atteint $1, 7 \cdot 1 0^{6}$ : la différence entre les deux programmes n'est pas une affaire de langage, de compilateur ou de machine, mais de , et aucun matériel n'y changera rien. En extrapolant la mesure par le facteur , la version naïve demanderait environ 22 secondes pour , 45 minutes pour , et près de 160 ans pour — alors que la version itérative répond en une microseconde.

La récursivité n'est pas toujours le bon outil

La récursivité est une manière d'écrire, pas une vertu. Deux situations opposées le montrent.

Un cas où l'itération est strictement meilleure. Pour la factorielle, la somme d'une liste, le parcours d'un tableau ou le calcul de $F_{n}$ , la version récursive n'apporte rien et coûte deux choses: un cadre de pile par élément, donc une mémoire $Θ (n)$ là où la boucle utilise $Θ (1)$ , et le surcoût d'un appel de fonction par élément. Sur 5000 éléments, la somme récursive en Python ne s'exécute même pas: elle lève RecursionError, quand la boucle aboutit sans difficulté. Toute récursion qui décrémente d'une unité — f(n) appelle f(n-1) une seule fois — est une boucle déguisée, et il vaut mieux écrire la boucle. (Certains langages, dont Scheme et OCaml, éliminent les appels terminaux et transforment automatiquement cette récursion en boucle; CPython ne le fait pas, délibérément.)

Question 3.3

Classez ces quatre façons de calculer $F_{n}$ pour $n$ grand, de la plus coûteuse à la moins coûteuse, en départageant les deux méthodes linéaires par la mémoire qu'elles consomment.

Glissez les éléments pour les mettre dans le bon ordre

Récursion mémoïsée:

Θ (n)

opérations et

Θ (n)

mémoire

Exponentiation rapide de la matrice de Fibonacci:

Θ (lo g_{2} n)

multiplications

Boucle à deux variables:

Θ (n)

opérations et

Θ (1)

mémoire

Récursion naïve:

Θ (φ^{n})

opérations

La recherche dichotomique

Le problème et l'algorithme

Chercher une valeur dans un tableau trié est le premier exemple sérieux de diviser pour régner, et le plus simple: on divise, on résout une seule des deux moitiés, et il n'y a rien à recombiner.

L'idée est celle du jeu où l'on doit deviner un nombre entre 1 et 100: on propose 50, on apprend si la cible est au-dessus ou en dessous, et l'on a éliminé la moitié des possibilités en une question. Sur un tableau trié $a [0.. n - 1]$ , on compare la cible $x$ à l'élément central $a [m]$ ; si $a [m] = x$ c'est fini, si $a [m] < x$ la cible ne peut être que dans la moitié droite, et si $a [m] > x$ que dans la moitié gauche.

fonction dichotomie(a, x)
    bas ← 0 ; haut ← longueur(a) - 1
    tant que bas ≤ haut faire
        m ← partie_entiere((bas + haut) / 2)
        si a[m] = x alors retourner m
        sinon si a[m] < x alors bas ← m + 1
        sinon haut ← m - 1
    retourner «absent»

L'invariant et la correction

Démonstration. Invariant. Nous affirmons qu'au début de chaque tour de boucle, si $x$ figure dans $a$ , alors son indice appartient à l'intervalle $[bas, haut]$ .

Avant le premier tour, l'intervalle est $[0, n - 1]$ tout entier: l'invariant est vrai. Supposons-le vrai au début d'un tour. Trois cas. Si $a [m] = x$ , on retourne $m$ et la conclusion est acquise. Si $a [m] < x$ , alors, le tableau étant trié, tout indice $i \leq m$ vérifie $a [i] \leq a [m] < x$ , donc aucun indice inférieur ou égal à ne porte ; l'indice cherché, s'il existe, est donc dans , qui est le nouvel intervalle. Le cas est symétrique. L'invariant est donc conservé.

Terminaison. Posons $k = haut - bas + 1$ , le nombre de candidats. Comme $bas \leq m \leq haut$ , chacune des deux branches retire au moins l'élément $m$ , donc $k$ décroît strictement à chaque tour tout en restant entier positif ou nul. La boucle s'arrête donc, soit par un retour, soit quand $k = 0$ , c'est-à-dire .

Correction. Si la boucle se termine par $bas > haut$ , l'intervalle est vide; par l'invariant, $x$ ne figure pas dans $a$ , et retourner «absent» est correct.

Coût. Précisons la décroissance. Avec $m = ⌊(bas + haut) /2 ⌋$ , la moitié gauche compte $m - bas = ⌊(k - 1) /2 ⌋$ éléments et la moitié droite $haut - m = ⌈(k - 1) /2 ⌉$ ; dans les deux cas le nouveau nombre de candidats est au plus . Partant de , après comparaisons il reste au plus candidats. La boucle s'arrête dès que ce nombre atteint , c'est-à-dire dès que , soit .

La formule (3.5) est d'une sobriété remarquable. Pour $n = 7$ elle donne $3$ ; pour $n = 1 0^{6}$ elle donne $20$ ; pour $n = 1 0^{9}$ elle donne $30$ . Chercher dans un annuaire d'un milliard de noms coûte trente comparaisons. C'est ce que le chapitre 2 appelle , et c'est la deuxième meilleure classe de complexité après .

Exemple 3.1 · Recherche de la valeur 10 pas à pas

Prenons le tableau du cours, trié: $a = [3, 9, 10, 27, 38, 43, 82]$ , et cherchons $x = 10$ . Les étapes sont celles de la figure 3.2, et elles ont été produites en exécutant l'algorithme.

Étape	bas	haut	$m$	$a [m]$

Question 3.4

Un tableau trié contient $n = 2000000$ éléments. Combien de comparaisons la recherche dichotomique effectue-t-elle au pire?

Diviser pour régner

Le schéma général

La dichotomie est un cas particulier d'un schéma qui organise une grande partie de l'algorithmique.

Dans la dichotomie, $a = 1$ (on ne résout qu'une moitié), $b = 2$ , et $f (n) = Θ (1)$ : une comparaison pour choisir la moitié, rien à combiner. Dans le tri fusion, $a = 2$ , $b = 2$ et $f (n) = Θ (n)$ : la division est triviale (couper au milieu) mais la combinaison est le vrai travail.

Le tri fusion

Tout repose sur la fusion. Deux tableaux déjà triés se fusionnent en parcourant les deux de front avec un doigt sur chacun: on compare les deux éléments pointés, on recopie le plus petit, on avance le doigt correspondant, et l'on recommence. Quand un des deux est épuisé, on recopie le reste de l'autre.

fonction fusionner(G, D)
    R ← tableau vide ; i ← 0 ; j ← 0
    tant que i < longueur(G) et j < longueur(D) faire
        si G[i] ≤ D[j] alors ajouter G[i] à R ; i ← i + 1
        sinon                 ajouter D[j] à R ; j ← j + 1
    ajouter le reste de G puis le reste de D à R
    retourner R

Chaque tour de boucle effectue une comparaison et écrit un élément. Comme il y a $∣ G ∣ + ∣ D ∣$ éléments à écrire au total et que la boucle s'arrête quand l'un des deux tableaux est épuisé, le nombre de comparaisons d'une fusion est compris entre $min (∣ G ∣, ∣ D ∣)$ et $∣ G ∣ + ∣ D ∣ - 1$ : la fusion de deux tableaux totalisant $n$ éléments coûte $Θ (n)$ , ce qui est optimal puisqu'il faut de toute façon lire les éléments.

La correction de la fusion tient dans un invariant: à chaque tour, $R$ contient, triés, les $i + j$ plus petits éléments de $G \cup D$ , et tous les éléments non encore recopiés leur sont supérieurs ou égaux. Il est vrai au départ ( $R$ vide) et se conserve, parce que le plus petit élément restant est nécessairement $G [i]$ ou $D [j]$ — les deux tableaux étant triés, aucun élément situé plus loin ne peut être plus petit que celui que son doigt pointe.

Démonstration. Par récurrence forte sur $n$ . Si $n \leq 1$ , le tableau est trié par définition et l'algorithme le retourne tel quel. Soit $n \geq 2$ ; supposons le résultat acquis pour toute taille strictement inférieure à $n$ . Les deux moitiés ont pour tailles $⌊ n /2 ⌋$ et $⌈ n /2 ⌉$ , toutes deux comprises entre $1$ et $n - 1$ dès que : l'hypothèse de récurrence s'applique et les deux appels retournent les moitiés triées. La fusion de deux tableaux triés retourne, par son invariant, un tableau trié contenant exactement leurs éléments. Le résultat est donc une permutation triée de . La terminaison suit du même argument: la taille décroît strictement à chaque appel et le cas de base est atteint.

Le tableau du cours, déroulé

Appliquons le tri fusion au tableau fixé du cours, $[38, 27, 43, 3, 9, 82, 10]$ — celui-là même que le chapitre 2 trie par insertion. La figure 3.3 montre la descente, la remontée et le compte de comparaisons de chaque fusion; toutes ces valeurs proviennent de l'exécution effective de l'algorithme, pas d'un comptage à la main.

Suivons la moitié droite, $[3, 9, 82, 10]$ . Elle se coupe en $[3, 9]$ et $[82, 10]$ . Chacune se coupe en deux singletons, déjà triés. Fusionner $[3]$ et $[9]$ demande une comparaison ( $3 \leq 9$ ) et donne $[3, 9]$ ; fusionner et en demande une aussi () et donne . Fusionner et demande deux comparaisons: recopie , recopie , et la moitié gauche est épuisée — le reste, , est recopié sans aucune comparaison. On obtient pour quatre comparaisons au total sur cette branche.

La fusion finale, celle de $[27, 38, 43]$ et $[3, 9, 10, 82]$ , en demande six: $27$ contre $3$ , contre $9$ , contre $10$ , puis $27$ contre $82$ (recopie $27$ ), $38$ contre (recopie ), contre (recopie ); la moitié gauche est épuisée et est recopié gratuitement. Le grand total est .

Exemple 3.2 · Treize contre quinze contre vingt et un

Comparons les trois tris sur le même tableau de sept éléments. Les trois nombres ci-dessous sont des comptages d'exécution: chaque algorithme a été instrumenté d'un compteur incrémenté à chaque comparaison de clés, y compris la comparaison qui échoue et met fin à une boucle interne.

Algorithme	Comparaisons sur le tableau du cours	Pire cas pour $n = 7$
Tri fusion	13	14
Tri par insertion	15	21
Tri par sélection	21	21

Sur sept éléments, l'écart est modeste — treize contre quinze — et c'est normal: $n lo g_{2} n$ et $n^{2}$ ne se séparent pas pour . Le tri par sélection effectue toujours exactement comparaisons, quelle que soit l'entrée. Le tri par insertion en effectue entre (tableau déjà trié) et (tableau à l'envers); sur les permutations possibles, sa moyenne mesurée est de comparaisons. Le tri fusion, lui, varie entre et selon la permutation, pour une moyenne mesurée de — il est donc surtout remarquable par sa : son pire cas est à peine plus mauvais que son cas moyen.

Question 3.5

Combien de comparaisons le tri fusion effectue-t-il au pire sur un tableau de $n = 8$ éléments? On utilisera la formule du pire cas $n ⌈ lo g_{2} n ⌉ - 2^{⌈ l o g_{2} n ⌉} + 1$ .

Relations de récurrence

Poser la récurrence

Le coût d'un algorithme diviser pour régner ne se lit pas dans une boucle: il se lit dans une équation. Si $T (n)$ désigne le nombre d'opérations élémentaires sur une entrée de taille $n$ , la définition même du schéma donne

T (n) = a T (\frac{n}{b}) + f (n), T (1) = Θ (1), (3.6)

avec $a \geq 1$ sous-problèmes de taille $n / b$ ( $b > 1$ ) et un coût $f (n)$ pour diviser et combiner. Pour le tri fusion, $a = 2$ , $b = 2$ et $f (n) = Θ (n)$ — la fusion coûte un passage sur les éléments. Pour la dichotomie, , et .

Nous écrivons $n / b$ sans nous soucier de la divisibilité; en toute rigueur, il faudrait $⌊ n / b ⌋$ et $⌈ n / b ⌉$ . On démontre que cela ne change pas l'ordre de grandeur de la solution, et nous l'admettons: la démonstration est un exercice de comptabilité sur les parties entières, sans idée nouvelle.

L'arbre de récursion

La méthode la plus éclairante pour résoudre (3.6) consiste à dessiner l'arbre des appels et à sommer le travail niveau par niveau. Au niveau $k$ , il y a $a^{k}$ sous-problèmes, chacun de taille $n / b^{k}$ , chacun coûtant $f (n / b^{k})$ hors appels récursifs. Le travail du niveau $k$ vaut donc $a^{k} f (n / b^{k})$ . Les feuilles sont atteintes quand , soit ; il y a alors feuilles, chacune de coût constant. D'où

T (n) = feuilles n^{l o g_{b} a} + k = 0 \sum l o g_{b} n - 1 a^{k} f (\frac{n}{b ^{k}}) . (3.7)

Tout se joue alors dans la comparaison entre le coût des feuilles, $n^{l o g_{b} a}$ , et le coût de la racine, $f (n)$ . Trois régimes apparaissent, et ce sont exactement les trois cas du théorème maître.

Premier régime: le travail par niveau croît vers le bas. Prenons le tri fusion, $T (n) = 2 T (n /2) + n$ , avec $n = 8$ . Le niveau $0$ compte un problème de taille $8$ , coût $8$ . Le niveau $1$ compte deux problèmes de taille $4$ , coût $2 \times 4 = 8$ . Le niveau : quatre problèmes de taille , coût . Le niveau : huit problèmes de taille , coût . , et il y a niveaux, d'où . C'est le cas d'équilibre, celui où et coïncident.

Deuxième régime: les feuilles dominent. Prenons $T (n) = 4 T (n /2) + n$ . Le niveau $k$ coûte $4^{k} \cdot n / 2^{k} = 2^{k} n$ : il double à chaque descente. La somme est géométrique de raison et vaut donc, à un facteur près, son dernier terme: . Ici écrase , et . La vérification numérique sur la récurrence exacte , , donne pour , soit un rapport qui tend vers : le est bien la bonne réponse.

Troisième régime: la racine domine. Prenons $T (n) = 2 T (n /2) + n^{2}$ . Le niveau $k$ coûte $2^{k} (n / 2^{k})^{2} = n^{2} / 2^{k}$ : il est divisé par deux à chaque descente. La somme géométrique de raison converge et vaut au plus , d'où — le coût est celui du niveau seul. La vérification numérique donne pour , soit un rapport qui tend vers .

Le théorème maître

Ces trois régimes se résument en un énoncé.

Ce théorème est admis. La raison est claire et vaut d'être dite: sa démonstration ne contient aucune idée que l'arbre de récursion ci-dessus n'ait déjà livrée, mais elle exige de traiter proprement les parties entières — les sous-problèmes n'ont pas tous exactement la taille $n / b^{k}$ — et de majorer la somme (3.7) par une série géométrique dans chacun des trois cas. C'est un travail technique de deux pages, mené dans le chapitre 4 de Cormen, Leiserson, Rivest et Stein. Ce qu'il faut retenir et savoir justifier, c'est l'argument de l'arbre: comparer le coût des feuilles au coût de la racine.

Trois applications

Explorateur 3.1 · Arbre d'appels: profondeur et facteur de branchement

À gauche, la version linéaire (un appel par niveau). À droite, l'arbre complet où chaque appel en engendre b. Modèle didactique: l'arbre binaire complet majore l'arbre de Fibonacci naïf, qui n'est pas complet.

Profondeur d3

Facteur de branchement b2

Feuilles b^d

Appels de la récursion

Appels version linéaire

Profondeur de pile

4cadres

Rapport récursif / linéaire

3,8 ×

Lecture

b ≥ 2: coût exponentiel en d

Question 3.6

À quelle classe appartient la solution de $T (n) = 3 T (n /2) + n$ ?

La borne inférieure: aucun tri par comparaisons ne bat n log n

Nous savons trier en $Θ (n lo g_{2} n)$ . La question qui vient naturellement est: peut-on faire mieux? Une réponse négative à cette question n'est pas un aveu d'échec, c'est un théorème — et un théorème d'une nature particulière, car il ne parle pas d'un algorithme mais de tous les algorithmes d'une famille, y compris ceux que personne n'a encore écrits. C'est le sommet intellectuel de ce chapitre.

Le modèle: le tri par comparaisons

Il faut d'abord dire précisément de quoi l'on parle, car une borne inférieure n'a de sens que dans un modèle de calcul.

Le tri par insertion, le tri par sélection, le tri fusion, le tri rapide et le tri par tas sont des tris par comparaisons. Le tri par comptage et le tri par base n'en sont pas: ils utilisent les valeurs elles-mêmes comme indices, ce qui suppose un univers de valeurs restreint. Cette distinction est essentielle: le théorème ci-dessous ne s'applique pas à eux, et c'est pourquoi ils peuvent trier en $Θ (n)$ dans leur domaine de validité.

L'arbre de décision

Fixons un algorithme de tri par comparaisons et une taille $n$ , et supposons les $n$ éléments deux à deux distincts. Exécutons l'algorithme. Son déroulement est entièrement déterminé par les réponses successives aux comparaisons qu'il pose: à entrée donnée, il pose une première comparaison, et selon la réponse — oui ou non — il pose une deuxième comparaison ou bien il conclut.

Deux observations, et le théorème est démontré.

La première: l'arbre a au moins $n!$ feuilles. En effet, l'algorithme doit être correct sur chacune des $n!$ façons d'ordonner $n$ éléments distincts. Or deux entrées demandant des permutations différentes pour être triées ne peuvent aboutir à la même feuille: la feuille détermine la permutation appliquée, et une seule permutation trie une entrée donnée. Chacune des $n!$ permutations doit donc étiqueter au moins une feuille.

La seconde: un arbre binaire de hauteur $h$ a au plus $2^{h}$ feuilles. Récurrence immédiate sur $h$ : un arbre de hauteur $0$ est une feuille, soit $1 = 2^{0}$ ; un arbre de hauteur $h$ a deux sous-arbres de hauteur au plus $h - 1$ , donc au plus feuilles.

Démonstration. Soit $h$ la hauteur de l'arbre de décision de l'algorithme pour la taille $n$ , c'est-à-dire son nombre de comparaisons dans le pire des cas. Les deux observations donnent

n! \leq nombre de feuilles \leq 2^{h},

d'où $2^{h} \geq n!$ et, en passant au logarithme de base 2, $h \geq lo g_{2} (n!)$ . Comme $h$ est entier, $h \geq ⌈ lo g_{2} (n!)⌉$ , ce qui établit (3.8).

Minorons maintenant $lo g_{2} (n!)$ sans aucun outil sophistiqué. Dans le produit $n! = 1 \cdot 2 \dots n$ , ne conservons que les $⌈ n /2 ⌉$ derniers facteurs; chacun est supérieur ou égal à $n /2$ . Donc

n! \geq (\frac{n}{2})^{n /2}, d’o \overset{u}{ˋ} lo g_{2} (n!) \geq \frac{n}{2} lo g_{2} \frac{n}{2} = \frac{n}{2} (lo g_{2} n - 1) .

Pour $n \geq 4$ on a $lo g_{2} n - 1 \geq \frac{1}{2} lo g_{2} n$ , donc : la borne annoncée vaut avec .

La constante exacte, par Stirling

La minoration élémentaire ci-dessus suffit pour l'ordre de grandeur, mais elle est lâche d'un facteur 4. La formule de Stirling donne la valeur exacte de l'asymptotique:

n! \sim 2 π n (\frac{n}{e})^{n} ⟹ lo g_{2} (n!) = n lo g_{2} n - n lo g_{2} e + \frac{1}{2} lo g_{2} (2 π n) + o (1), (3.9)

avec $lo g_{2} e \approx 1, 4427$ . Le terme dominant est donc bien $n lo g_{2} n$ , et le second terme, $- 1, 4427 n$ , est linéaire: il ne change pas la classe de complexité. La qualité de l'approximation (3.9) a été vérifiée numériquement: pour $n = 100$ , et la formule de Stirling donne , soit un écart relatif de ; pour l'écart relatif tombe à environ.

Retenez la conclusion sous la forme la plus parlante: pour trier $n$ objets, il faut au moins $n lo g_{2} n - 1, 44 n$ comparaisons, et le tri fusion en effectue au plus $n ⌈ lo g_{2} n ⌉ - 2^{⌈ l o g_{2} n ⌉} + 1$ , soit à peu près . Il n'y a pas d'algorithme de tri par comparaisons dix fois plus rapide qui attendrait d'être découvert: la borne est une propriété du problème, pas une limite de notre ingéniosité.

Question 3.7

Quel est le nombre minimal de comparaisons, au pire des cas, que doit effectuer un tri par comparaisons sur $n = 10$ éléments? On donnera $⌈ lo g_{2} (10!)⌉$ .

Les tours de Hanoï

Le problème

Trois piquets, $n$ disques de diamètres tous différents empilés sur le premier par taille décroissante. Il s'agit de transporter la pile entière sur le troisième piquet en respectant deux règles: on ne déplace qu'un disque à la fois, et l'on ne pose jamais un disque sur un disque plus petit.

La solution récursive se lit presque sans y penser. Pour déplacer $n$ disques de $A$ vers $C$ en s'aidant de $B$ : déplacer les $n - 1$ disques du dessus de $A$ vers $B$ (en s'aidant de $C$ ), déplacer le grand disque de $A$ vers $C$ , puis déplacer les disques de vers (en s'aidant de ).

procédure hanoi(n, depart, auxiliaire, arrivee)
    si n = 0 alors retourner            # rien à déplacer
    hanoi(n - 1, depart, arrivee, auxiliaire)
    déplacer un disque de depart vers arrivee
    hanoi(n - 1, auxiliaire, depart, arrivee)

Quatre lignes. Il serait difficile de faire plus court, et une version itérative existe mais demande de raisonner sur la parité de $n$ et sur un ordre cyclique des piquets — l'exemple parfait d'un problème où la récursivité est le bon outil, celui annoncé dans l'avertissement plus haut.

Notez que la correction se prouve exactement comme le théorème 3.1: si l'on admet que les deux appels récursifs déplacent correctement $n - 1$ disques, alors la séquence complète est légale — pendant le déplacement du grand disque, les $n - 1$ autres sont tous sur $B$ , et le grand disque est plus grand que tous, donc aucune règle n'est violée.

Le nombre de coups

Démonstration. La formule. La structure de la procédure donne la récurrence

H (0) = 0, H (n) = 2 H (n - 1) + 1 (n \geq 1), (3.10)

puisqu'elle effectue deux fois le travail pour $n - 1$ disques plus un déplacement. Montrons $H (n) = 2^{n} - 1$ par récurrence. Pour $n = 0$ : $2^{0} - 1 = 0$ . Si , alors

H (n) = 2 (2^{n - 1} - 1) + 1 = 2^{n} - 2 + 1 = 2^{n} - 1.

L'optimalité. Soit $M (n)$ le nombre minimal de déplacements, toutes stratégies confondues. Le plus grand disque doit quitter $A$ au moins une fois. À l'instant où il quitte $A$ pour aller sur $C$ — ce doit être vers $C$ , sinon il faudra l'en ressortir plus tard — les $n - 1$ autres disques ne peuvent être ni sur $A$ (ils seraient au-dessus de lui) ni sur $C$ (ils empêcheraient de l'y poser): ils sont donc tous sur $B$ . Les amener tous sur coûte au moins déplacements; le grand disque en coûte au moins un; les ramener ensuite de vers en coûte au moins . Donc , avec ; la même récurrence donne . Comme la procédure atteint cette valeur, .

Cette récurrence est du type $T (n) = 2 T (n - 1) + 1$ : elle décrémente au lieu de diviser, et le théorème maître ne s'y applique pas, comme l'avertissement plus haut l'annonçait. Elle produit une complexité $Θ (2^{n})$ , exponentielle, et cette fois ce n'est pas une maladresse d'implémentation: c'est la difficulté intrinsèque du problème, puisque la borne inférieure vaut pour toute stratégie.

Synthèse

Une définition récursive comporte un cas de base, un cas récursif et une taille qui décroît strictement; les trois sont nécessaires. Prouver qu'un algorithme récursif est correct, c'est faire une démonstration par récurrence: le cas de base est l'initialisation, l'appel récursif est l'hypothèse de récurrence.
Chaque appel en cours occupe un cadre sur la pile d'appels (paramètres, variables locales, adresse de retour). La pile est de taille fixe: une récursion de profondeur linéaire finit par déborder — en Python, dès 998 appels avec la limite par défaut — alors qu'une récursion qui divise reste à une profondeur d'une vingtaine de cadres pour un million d'éléments.
La version récursive naïve de Fibonacci effectue exactement $2 F_{n + 1} - 1$ appels, soit $Θ (φ^{n})$ avec $φ \approx 1, 618$ : 15 appels pour , 2 692 537 pour , 331 160 281 pour . La mémoïsation ramène le coût à temps et mémoire, la boucle à deux variables à temps et mémoire. Mesuré: 1,98 s contre 1,14 µs à .

Série d'exercices du chapitre 3Exercice 1 sur 5

Question 3.8

Combien d'appels la version récursive naïve de Fibonacci effectue-t-elle pour calculer $F_{7} = 13$ ? On compte l'appel initial.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Exercice 3.1 · Trois définitions récursives

Pour chacune des fonctions suivantes, identifiez le ou les cas de base, le cas récursif, l'argument de décroissance, et dites si la définition est bien fondée. Si elle ne l'est pas, corrigez-la.

$s (n)$ = somme des entiers de $1$ à $n$ : $s (0) = 0$ et $s (n) = n + s (n - 1)$ .

Exercice 3.2 · Compter les appels et les additions

Soit fib la version récursive naïve.

Combien d'appels et combien d'additions fib(6) effectue-t-il?
Combien de fois fib(2) est-il évalué au cours de fib(6)?
Montrez que le nombre d'additions vaut $F_{n + 1} - 1$ , et interprétez ce résultat.
Pour $n = 40$ , estimez le temps d'exécution de la version naïve sachant que la version mesurée traite $n = 35$ en 1,98 s.

Exercice 3.3 · Dichotomie: invariant, pire cas, variantes

Sur le tableau trié $a = [3, 9, 10, 27, 38, 43, 82]$ , déroulez la recherche de $x = 82$ et celle de $x = 11$ , en donnant à chaque étape l'intervalle et le pivot.
Quelle est la valeur de $x$ trouvée en une seule comparaison? Combien de valeurs du tableau demandent exactement trois comparaisons?

Exercice 3.4 · Récurrences et théorème maître

Résolvez, en indiquant le cas du théorème maître utilisé ou en expliquant pourquoi il ne s'applique pas.

$T (n) = 4 T (n /2) + n^{2}$ .
$T (n) = 3 T (n /4) + n lo g_{2} n$ .

Exercice 3.5 · La borne n log n et ce qu'elle interdit

Un ami affirme avoir écrit un tri par comparaisons qui trie $n$ éléments en $Θ (n)$ comparaisons au pire. Démontrez qu'il se trompe.
Combien de comparaisons faut-il au minimum pour trier 5 éléments? Et 12?
On dispose de 12 pièces d'apparence identique dont une est fausse, plus lourde ou plus légère. On ne dispose que d'une balance à deux plateaux, qui indique «gauche plus lourd», «équilibre» ou «droite plus lourde». Donnez une borne inférieure sur le nombre de pesées nécessaires pour identifier la fausse pièce et dire si elle est plus lourde ou plus légère.
Le tri fusion effectue au plus $n ⌈ lo g_{2} n ⌉ - 2^{⌈ l o g_{2} n ⌉} + 1$ comparaisons. Pour , comparez cette majoration à la borne et concluez.

Références

Cormen, T. H., Leiserson, C. E., Rivest, R. L. & Stein, C., Introduction to Algorithms, 4e édition, MIT Press — chapitres 2 (tri fusion, invariants), 4 (récurrences, théorème maître, Strassen) et 8 (borne des tris par comparaisons).
Sipser, M., Introduction to the Theory of Computation, Cengage — pour le lien entre récursivité, récurrence et définitions inductives.
Knuth, D. E., The Art of Computer Programming, volume 3: Sorting and Searching, Addison-Wesley — section 5.3.1 pour le nombre minimal de comparaisons et l'algorithme de tri par fusion-insertion.
Abelson, H., Ledeen, K. & Lewis, H., Blown to Bits, Addison-Wesley — pour la portée des ordres de grandeur exponentiels hors de l'informatique.
Polycopiés du cours ICC de l'EPFL, partie «algorithmique et complexité».

1	0	6	3	27	$27 > 10$ : haut $\leftarrow 2$
2	0	2	1	9	$9 < 10$ : bas $\leftarrow 2$
3	2	2	2	10	trouvé à l'indice 2

$n$	Tri fusion	Tri par insertion	Rapport
100	543	2 444	4,5
1 000	8 701	248 538	28,6
10 000	120 443	25 078 356	208,2

Étape	bas	haut	$m$	$a [m]$	Décision
1	0	6	3	27	$27 < 82$ : bas $\leftarrow 4$
2	4	6	5	43	$43 < 82$ : bas $\leftarrow 6$
3	6	6	6	82	trouvé à l'indice 6

Étape	bas	haut	$m$	$a [m]$	Décision
1	0	6	3	27	$27 > 11$ : haut $\leftarrow 2$
2	0	2	1	9	$9 < 11$ : bas $\leftarrow 2$
3	2	2	2	10	$10 < 11$ : bas

Objectifs du chapitre

Définitions récursives

Un objet défini à partir de lui-même

La factorielle

La suite de Fibonacci

Récursivité et récurrence: le même objet

La pile d'appels

Ce qu'un appel coûte

La profondeur est bornée

Fibonacci récursif naïf: l'anatomie d'une catastrophe

Le programme

L'arbre des appels

Combien d'appels, exactement

Mémoïsation: se souvenir

Itération: ne rien empiler du tout

Les trois coûts, mesurés

La recherche dichotomique

Le problème et l'algorithme

L'invariant et la correction

Diviser pour régner

Le schéma général

Le tri fusion

Le tableau du cours, déroulé

Relations de récurrence

Poser la récurrence

L'arbre de récursion

Le théorème maître

Trois applications

La borne inférieure: aucun tri par comparaisons ne bat n log n

Le modèle: le tri par comparaisons

L'arbre de décision

La constante exacte, par Stirling

Les tours de Hanoï

Le problème

Le nombre de coups

Synthèse

Exercices

Références

Poser la récurrence

Résoudre par l'arbre de récursion

La forme générale, et le théorème maître

Comparer avec la boucle