Mathématiques pour l'informatique 201-N11 • Cégep à Montréal

Fiche de révision : récurrence et récursivité (201-N11)

La récurrence est le premier raisonnement du cours où la RÉDACTION vaut autant que l'idée : deux étapes, deux phrases types, et un point perdu chaque fois que l'une des deux manque. Cette fiche traite ces phrases, puis leur contrepartie algorithmique, le coût d'une fonction récursive.

Elle est écrite pour les étudiants de cégep en techniques de l'informatique à Montréal et pour tous ceux qui abordent l'algorithmique par les mathématiques. La série d'exercices corrigés du même chapitre met ensuite chaque réflexe à l'épreuve.

Marque ici la fiche comme lue ou mets-la en favori : un compte gratuit, sans mot de passe, retient tes fiches lues et tes favoris d'une visite à l'autre, te dit quel chapitre attaquer ensuite et te permet de demander la méthode ou l'exercice qui te manque. Crée ton espace, un courriel suffit.

Le fil du chapitre

L'hérédité est une IMPLICATION à démontrer, pas une propriété à supposer vraie. Les points se perdent en écrivant « supposons la propriété vraie pour tout $n$ », qui suppose déjà le résultat, et en oubliant l'initialisation, qui est la seule chose qui rattache la chaîne au sol.

Ce chapitre fait partie de Mathématiques pour l'informatique, 201-N11

Pour s'entraîner Les exercices corrigés de ce chapitre, 10 exercices

Avant ce chapitre

Cette fiche suppose ces notions acquises. Si une méthode ci-dessous reste opaque, c'est presque toujours l'une d'elles qui manque, pas la fiche.

Théorie des ensembles et relations Exercices

Remonter plus loin : la chaîne complète (2 chapitres) ↓

Le chemin de remédiation, du plus ancien au plus proche. Un élève qui reprend ce chapitre de zéro le reprend dans cet ordre.

L'essentiel

Deux étapes, et l'hérédité est une IMPLICATION

• INITIALISATION : $P(n_{0})$ est vraie, vérifiée par le calcul, pas affirmée.
• HÉRÉDITÉ : pour tout $k\geq n_{0}$ , $P(k)$ ENTRAÎNE $P(k+1)$ . On fixe $k$ , on suppose $P(k)$ , on démontre $P(k+1)$ .
• Conclusion : $P(n)$ est vraie pour tout $n\geq n_{0}$ .
• On ne suppose JAMAIS que $P(k)$ est vraie pour tout $k$ : ce serait supposer exactement ce que l'on veut démontrer.

L'initialisation fait tomber le premier domino ; l'hérédité garantit que chaque domino qui tombe fait tomber le suivant. Les deux ensemble font tomber toute la file.

La phrase d'hérédité correcte est : « Soit $k\geq n_{0}$ un entier tel que $P(k)$ soit vraie. Montrons que $P(k+1)$ l'est aussi. » Elle se recopie telle quelle, et elle vaut un point à chaque copie.

Les deux échecs types, chacun tuant une étape

• HÉRÉDITÉ SANS INITIALISATION : la propriété « $n=n+1$ » est héréditaire, puisque $k=k+1$ entraîne $k+1=k+2$ . Elle est pourtant fausse partout, faute d'un rang de départ.
• VÉRIFICATIONS SANS HÉRÉDITÉ : $n^{2}+n+41$ est premier pour $n$ de $0$ à $39$ , et vaut $41^{2}$ en $n=40$ . Quarante cas ne démontrent rien.
• Ces deux échecs disent la même chose : chacune des deux étapes est nécessaire, aucune n'est suffisante.
• En examen, l'initialisation oubliée est la faute la plus fréquente, et c'est la plus facile à éviter : deux lignes de calcul.

À gauche, la chaîne est parfaite mais personne ne pousse : rien ne tombe. À droite, on a poussé, mais la chaîne casse au rang

40

: les vérifications ne suffisent pas.

Une récurrence à DEUX CRANS demande DEUX initialisations, et une récurrence forte se contente d'une seule quand le cas de base est unique : le nombre d'initialisations est celui des rangs antérieurs utilisés.

De la suite récurrente à la fonction récursive

• Une fonction récursive TERMINE si elle possède un CAS DE BASE et si chaque appel porte sur un argument strictement plus petit qui finit par l'atteindre.
• La PILE D'APPELS conserve un enregistrement par appel en cours : d'où la limite d'environ mille appels imbriqués en Python.
• Coûts usuels : $T(n)=T\left(\frac{n}{2}\right)+1$ donne $\log_{2}n$ , la dichotomie. $T(n)=2T\left(\frac{n}{2}\right)+n$ donne $n\log_{2}n$ , le tri fusion.
• $T(n)=2T(n-1)+1$ donne $2^{n}-1$ , les tours de Hanoï. $T(n)=T(n-1)+T(n-2)+1$ donne $2F_{n+1}-1$ , la version naïve de Fibonacci.

Les quatre coûts du chapitre à la même échelle :

\log_{2}n

reste plat,

n

monte doucement,

n\log_{2}n

la suit de près, et

2^{n}

sort déjà du cadre avant

n=7

Récurrence linéaire à deux crans : l'équation caractéristique

• Pour $u_{n+2}=au_{n+1}+bu_{n}$ , on résout $r^{2}=ar+b$ , dite équation caractéristique.
• Deux racines distinctes $r_{1}$ et $r_{2}$ : $u_{n}=Ar_{1}^{n}+Br_{2}^{n}$ , les DEUX conditions initiales fixant $A$ et $B$ .
• Racine double $r$ : $u_{n}=(A+Bn)r^{n}$ .
• Sur $u_{n+2}=u_{n+1}+u_{n}$ , cela donne la formule de Binet pour Fibonacci, avec le nombre d'or comme racine.

Les termes de Fibonacci (points) suivent la courbe

\frac{\varphi^{n}}{\sqrt{5}}

: le terme en

r_{2}^{n}

de la formule de Binet s'éteint, et

F_{n}

en est l'arrondi.

Le système en $A$ et $B$ se résout avec $u_{0}$ ET $u_{1}$ . Une seule condition laisse une famille de solutions, et rendre l'une d'elles au hasard coûte la moitié de la question.

Les pièges qui coûtent des points

Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.

1. Supposer la propriété vraie pour tout $n$

1 à 2 points, à chaque récurrence de la copie

Ce qu'il ne faut pas écrire

« Supposons que $P(n)$ soit vraie pour tout $n$ , et montrons $P(n+1)$ . »

Ce qu'il faut écrire

« Soit $k\geq n_{0}$ un entier tel que $P(k)$ soit vraie. Montrons que $P(k+1)$ l'est aussi. »

Pourquoi : Supposer la propriété vraie pour tout $n$ , c'est supposer le résultat : la démonstration ne démontre plus rien. On fixe UN rang, on suppose la propriété à ce rang seulement.

2. Sauter l'initialisation parce qu'elle est évidente

toute la démonstration, l'hérédité seule ne prouvant rien

Ce qu'il ne faut pas écrire

« L'hérédité est établie, donc la propriété est vraie pour tout $n$ . »

Ce qu'il faut écrire

« Initialisation : $P(1)$ se vérifie par le calcul. Hérédité : ... Conclusion : par récurrence, $P(n)$ est vraie pour tout $n\geq 1$ . »

Pourquoi : La propriété « $n=n+1$ » est parfaitement héréditaire et fausse partout. Sans un rang où la chaîne touche le sol, l'hérédité fait tomber des dominos qui n'existent pas.

3. Prendre des vérifications pour une démonstration

toute la question

Ce qu'il ne faut pas écrire

« $n^{2}+n+41$ est premier pour $n=0$ , $1$ , $2$ , ..., $10$ : la propriété est donc vraie. »

Ce qu'il faut écrire

« Aucun nombre de cas ne démontre une propriété sur $\mathbb{N}$ . Ici la formule est premier jusqu'à $n=39$ et vaut $41^{2}=1681$ en $n=40$ . »

Pourquoi : C'est le contre-exemple historique d'Euler, et il est choisi précisément parce que quarante cas semblent une preuve écrasante. Seule l'hérédité couvre l'infinité des rangs.

4. Une seule initialisation pour une relation à deux crans

2 points, et une hérédité qui ne peut pas démarrer

Ce qu'il ne faut pas écrire

« $u_{n+2}=u_{n+1}+2u_{n}$ : je vérifie $u_{0}$ , puis je fais l'hérédité. »

Ce qu'il faut écrire

« Il faut DEUX initialisations, $u_{0}$ et $u_{1}$ , autant que de rangs antérieurs dans la relation, et l'hérédité suppose $P(k)$ ET $P(k+1)$ . »

Chaque terme s'appuie sur les DEUX précédents (arcs gris) : pour lancer la chaîne, il faut pousser

u_{0}

u_{1}

Pourquoi : L'hérédité fait passer de deux rangs consécutifs au suivant : sans deux points de départ, elle n'a rien sur quoi s'appuyer. Le nombre d'initialisations est celui des rangs antérieurs utilisés.

5. Écrire une fonction récursive sans cas de base atteignable

toute la question de terminaison, et un programme qui plante

Ce qu'il ne faut pas écrire

« $f(n)$ appelle $f(n-2)$ , avec pour seul cas de base $f(0)=1$ . »

Ce qu'il faut écrire

« Pour $n$ impair, la suite des appels ne rencontre jamais $0$ : il faut un second cas de base, $f(1)$ , ou une décroissance vers $0$ garantie. »

f(n)

appelle

f(n-2)

: partant de

4

, on atteint le cas de base

0

; partant de

5

, les appels sautent

0

et descendent sans fin.

Pourquoi : La terminaison demande deux choses : un cas de base, et un argument qui décroît strictement JUSQU'À l'atteindre. Le premier sans le second produit un dépassement de pile, pas une erreur mathématique.

6. Croire qu'une récursion naïve de Fibonacci est linéaire

toute la question de complexité

Ce qu'il ne faut pas écrire

« $f(n)$ fait deux appels, donc environ $2n$ appels en tout. »

Ce qu'il faut écrire

« Le nombre d'appels vérifie $T(n)=T(n-1)+T(n-2)+1$ , donc $T(n)=2F_{n+1}-1$ : c'est EXPONENTIEL, et $f(40)$ demande déjà plus de trois cents millions d'appels. »

L'arbre des appels de

f(4)

recalcule

f(2)

deux fois et

f(1)

trois fois : les sous-problèmes SE RECOUVRENT, et c'est exactement ce que la mémoïsation supprime.

Pourquoi : Deux appels par niveau sur une profondeur $n$ font un arbre, pas une chaîne. C'est le nombre de FEUILLES qui compte, et il croît comme le nombre d'or à la puissance $n$ .

7. Croire que la mémoïsation accélère toute récursion

1 à 2 points, et une conclusion algorithmique fausse

Ce qu'il ne faut pas écrire

« Hanoï est exponentiel, je vais donc le mémoïser. »

Ce qu'il faut écrire

« La mémoïsation ne sert que si les sous-problèmes SE RECOUVRENT. Dans Hanoï, chaque déplacement est distinct : les $2^{n}-1$ coups sont le coût intrinsèque du problème et rien ne l'améliorera. »

Pourquoi : La mémoïsation supprime les RECALCULS, pas le travail. Fibonacci naïf recalcule les mêmes valeurs, Hanoï produit une sortie de longueur $2^{n}-1$ qu'aucune astuce ne raccourcira.

8. Confondre le nombre d'appels et la profondeur de la pile

1 à 2 points, et un diagnostic faux

Ce qu'il ne faut pas écrire

« La récursion de Fibonacci fait des millions d'appels, donc la pile déborde. »

Ce qu'il faut écrire

« La PROFONDEUR de la pile vaut $n$ , pas le nombre total d'appels : les appels se succèdent, ils ne coexistent pas tous. C'est une récursion terminale sur $n$ très grand qui fait déborder la pile. »

\mathrm{fib}(4)

fait

9

appels, mais la pile n'en contient jamais plus que la branche en cours (bleu) : sa profondeur est

4

Pourquoi : La pile ne contient que les appels EN COURS. Un arbre de trois cents millions de nœuds n'a qu'une quarantaine de niveaux, alors qu'une simple boucle récursive sur $10^{6}$ déborde en Python dès mille appels.

Quelle méthode choisir

Quelle forme de récurrence selon la propriété

On regarde de quels rangs antérieurs le rang $n$ dépend. C'est cela, et rien d'autre, qui fixe le nombre d'initialisations et la forme de l'hypothèse.

Si $P(k)$ suffit à obtenir $P(k+1)$ → récurrence simple, une initialisation

Exemple : $\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$
Si la relation fait intervenir $u_{n+1}$ ET $u_{n}$ → récurrence à deux crans, DEUX initialisations, hypothèse portant sur deux rangs consécutifs

Exemple : $u_{n+2}=u_{n+1}+2u_{n}$
Si on décompose l'objet en morceaux de tailles INCONNUES → récurrence FORTE : l'hypothèse porte sur tous les rangs de $n_{0}$ à $k$

Exemple : tout entier supérieur à $1$ admet un diviseur premier

C'est le cas typique en informatique : une liste coupée en deux morceaux de tailles quelconques oblige à supposer la propriété pour toutes les tailles inférieures.
Si la propriété est une INÉGALITÉ → même schéma, mais on part du membre de gauche et l'on majore, sans jamais partir de l'inégalité à démontrer

Exemple : $2^{n}\geq n^{2}$ pour $n\geq 4$
Si la propriété est une DIVISIBILITÉ → écrire l'hypothèse sous la forme $u_{k}=m\times q$ , puis faire apparaître le facteur $m$ dans $u_{k+1}$

Exemple : $7^{n}-1$ est divisible par $6$

Dans tous les cas, la conclusion se rédige : « Par récurrence, $P(n)$ est vraie pour tout $n\geq n_{0}$ . » Elle vaut un point et elle est omise dans une copie sur trois.

Quel coût selon la forme de la relation de récurrence

On lit la relation $T(n)$ et l'on cherche deux choses : de combien l'argument diminue, et combien d'appels sont lancés à chaque niveau.

Chaque étape de la dichotomie divise la zone de recherche par DEUX : quatre étapes suffisent pour

16

cases, ce qui est exactement

\log_{2}16

. C'est la forme

T(n)=T\left(\frac{n}{2}\right)+1

Si $T(n)=T\left(\frac{n}{2}\right)+1$ → $\log_{2}n$ , coût logarithmique

Exemple : recherche dichotomique dans un tableau trié
Si $T(n)=2T\left(\frac{n}{2}\right)+n$ → $n\log_{2}n$

Exemple : tri fusion, tri rapide en moyenne
Si $T(n)=T(n-1)+1$ → $n$ , coût linéaire

Exemple : somme récursive des éléments d'une liste
Si $T(n)=2T(n-1)+1$ → $2^{n}-1$ , coût exponentiel INTRINSÈQUE

Exemple : tours de Hanoï

Ici la sortie elle-même a une longueur exponentielle : aucune optimisation ne peut faire mieux, et la mémoïsation ne sert à rien.
Si $T(n)=T(n-1)+T(n-2)+1$ → $2F_{n+1}-1$ , exponentiel ÉVITABLE

Exemple : Fibonacci naïf, ramené à un coût linéaire par mémoïsation

La question à se poser devant un coût exponentiel est toujours la même : les sous-problèmes se RECOUVRENT-ils ? Si oui, la mémoïsation ramène au nombre de sous-problèmes distincts; si non, le coût est celui du problème.

La rédaction attendue

Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.

Rédiger une récurrence pour le correcteur

Quand l'utiliser : Toute propriété à démontrer pour tout entier $n$ supérieur ou égal à un certain rang.

1 Énoncer la propriété avec son rang : « Pour $n\geq 1$ , notons $P(n)$ : $\sum_{i=1}^{n}i^{3}=\left(\frac{n(n+1)}{2}\right)^{2}$ . »
2 INITIALISATION, par le calcul des deux membres : « $P(1)$ : à gauche $1^{3}=1$ , à droite $\left(\frac{1\times 2}{2}\right)^{2}=1$ . $P(1)$ est vraie. »
3 HÉRÉDITÉ, en fixant le rang : « Soit $k\geq 1$ tel que $P(k)$ soit vraie. Montrons $P(k+1)$ . »
4 Partir du membre de GAUCHE au rang $k+1$ , isoler le terme nouveau, remplacer par l'hypothèse, puis transformer jusqu'au membre de droite attendu.
5 CONCLUSION, nommée : « Par récurrence, $P(n)$ est vraie pour tout $n\geq 1$ . »

Phrase de conclusion

Par récurrence, pour tout entier $n\geq 1$ , $\sum_{i=1}^{n}i^{3}=\left(\frac{n(n+1)}{2}\right)^{2}$ .

Le piège : Partir de l'égalité à démontrer et la transformer des deux côtés jusqu'à obtenir une identité vraie. C'est un raisonnement à l'envers : le correcteur attend un calcul qui PART du membre de gauche et ARRIVE au membre de droite.

Barème : En général 1 point pour l'initialisation calculée, 1 point pour la phrase d'hérédité correctement quantifiée, 2 points pour le calcul, 1 point pour la conclusion.

Résoudre une récurrence linéaire à deux crans

Quand l'utiliser : L'énoncé donne $u_{n+2}=au_{n+1}+bu_{n}$ avec $u_{0}$ et $u_{1}$ , et demande une expression de $u_{n}$ .

1 Écrire l'équation caractéristique : « $u_{n+2}=u_{n+1}+2u_{n}$ donne $r^{2}=r+2$ , soit $r^{2}-r-2=0$ . »
2 Résoudre et annoncer le cas : « Les racines sont $r_{1}=2$ et $r_{2}=-1$ , distinctes. »
3 Écrire la forme générale : « Il existe $A$ et $B$ tels que $u_{n}=A\times 2^{n}+B\times(-1)^{n}$ . »
4 Utiliser les DEUX conditions initiales pour former un système : « $u_{0}=A+B=1$ et $u_{1}=2A-B=8$ . »
5 Résoudre, écrire l'expression, puis VÉRIFIER sur un troisième rang calculé des deux façons.

Phrase de conclusion

Pour tout $n\geq 0$ , $u_{n}=3\times 2^{n}-2\times(-1)^{n}$ .

Le piège : Utiliser une seule condition initiale et fixer l'autre constante au hasard. Le système à deux inconnues exige deux équations, et une seule laisse une famille entière de suites solutions.

Barème : 1 point pour l'équation caractéristique, 1 point pour les racines, 1 point pour le système, 1 point pour l'expression finale vérifiée.

Vérifier avant de rendre

Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.

Tester la formule sur les trois premiers rangs

Calculer les deux membres pour $n_{0}$ , $n_{0}+1$ et $n_{0}+2$ . Une formule fausse le devient presque toujours dès le deuxième ou le troisième rang.

Sur $\sum i^{3}$ : $1$ , puis $1+8=9=3^{2}$ , puis $9+27=36=6^{2}$ . Les carrés $1$ , $9$ , $36$ confirment la formule avant même de commencer la récurrence.
Vérifier que l'hérédité utilise vraiment l'hypothèse

Relire le calcul d'hérédité et repérer l'endroit exact où $P(k)$ a servi. Si l'hypothèse n'est jamais utilisée, c'est que la propriété se démontre directement, et la récurrence est un détour.

Dans le calcul de $\sum_{i=1}^{k+1}i^{3}$ , l'hypothèse sert au moment où la somme des $k$ premiers cubes est remplacée par $\left(\frac{k(k+1)}{2}\right)^{2}$ . Sans cette substitution, il n'y a pas de récurrence.
Compter les initialisations

Autant d'initialisations que de rangs antérieurs dans la relation. Une relation à deux crans en demande deux, une récurrence simple une seule.

$u_{n+2}=u_{n+1}+2u_{n}$ demande $u_{0}$ et $u_{1}$ . Une seule initialisation laisserait passer, par exemple, toute suite de la forme $A\times 2^{n}$ .
Vérifier un coût annoncé sur un petit cas

Dérouler l'algorithme à la main pour $n=3$ ou $n=4$ et compter les opérations. Le nombre obtenu doit coïncider avec la formule.

Hanoï avec trois disques demande sept déplacements, et $2^{3}-1=7$ . Un comptage à huit signale une décomposition mal écrite.

L'exercice type décortiqué

Les tours de Hanoï : démontrer $2^{n}-1$ déplacements

On dispose de trois piquets et de $n$ disques de tailles différentes, empilés du plus grand au plus petit sur le premier piquet.

On déplace un disque à la fois et l'on ne pose jamais un disque sur un plus petit.

Démontrer par récurrence que le déplacement de la pile entière demande exactement $2^{n}-1$ déplacements.

Trois piquets, une pile de disques du plus grand au plus petit : on déplace un disque à la fois, jamais sur un plus petit.

Étape 1

Pour $n\geq 1$ , notons $P(n)$ la propriété : « déplacer une pile de $n$ disques demande exactement $2^{n}-1$ déplacements ».

Pourquoi

On nomme la propriété et son rang de départ AVANT tout calcul. Une récurrence sans propriété nommée est impossible à corriger, et le correcteur ne peut pas suivre à quel rang s'applique chaque affirmation.

Étape 2

INITIALISATION. Pour $n=1$ , un seul disque se déplace en un coup, et $2^{1}-1=1$ . Donc $P(1)$ est vraie.

Pourquoi

L'initialisation se CALCULE, elle ne s'affirme pas. Deux lignes, un point du barème, et c'est l'étape la plus souvent sautée du chapitre.

Étape 3

HÉRÉDITÉ. Soit $k\geq 1$ un entier tel que $P(k)$ soit vraie. Montrons que $P(k+1)$ l'est aussi.

Pourquoi

On fixe UN rang $k$ et l'on suppose la propriété à ce rang seulement. Écrire « pour tout $k$ » ici reviendrait à supposer le résultat, et la démonstration ne démontrerait plus rien.

Étape 4

Pour déplacer $k+1$ disques, on déplace les $k$ disques du dessus sur le piquet libre, ce qui demande $2^{k}-1$ coups par hypothèse de récurrence; on déplace le grand disque, soit $1$ coup; on redéplace les $k$ disques sur le grand, soit encore $2^{k}-1$ coups.

Pourquoi

C'est l'unique moment où l'hypothèse de récurrence sert, et elle sert DEUX fois. Le repérer permet de vérifier que la démonstration en est bien une, et non un calcul direct déguisé.

Étape 5

Total : $\left(2^{k}-1\right)+1+\left(2^{k}-1\right)=2\times 2^{k}-1=2^{k+1}-1$ . Donc $P(k+1)$ est vraie.

Pourquoi

Le calcul part de la décomposition et ARRIVE à la forme attendue. Partir de $2^{k+1}-1$ pour retomber sur la décomposition serait un raisonnement à l'envers, refusé par le correcteur.

Étape 6

CONCLUSION. Par récurrence, pour tout $n\geq 1$ , déplacer $n$ disques demande exactement $2^{n}-1$ déplacements.

Pourquoi

La phrase de conclusion nomme le principe utilisé et rappelle le domaine de validité. Elle vaut un point et manque dans une copie sur trois.

Étape 7

Contrôle : $n=3$ donne $2^{3}-1=7$ , ce qu'on retrouve en déroulant le jeu à la main; $n=4$ donne $15$ , et $n=10$ déjà $1023$ .

Pourquoi

Un petit cas déroulé à la main confirme la décomposition, et les grandes valeurs montrent que le coût est bien exponentiel : c'est souvent la question suivante de l'énoncé.

Conclusion rédigée

Par récurrence, le déplacement d'une pile de $n$ disques demande exactement $2^{n}-1$ déplacements, ce qui est aussi le nombre minimal : la décomposition utilisée est la seule possible.

L'erreur classique sur cet exercice : Écrire le total $2^{k}-1+1+2^{k}-1=2^{k+1}$ , en perdant le $-1$ . La formule obtenue donnerait $2$ déplacements pour un seul disque, ce que l'initialisation contredit immédiatement : le contrôle sur $n=1$ attrape cette faute en trois secondes.

À savoir par cœur

• Deux étapes : INITIALISATION calculée, puis HÉRÉDITÉ, qui est une implication.
• La phrase d'hérédité : « Soit $k\geq n_{0}$ tel que $P(k)$ soit vraie. Montrons $P(k+1)$ . »
• Autant d'initialisations que de rangs antérieurs dans la relation.
• Hérédité sans initialisation : « $n=n+1$ ». Cas vérifiés sans hérédité : $n^{2}+n+41$ .
• Une fonction récursive termine si elle a un cas de base ET un argument qui décroît jusqu'à l'atteindre.
• $T\left(\frac{n}{2}\right)+1$ donne $\log_{2}n$ ; $2T\left(\frac{n}{2}\right)+n$ donne $n\log_{2}n$ ; $2T(n-1)+1$ donne $2^{n}-1$ .
• La mémoïsation ne sert que si les sous-problèmes SE RECOUVRENT.
• Équation caractéristique $r^{2}=ar+b$ , puis $u_{n}=Ar_{1}^{n}+Br_{2}^{n}$ avec DEUX conditions initiales.

Questions fréquentes

Comment rédiger correctement l'hypothèse de récurrence ?

On fixe un rang et on suppose la propriété vraie à ce rang seulement : soit k supérieur ou égal au rang initial tel que la propriété au rang k soit vraie, montrons qu'elle l'est au rang k plus un. Écrire qu'on suppose la propriété vraie pour tout n reviendrait à supposer le résultat, et la démonstration ne démontrerait plus rien.

Pourquoi faut-il une initialisation si l'hérédité est démontrée ?

Parce que l'hérédité seule ne prouve rien. La propriété n égale n plus un est héréditaire et fausse partout : si elle était vraie à un rang, elle le serait au suivant, mais elle n'est vraie à aucun. L'initialisation est ce qui rattache la chaîne au sol, et sans elle aucun domino ne tombe.

Combien d'initialisations faut-il pour une suite à deux crans ?

Deux, autant que de rangs antérieurs utilisés dans la relation. Une suite définie par ses deux termes précédents a besoin de ses deux premiers termes pour démarrer, et l'hypothèse de récurrence doit porter sur deux rangs consécutifs. Une seule initialisation laisserait passer d'autres suites que celle de l'énoncé.

Quand la mémoïsation accélère-t-elle une fonction récursive ?

Seulement quand les sous-problèmes se recouvrent, c'est à dire quand la fonction recalcule plusieurs fois les mêmes valeurs. C'est le cas de Fibonacci naïf, qui passe d'un coût exponentiel à un coût linéaire. Ce n'est pas le cas des tours de Hanoï, où chaque déplacement est distinct et où le coût exponentiel est celui du problème.

Quelle est la différence entre le nombre d'appels et la profondeur de la pile ?

La pile ne contient que les appels en cours, donc sa profondeur est la longueur de la plus longue chaîne d'appels imbriqués. L'arbre d'appels de Fibonacci compte des millions de nœuds mais seulement une quarantaine de niveaux. À l'inverse, une simple récursion linéaire sur un million d'éléments dépasse la limite de mille appels imbriqués de Python.

Passer à la pratique

Exercices corrigés : Récurrence et récursivité

Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.

10 exercices corrigés
100 points
150 minutes

Faire les exercices

Il manque quelque chose dans cette fiche ? Une méthode, un piège, un exercice pour l'appliquer, une erreur repérée : dis-le-moi, je lis chaque demande.

L'envoi passe par ton espace gratuit : c'est ce qui me permet de te répondre et de te prévenir quand l'exercice est ajouté. Un courriel suffit, pas de mot de passe. Crée ton espace. Pas envie de créer un compte ? Écris-moi directement.

Fiche précédente Fonctions injectives, surjectives, bijectives Fiche suivante Introduction aux graphes et aux matrices

© Ahmed Squalli Houssaini. Fiche publiée sur www.letuteurscientifique.ca/fiches/n11-recurrence-recursivite. Libre pour l'usage personnel et en classe ; sa republication ailleurs demande une autorisation écrite (mentions légales).

Voir aussi

Toutes les fiches Tous les exercices Dénombrement et probabilités (201-N11)Examen de synthèse (201-N11)Maths et informatique au cégep Tutorat au cégep

Vous cherchez un tuteur en mathématiques pour l'informatique 201-N11 à Montréal ?

Contactez-moi pour une première séance. On travaille la récurrence et la récursivité au niveau réel des évaluations, de la rédaction d'une hérédité jusqu'à l'analyse du coût d'un algorithme.

Me contacter WhatsApp

Site par Studio Squalli

Fiche de révision : récurrence et récursivité (201-N11)

L'essentiel

Deux étapes, et l'hérédité est une IMPLICATION

Les deux échecs types, chacun tuant une étape

De la suite récurrente à la fonction récursive

Récurrence linéaire à deux crans : l'équation caractéristique

Les pièges qui coûtent des points

1. Supposer la propriété vraie pour tout nnn

2. Sauter l'initialisation parce qu'elle est évidente

3. Prendre des vérifications pour une démonstration

4. Une seule initialisation pour une relation à deux crans

5. Écrire une fonction récursive sans cas de base atteignable

6. Croire qu'une récursion naïve de Fibonacci est linéaire

7. Croire que la mémoïsation accélère toute récursion

8. Confondre le nombre d'appels et la profondeur de la pile

Quelle méthode choisir

Quelle forme de récurrence selon la propriété

Quel coût selon la forme de la relation de récurrence

La rédaction attendue

Rédiger une récurrence pour le correcteur

Résoudre une récurrence linéaire à deux crans

Vérifier avant de rendre

L'exercice type décortiqué

Les tours de Hanoï : démontrer 2n−12^{n}-12n−1 déplacements

À savoir par cœur

Questions fréquentes

Comment rédiger correctement l'hypothèse de récurrence ?

Pourquoi faut-il une initialisation si l'hérédité est démontrée ?

Combien d'initialisations faut-il pour une suite à deux crans ?

Quand la mémoïsation accélère-t-elle une fonction récursive ?

Quelle est la différence entre le nombre d'appels et la profondeur de la pile ?

Exercices corrigés : Récurrence et récursivité

Voir aussi

Vous cherchez un tuteur en mathématiques pour l'informatique 201-N11 à Montréal ?

1. Supposer la propriété vraie pour tout $n$

Les tours de Hanoï : démontrer $2^{n}-1$ déplacements