Exercice
On définit la fonction récursive suivante due à McCarthy. Elle prend en entrée un entier $n$ et est définie par : \[f(n) = \begin{cases} n – 10 & \text{ si } n \gt 100 \\ f(f(n+11)) & \text{ sinon} \end{cases}\]
On considère l’algorithme qui calcule $f(n)$ en partant de la formule de récurrence. Montrer que cet algorithme termine et donner une valeur explicite de $f(n)$ pour tout entier $n$.
Correction
Nous savons que notre algorithme termine pour tout entrée supérieur à $101$, mais nous ignorons comment il se comporte pour des entrées plus petites. On doit donc effectuer une récurrence décroissante.
Montrons par induction que f l’algorithme calculant la fonction de McCarthy termine sur toute entrée entière $n$ et renvoie $n – 10$ si $n$ est supérieur ou égale à $101$ et renvoie $91$ sinon.
On initialise notre induction pour les cas de bases $n\gt100$. Dans ce cas, la fonction de McCarthy termine bien et renvoie ce que l’on souhaite.
On suppose maintenant la propriété vraie pour tout $n \gt k$ avec $ 0 \leq k\leq100$. Montrons qu’elle le reste au rang $k$.
Si $100\geq k\geq90$ : alors $f(k) = f(f(k+11))$. Or ici, $k+11 \gt 100$ et $f(k+11)$ termine et renvoie $k+1$. Donc $f(f(k+11)) = f(k+1)$. Par hypothèse d’induction, la fonction termine sur l’entrée $k+1$. De plus, si $k=100$ alors $f(k+1)=f(101)=91$ et si $k<100$, alors $f(k)=f(k+1)=91$. Donc la fonction de McCarthy termine sur l'entrée $k$ et renvoie $91$.
Si $90 \gt k$ : On a $f(k)=f(f(k+11))$. Or, par hypothèse d’induction, $f$ termine sur l’entrée $k+11$ et renvoie $91$. Donc $f(k)=f(91)$ qui termine et vaut $91$.
Cela achève notre induction et nous permet donc de conclure que l’algorithme calculant la fonction de McCarthy termine sur toute entrée entière $k$ et est définie par :
\[f(k) =\begin{cases} n – 10 & \text{ si } n \gt 100 \\ 91 & \text{ sinon} \end{cases}\]