Exercices corrigés : récurrence et récursivité (201-N11)

a) Soit $P(n)$ une propriété dépendant d'un entier $n$. Si (1) INITIALISATION : $P(n_{0})$ est vraie pour un premier rang $n_{0}$ ; et (2) HÉRÉDITÉ : pour tout $k\geq n_{0}$, $P(k)$ vraie entraîne $P(k+1)$ vraie ; alors $P(n)$ est vraie pour tout $n\geq n_{0}$. L'hérédité est une implication, pas une affirmation : on ne prétend jamais que $P(k)$ est vraie, on suppose qu'elle l'est.

b) INITIALISATION en $n=1$ : le membre de gauche vaut 1, celui de droite $\frac{1\times 2}{2}=1$ ✓. HÉRÉDITÉ : supposons $1+2+\dots+k=\frac{k(k+1)}{2}$ pour un certain $k\geq 1$. Alors $1+2+\dots+k+(k+1)=\frac{k(k+1)}{2}+(k+1)=(k+1)\left(\frac{k}{2}+1\right)=\frac{(k+1)(k+2)}{2}$, qui est bien la formule au rang $k+1$ ✓. Contrôle numérique en $n=10$ : $\frac{10\times 11}{2}=55$, et la somme vaut effectivement 55.

c) Sans initialisation, l'hérédité seule ne prouve rien. Prenons $P(n)$ : « $n=n+1$ ». L'hérédité est PARFAITEMENT VRAIE : si $k=k+1$, alors en ajoutant 1 aux deux membres on obtient $k+1=k+2$, donc $P(k+1)$. La chaîne d'implications est irréprochable, et pourtant $P(n)$ est fausse pour tout $n$, faute d'un premier domino à pousser. C'est le contre-exemple à retenir, parce qu'il montre qu'une hérédité valide n'a aucune valeur toute seule.

d) Sans hérédité, vérifier des cas ne prouve rien non plus. La propriété « $n^{2}+n+41$ est premier » est vraie pour $n=0$, où l'on obtient 41, pour $n=1$, où l'on obtient 43, et en fait pour tous les entiers de 0 à 39. Elle est FAUSSE en $n=40$, car $40^{2}+40+41=1681=41^{2}$. Quarante vérifications successives ne valent pas une démonstration : l'hérédité est ce qui remplace une infinité de vérifications.

e) Le geste initial, la main qui pousse le premier domino, représente l'INITIALISATION. La chaîne, c'est-à-dire le fait que chaque domino soit assez près du suivant pour le faire tomber, représente l'HÉRÉDITÉ. Sans le geste, la chaîne reste debout ; sans la chaîne, seul le premier tombe. Il faut donc les deux, et l'image dit aussi pourquoi : chacun des deux ingrédients est inutile sans l'autre.

a) INITIALISATION en $n=1$ : à gauche 1, à droite $\frac{1\times 2\times 3}{6}=1$ ✓. HÉRÉDITÉ : en supposant la formule au rang $k$, la somme au rang $k+1$ vaut $\frac{k(k+1)(2k+1)}{6}+(k+1)^{2}=\frac{(k+1)\left[k(2k+1)+6(k+1)\right]}{6}=\frac{(k+1)\left(2k^{2}+7k+6\right)}{6}=\frac{(k+1)(k+2)(2k+3)}{6}$, qui est la formule au rang $k+1$ ✓. Le pas décisif est la factorisation de $2k^{2}+7k+6$ en $(k+2)(2k+3)$ : on la trouve en cherchant la forme attendue, jamais en développant au hasard. Contrôle en $n=5$ : $1+4+9+16+25=55$ et $\frac{5\times 6\times 11}{6}=55$ ✓.

b) Le rang 5 est nécessaire : en $n=2$, $4>4$ est faux ; en $n=3$, $8>9$ est faux ; en $n=4$, $16>16$ est faux. En $n=5$ : $32>25$ ✓, l'initialisation passe. HÉRÉDITÉ : supposons $2^{k}>k^{2}$ avec $k\geq 5$. Alors $2^{k+1}=2\times 2^{k}>2k^{2}$. Il reste à montrer que $2k^{2}\geq(k+1)^{2}$, c'est-à-dire $k^{2}-2k-1\geq 0$, ce qui est vrai dès $k\geq 3$ puisque $k^{2}-2k-1=(k-1)^{2}-2$. Donc $2^{k+1}>(k+1)^{2}$ ✓. Une inégalité par récurrence demande presque toujours cette étape supplémentaire de majoration.

c) INITIALISATION : $3^{2}-2=9-2=7$, divisible par 7 ✓. HÉRÉDITÉ : supposons $3^{2k}-2^{k}=7m$ pour un entier $m$. Alors $3^{2(k+1)}-2^{k+1}=9\times 3^{2k}-2\times 2^{k}=9\left(3^{2k}-2^{k}\right)+9\times 2^{k}-2\times 2^{k}=9\times 7m+7\times 2^{k}=7\left(9m+2^{k}\right)$, multiple de 7 ✓. L'astuce est de faire apparaître de force l'expression du rang $k$ en ajoutant et retranchant le terme manquant. Contrôle en $n=3$ : $729-8=721=7\times 103$ ✓.

d) SOMME : l'hypothèse remplace la somme des $k$ premiers termes par sa forme close, ce qui transforme une somme en expression algébrique. INÉGALITÉ : l'hypothèse fournit la minoration $2^{k}>k^{2}$ qu'on multiplie par 2. DIVISIBILITÉ : l'hypothèse fournit l'écriture $3^{2k}-2^{k}=7m$, que l'on met en facteur. Dans les trois cas, elle sert à REMPLACER une expression du rang $k$ par quelque chose de connu.

e) Parce que si l'hypothèse ne sert jamais, c'est que l'on a démontré $P(k+1)$ directement, sans rien supposer : la récurrence n'était donc pas nécessaire, et il est bien plus probable qu'on ait commis une erreur, typiquement en supposant ce qu'il fallait démontrer. Le contrôle vaut d'être fait systématiquement : relire l'hérédité et pointer du doigt l'endroit exact où l'hypothèse a été employée. Si l'on n'en trouve pas, il y a un problème.

a) RÉCURRENCE FORTE : si $P(n_{0})$ est vraie, et si pour tout $k$ le fait que $P(n_{0}),P(n_{0}+1),\dots,P(k)$ soient TOUTES vraies entraîne $P(k+1)$, alors $P(n)$ est vraie pour tout $n\geq n_{0}$. La différence tient à l'hypothèse : on ne dispose plus du seul rang $k$ mais de TOUS les rangs jusqu'à $k$. Les deux principes sont en fait logiquement équivalents, mais la forme forte est bien plus commode dès qu'on décompose un objet en morceaux de tailles inconnues.

b) INITIALISATION : 2 est premier, il est donc son propre diviseur premier ✓. HÉRÉDITÉ FORTE : soit $n\geq 3$, et supposons la propriété vraie pour tous les entiers de 2 à $n-1$. Deux cas. Si $n$ est premier, il admet $n$ comme diviseur premier ✓. Sinon, $n$ s'écrit $n=ab$ avec $2\leq a<n$, et l'hypothèse forte appliquée à $a$ fournit un diviseur premier $p$ de $a$ ; comme $p$ divise $a$ qui divise $n$, $p$ divise $n$ ✓. On voit pourquoi la récurrence ordinaire ne suffirait pas : le facteur $a$ n'a aucune raison d'être égal à $n-1$.

c) Il en faut DEUX, aux rangs 0 et 1. La raison est que l'hérédité déduit le rang $n+2$ des rangs $n+1$ ET $n$ : pour démarrer, il faut donc disposer de deux valeurs consécutives déjà établies. Avec une seule initialisation, on ne pourrait jamais calculer $F_{2}$, faute de connaître l'un des deux termes dont il dépend.

d) INITIALISATIONS : $F_{0}=0<1=2^{0}$ ✓ et $F_{1}=1<2=2^{1}$ ✓. HÉRÉDITÉ : supposons $F_{k}<2^{k}$ et $F_{k+1}<2^{k+1}$. Alors $F_{k+2}=F_{k+1}+F_{k}<2^{k+1}+2^{k}=2^{k}\left(2+1\right)=3\times 2^{k}<4\times 2^{k}=2^{k+2}$ ✓. La majoration finale est généreuse, et c'est volontaire : on démontre ce qu'on demande, pas le meilleur résultat possible. Contrôle : $F_{10}=55<1024=2^{10}$ ✓.

e) Oui, elle échoue. Cette suite vérifie $u_{n}=2^{n+1}-1$ : on a $u_{0}=1$, $u_{1}=3$, $u_{2}=3\times 3-2\times 1=7$, $u_{3}=3\times 7-2\times 3=15$. Supposons qu'on veuille démontrer « $u_{n}$ est impair » en n'initialisant qu'au rang 0. L'hérédité $u_{n+2}=3u_{n+1}-2u_{n}$ demande $u_{n+1}$ ET $u_{n}$ ; à l'étape qui produit $u_{2}$, on ne dispose que de $u_{0}$ et la démonstration s'arrête net. Ce n'est pas une subtilité de rédaction : le nombre d'initialisations doit toujours être égal au nombre de rangs antérieurs dont dépend la relation.

a) La version récursive traduit littéralement la définition $n!=n\times(n-1)!$ avec $0!=1$. La version itérative accumule le produit dans une boucle. Les deux calculent la même chose ; la récursive est plus proche de la définition mathématique, l'itérative consomme une mémoire constante. Contrôle : $5!=120$ et $10!=3\,628\,800$ dans les deux cas.

b) (1) Il faut un CAS DE BASE, c'est-à-dire au moins une valeur pour laquelle la fonction répond sans se rappeler. (2) Il faut que chaque appel récursif porte sur un argument STRICTEMENT PLUS PETIT, et qui finisse par atteindre le cas de base. Violation de la première : une fonction qui s'écrit uniquement $f(n)=f(n-1)$ ne s'arrête jamais. Violation de la seconde : $f(n)=f(n)+1$, ou plus insidieusement $f(n)=f(n-2)$ appelée sur un nombre impair alors que le cas de base est $f(0)$, qui manque toujours sa cible d'une unité.

c) La version naïve traduit la relation $F_{n}=F_{n-1}+F_{n-2}$ avec deux cas de base. Elle est correcte mais catastrophiquement lente, pour la raison examinée à l'exercice 7 : elle recalcule indéfiniment les mêmes valeurs.

d) Avec un argument négatif, le cas de base $n=0$ n'est jamais atteint : les appels descendent vers $-1$, $-2$, et ainsi de suite, sans fin. Python finit par lever une erreur de dépassement de la profondeur maximale de récursion. CORRECTION : ajouter une garde au début de la fonction qui rejette les entrées négatives, par exemple en levant une exception. C'est l'illustration exacte de la seconde condition de la question b : l'argument décroît bien, mais il ne rencontre jamais le cas de base.

e) La PILE D'APPELS est la zone de mémoire où l'interpréteur conserve, pour chaque appel en cours, les variables locales et l'endroit où revenir une fois le calcul terminé. Une récursion de profondeur $n$ y empile $n$ enregistrements simultanés. Python fixe par défaut une limite d'environ mille appels imbriqués, non par manque de mémoire mais comme GARDE-FOU : elle transforme une récursion infinie, qui ferait planter le processus de façon opaque, en une exception lisible. On peut relever cette limite, mais c'est presque toujours le signe qu'il fallait écrire une boucle.

a) L'arbre compte 15 nœuds, donc 15 appels au total. La valeur $\mathrm{fib}(2)$ y apparaît TROIS fois, et $\mathrm{fib}(1)$ cinq fois. Ces recalculs ne sont pas un défaut de programmation : ils sont inscrits dans la structure de l'arbre, où deux branches issues d'un même nœud redescendent vers des sous-problèmes qui se recouvrent.

b) Un appel à $\mathrm{fib}(n)$ compte pour lui-même, plus tous les appels de ses deux sous-arbres : $C(n)=1+C(n-1)+C(n-2)$ pour $n\geq 2$, avec $C(0)=C(1)=1$. Calculs : $C(2)=1+1+1=3$ ; $C(3)=1+3+1=5$ ; $C(4)=1+5+3=9$ ; $C(5)=1+9+5=15$, ce qui confirme la figure ; $C(6)=1+15+9=25$.

c) Par récurrence à deux crans. INITIALISATIONS : $2F_{1}-1=2\times 1-1=1=C(0)$ ✓ et $2F_{2}-1=2\times 1-1=1=C(1)$ ✓. HÉRÉDITÉ : en supposant la formule aux rangs $k$ et $k+1$, on a $C(k+2)=1+C(k+1)+C(k)=1+\left(2F_{k+2}-1\right)+\left(2F_{k+1}-1\right)=2\left(F_{k+2}+F_{k+1}\right)-1=2F_{k+3}-1$ ✓. Contrôle : $C(5)=2F_{6}-1=2\times 8-1=15$ ✓.

d) $C(30)=2F_{31}-1=2\times 1\,346\,269-1=2\,692\,537$ appels, soit environ 2,7 millions. À un million d'appels par seconde, cela prend environ $2{,}7$ secondes pour un calcul dont le résultat, $F_{30}=832\,040$, tient sur six chiffres. En $n=50$ il faudrait plus de neuf heures, et en $n=80$ plus de quarante mille ans : la croissance est en $\varphi^{n}$, où $\varphi\approx 1{,}618$ est le nombre d'or.

e) Avec mémoïsation, chaque valeur de $\mathrm{fib}(k)$ n'est calculée qu'UNE fois, pour $k$ allant de 0 à $n$ : le nombre d'appels effectifs devient linéaire, de l'ordre de $2n+1$. Pour $n=30$, cela fait 61 appels au lieu de 2,7 millions, un gain d'un facteur 44 000. La leçon dépasse Fibonacci : dès que les sous-problèmes se RECOUVRENT, mémoriser les résultats transforme un coût exponentiel en coût linéaire. C'est le principe de la programmation dynamique.

a) En reportant $u_{n}=r^{n}$ dans la relation : $r^{n+2}=r^{n+1}+r^{n}$, et en divisant par $r^{n}$ non nul, $r^{2}=r+1$, soit $r^{2}-r-1=0$. Le discriminant vaut $1+4=5$, donc les deux racines sont $\varphi=\frac{1+\sqrt 5}{2}\approx 1{,}618034$ et $\psi=\frac{1-\sqrt 5}{2}\approx-0{,}618034$. Cette équation s'appelle l'équation caractéristique de la récurrence.

b) Comme la relation est LINÉAIRE, toute combinaison $u_{n}=A\varphi^{n}+B\psi^{n}$ la vérifie encore, et l'on montre qu'il n'y en a pas d'autres. Les deux conditions initiales fixent $A$ et $B$ : $F_{0}=0$ donne $A+B=0$, donc $B=-A$ ; $F_{1}=1$ donne $A\varphi-A\psi=A\sqrt 5=1$, donc $A=\frac{1}{\sqrt 5}$. D'où la FORMULE DE BINET : $F_{n}=\frac{\varphi^{n}-\psi^{n}}{\sqrt 5}$. Fait remarquable, cette expression pleine de racines carrées donne un entier pour chaque $n$.

c) $\varphi^{10}\approx 122{,}9919$ et $\psi^{10}\approx 0{,}0081$, donc $\frac{122{,}9919-0{,}0081}{2{,}2360680}\approx\frac{122{,}9837}{2{,}2360680}\approx 55{,}0000$ ✓, ce qui est bien $F_{10}=55$. Le calcul direct par la relation donne la même valeur, comme il se doit.

d) Le second terme $\frac{\psi^{n}}{\sqrt 5}$ a pour module $\frac{0{,}618034^{n}}{2{,}236}$, qui est inférieur à $\frac{1}{2}$ dès $n=1$ et tend très vite vers 0. L'écart entre $F_{n}$ et $\frac{\varphi^{n}}{\sqrt 5}$ est donc toujours inférieur à un demi, ce qui signifie exactement que $F_{n}$ est l'entier le plus proche. Vérification en $n=10$ : $\frac{122{,}9919}{2{,}2360680}\approx 55{,}0036$, dont l'entier le plus proche est bien 55. C'est cette domination d'une racine sur l'autre qui explique aussi la croissance en $\varphi^{n}$ observée à l'exercice 5.

e) Équation caractéristique : $r^{2}=3r-2$, soit $r^{2}-3r+2=0$, de racines $r=1$ et $r=2$. Forme générale : $u_{n}=A\times 1^{n}+B\times 2^{n}=A+B2^{n}$. Conditions initiales : $u_{0}=A+B=1$ et $u_{1}=A+2B=3$. En soustrayant, $B=2$, puis $A=-1$. Donc $u_{n}=2^{n+1}-1$. Contrôle : $u_{0}=1$, $u_{1}=3$, $u_{2}=7$, $u_{3}=15$ ✓, ce qui confirme la conjecture formulée à l'exercice 3. Le procédé est identique, seules les racines changent.

a) On compare la valeur cherchée à l'élément du MILIEU. Si elle est égale, c'est fini. Si elle est plus petite, on recommence dans la moitié gauche ; sinon dans la moitié droite. À chaque tour, l'intervalle de recherche est divisé par deux, comme le montre la figure : 16 cases, puis 8, puis 4, puis 2, puis 1. La condition indispensable est que le tableau soit TRIÉ, sans quoi la comparaison au milieu n'apprend rien sur les deux moitiés.

b) $T(n)=T\left(\frac{n}{2}\right)+1$, avec $T(1)=1$ : une comparaison au milieu, puis le même problème sur une moitié. En déroulant : $T(n)=1+1+\dots+1$ autant de fois qu'on peut diviser $n$ par 2 avant d'atteindre 1, c'est-à-dire $\log_{2}n$ fois. Donc $T(n)\approx\log_{2}n+1$, un coût LOGARITHMIQUE.

c) $\log_{2}\left(10^{6}\right)=\frac{6\ln 10}{\ln 2}\approx 19{,}93$, donc 20 comparaisons suffisent. La recherche séquentielle en demanderait jusqu'à un million, soit 50 000 fois plus. Autrement dit, doubler la taille du tableau ajoute UNE comparaison à la dichotomie et un million à la recherche séquentielle : c'est la différence de nature entre logarithmique et linéaire.

d) Parce que ses deux sous-problèmes ne sont jamais explorés tous les deux : on en CHOISIT un et l'on abandonne l'autre. L'arbre d'appels de Fibonacci se ramifie en deux à chaque nœud, d'où sa taille exponentielle ; celui de la dichotomie est un simple CHEMIN de longueur $\log_{2}n$. Ce n'est donc pas la récursivité qui coûte cher, c'est la ramification avec recouvrement.

e) Le coût est $n\log_{2}n$. Argument d'arbre : l'arbre des appels a $\log_{2}n$ niveaux, puisque la taille est divisée par deux à chaque descente. À CHAQUE niveau, la fusion traite au total $n$ éléments, répartis entre les appels de ce niveau : $n$ en haut, deux fois $\frac{n}{2}$ au niveau suivant, quatre fois $\frac{n}{4}$ ensuite, toujours $n$ au total. Le coût global est donc le nombre de niveaux multiplié par le travail par niveau, soit $n\log_{2}n$. Pour un million d'éléments, cela fait environ 20 millions d'opérations, contre $10^{12}$ pour un tri par sélection : c'est la raison pour laquelle tous les tris utilisés en pratique sont récursifs.

1) FAUX. Il manque l'INITIALISATION, et sans elle l'hérédité ne prouve rien. La propriété « $n=n+1$ » a une hérédité parfaitement valide, puisque $k=k+1$ entraîne $k+1=k+2$, et elle est pourtant fausse à tous les rangs. L'hérédité établit une chaîne d'implications ; encore faut-il que quelque chose la déclenche.

2) FAUX. Cent vérifications ne valent pas une démonstration, et l'exemple d'Euler le montre : $n^{2}+n+41$ est premier pour $n$ de 0 à 39 et cesse de l'être en $n=40$, où l'on obtient $1681=41^{2}$. Il existe des propriétés dont le premier contre-exemple dépasse le milliard. Le rôle de l'hérédité est justement de remplacer une infinité de vérifications, ce qu'aucun nombre fini d'essais ne peut faire.

3) FAUX, et c'est le malentendu le plus tenace du chapitre. On ne suppose PAS que $P(k)$ est vraie : on démontre l'IMPLICATION « si $P(k)$ alors $P(k+1)$ ». Une implication peut être vraie alors que son hypothèse est fausse, et l'on n'a donc rien affirmé sur $P(k)$. Ce que l'on démontre, c'est un mécanisme de transmission ; l'initialisation, elle, fournit un point de départ vrai, et la conjonction des deux donne la conclusion.

4) FAUX. La récursivité n'est pas coûteuse en soi : c'est la RAMIFICATION AVEC RECOUVREMENT qui l'est. La recherche dichotomique récursive coûte $\log_{2}n$ comparaisons, exactement comme sa version itérative ; le tri fusion récursif en $n\log_{2}n$ bat tout tri quadratique itératif. Ce qui rend $\mathrm{fib}$ naïve désastreuse, c'est qu'elle recalcule les mêmes valeurs, et la mémoïsation la ramène à un coût linéaire sans lui retirer sa récursivité.

5) FAUX. La relation $F_{n+2}=F_{n+1}+F_{n}$ fait intervenir DEUX rangs antérieurs, il faut donc DEUX initialisations, aux rangs 0 et 1. Avec une seule, on ne peut même pas calculer $F_{2}$. Règle générale : le nombre d'initialisations doit être égal au nombre de rangs antérieurs dont dépend la relation.

a) RÈGLES : on déplace un seul disque à la fois, en le prenant au sommet d'un piquet, et l'on ne pose jamais un disque sur un plus petit. STRATÉGIE : pour déplacer $n$ disques de A vers C, on déplace d'abord les $n-1$ disques du dessus de A vers B, en utilisant C comme intermédiaire ; on déplace ensuite le grand disque de A vers C, seul mouvement direct ; on déplace enfin les $n-1$ disques de B vers C en utilisant A. Le cas de base est $n=1$, où l'on déplace le disque unique.

b) La stratégie donne directement $H(n)=2H(n-1)+1$ avec $H(1)=1$. Calculs : $H(2)=3$ ; $H(3)=7$ ; $H(4)=15$, ce qu'annonce la figure ; $H(5)=31$. On reconnaît la suite $2^{n}-1$, ce que la question suivante démontre.

c) INITIALISATION : $H(1)=1=2^{1}-1$ ✓. HÉRÉDITÉ : supposons $H(k)=2^{k}-1$. Alors $H(k+1)=2H(k)+1=2\left(2^{k}-1\right)+1=2^{k+1}-2+1=2^{k+1}-1$ ✓. La formule est donc établie pour tout $n\geq 1$. Remarquez que la démonstration reprend exactement la structure de l'algorithme : c'est le propre des problèmes récursifs, la preuve et le programme se ressemblent.

d) $H(64)=2^{64}-1=18\,446\,744\,073\,709\,551\,615$ déplacements. À raison d'un par seconde, cela fait environ $5{,}85\times 10^{11}$ années, soit près de 585 milliards d'années. À titre de comparaison, l'âge de l'Univers est estimé à environ 13,8 milliards d'années : les moines de la légende auraient donc besoin d'une durée quarante fois supérieure. C'est le meilleur argument pédagogique qui soit contre l'idée qu'un ordinateur plus rapide résout tout.

e) NON, on ne peut pas faire mieux : on démontre que $2^{n}-1$ est le nombre MINIMAL de déplacements, car le grand disque doit être déplacé au moins une fois, et pour cela les $n-1$ autres doivent tous être empilés ailleurs. Le coût exponentiel n'est donc pas la faute de l'algorithme récursif, il est dans le PROBLÈME lui-même. C'est la distinction fondamentale avec Fibonacci naïf, dont le coût exponentiel venait de la méthode et disparaissait par mémoïsation. Avant d'optimiser un programme lent, il faut donc se demander lequel des deux cas on a sous les yeux.