\input{../.headers/cours.tex} \baselineskip15pt \begin{center} \shadowbox{\LARGE \bf \textsc{\supline R\'ecursivit\'e\subline}}\\ \end{center} \section{D\'efinition. Exemples.} \dfn On adopera la d\'efinition na\"\i ve suivante% de "fonction r\'ecursive" ~: une fonction r\'ecursive est une fonction qui s'appelle elle-m\^eme.\subline \nfd \exs Quelques exemples de fonctions qu'on peut d\'efinir de fa\c{c}on r\'ecursive~: \begin{minted}{ocaml} let rec fact n = match n with | 0 -> 1 | _ when n > 0 -> n * fact (n-1) let rec pgcd a b = match b with | 0 -> a | _ -> pgcd b (a mod b) let rec binomial n k = match (n, k) with | (_, 0) -> 1 | (0, _) -> 0 | _ -> binomial (n-1) k + binomial (n-1) (k-1) let rec fib n = match n with | 0 -> 0 | 1 -> 1 | _ -> fib (n-1) + fib (n-2) let rec valuation p n = match n with | 0 -> raise Division_by_zero | _ when n mod p = 0 -> 1 + valuation p (n/p) | _ -> 0 \end{minted} \sxe \section{R\'ecursivit\'e envelopp\'ee, r\'ecursivit\'e terminale, it\'eration} \medskip J'ai essay\'e d'insister sur le fait que Caml \'etait optimis\'e pour g\'erer efficacement la r\'ecursivit\'e, l\`a o\`u Python est surtout efficace pour l'it\'eration. Je vais maintenant essayer de montrer que l'opposition pertinente n'est pas \`a faire entre it\'eration et r\'ecursivit\'e mais plut\^ot entre r\'ecursivit\'e terminale et r\'ecursivit\'e envelopp\'ee. \medskip \subsection{It\'eration} \medskip L'it\'eration, c'est la r\'ep\'etition d'une suite d'instructions \`a l'aide d'une boucle. On dispose de deux type de boucles~: \begin{enumerate} \item les boucles {\bf conditionnelles}, qui sont les boucles \ocaml{while}~; \item et les boucles {\bf inconditionnelles}, qui sont les boucles \ocaml{for} \end{enumerate} \medskip \exx~~ On a vu avant les vacances de nombreuses fonctions pouvant s'\'ecrire avec des boucles~:\\ recherche dichotomique $\{$dans un tableau trié, de racine de fonctions$\}$, test de primalité, tri de tableau. Notons, et c'est important pour la suite, qu'on pouvait aussi les \'ecrire sans boucle. \xxe \medskip %\rmq Il n'y a pas de sortie de boucle anticip\'ee (return/break) en Caml. Mais on pourra les \'emuler en utilisant des exceptions. On y reviendra plus tard. %\qmr \exx~~ Un autre~?\\ fibonacci, pgcd, binomiaux, valuations p-adiques \xxe \subsection{R\'ecursivit\'e envelopp\'ee} %\rmq La plupart des fonctions r\'ecursives qu'on \'ecrit naturellement sont {\bf r\'ecursives envelopp\'ees}. \\[0.1cm] %L'appel r\'ecursif se fait {\it \`a l'int\'erieur} d'une fonction~: $\dsp{f(n)=\lect{\text{si n est un cas de base alors une valeur de base}\\ %\text{ sinon }g(n,f(m\_1),$\ldots$,f(m\_k)).}}$\\[0.1cm] %%%(avec les \texttt{m\_i}$<_{{}_E}$\texttt{n} o\`u $\leq_{{}_E}$ est un bon ordre si on veut s'assurer que la fonction termine).\\[0.2cm] %La fonction $g$ {\bf enveloppe} l'appel r\'ecursif. %\qmr La plupart des fonctions r\'ecursives qu'on \'ecrit naturellement sont {\bf r\'ecursives envelopp\'ees}. \dfn Une fonction est dite {\bf r\'ecursive envelopp\'ee} lorsque %tous ses appels r\'ecursifs se font {\it \`a l'int\'erieur} d'une fonction~: $$\dsp{f(x)=\lect{\text{si x est un cas de base alors une valeur de base}\\ \text{sinon }g(x,f(h_1(x)),$\ldots$,f(h_k(x))).}}$$ La fonction $g$ {\bf enveloppe} les appels r\'ecursifs (ou l'unique appel r\'ecursif si $k=1$). \nfd \exs~ \begin{description} \item[fibonacci] \ocaml{(+)} \item[factorielle] \ocaml{fun x -> n * x} \item[binomiaux] \ocaml{(+)} \item[valuations] \ocaml{fun x -> 1 + x} \end{description} \sxe %\begin{frame}{R\'ecursivit\'e envelopp\'ee~: exemple} %Qui est \texttt{g} pour $\ldots$\pause %\begin{enumerate} %\item la factorielle (\'ecrite na\"ivement)~?\pause %\item le calcul des binomiaux~?\pause %\item la fonction 91 de McCarthy~? %\end{enumerate} %\end{frame} % %\begin{frame}{Rappel} L'utilisation de la r\'ecursivit\'e envelopp\'ee implique l'utilisation d'une pile d'ex\'ecution. \exx ~Qu'est-ce qui se passe quand on lui demande de calculer $3!$, en fait~? \begin{table}[h] \centering \caption{Pile d'appel pour \ocaml{fact 3}} \label{tab:callstack_fact_3} \begin{tabular}{l|l} Calcul & Pile \\\hline $3!$ & $()$ \\ $3 \times \fbox{2!}$ & $ (\times 3) $ \\ $3\times 2\times \fbox{1!}$ & $ (\times 2, \times 3) $ \\ $3\times 2\times \fbox{1\times 1}$& $ (\times 1, \times 2, \times 3) $ \\ $3\times \fbox{2\times 1}$& $(\times 2, \times 3)$\\ $\fbox{3\times 2}$& $(\times 2)$ \\ $6$&$()$ \end{tabular} \end{table} \xxe %Les calculs se feront seulement au moment du d\'epilage.\\\pause %\`A chaque appel r\'ecursif, on empile. Cela consomme de la m\'emoire. C'est dangereux.\\\pause %(C'est pour \c{c}a que le "recursionlimit" est fix\'e \`a 987 en Python. Caml par contre est optimis\'e pour g\'erer convenablement cette pile.) %\end{frame} % % %\begin{frame}{R\'ecursivit\'e terminale} %Mais \subsection{R\'ecursivit\'e terminale} Attention, toutes les fonctions r\'ecursives qu'on \'ecrit ne sont pas r\'ecursives envelopp\'ees~! % \exx L'exemple typique~: \begin{table}[h] \centering \caption{Pile d'appel pour \ocaml{pgcd 123 45}} \label{tab:call_stack_pgcd} \begin{tabular}{l|l} Calcul & Pile \\\hline \ocaml{pgcd 123 45} & $( )$ \\ \ocaml{pgcd 45 33} & $( )$ \\ \ocaml{pgcd 33 12} & $( )$ \\ \ocaml{pgcd 12 9} & $( )$ \\ \ocaml{pgcd 9 3} & $( )$ \\ \ocaml{pgcd 3 0} & $( )$ \\ \ocaml{0} & $( )$ \\ \end{tabular} \end{table} \xxe \newpage\ \\[-1.75cm] \dfn Une fonction $f : E \too X$ est dite {\bf r\'ecursive terminale} lorsqu'elle est de la forme~: $$f(x)=\lect{\text{si x est un cas de base alors une valeur de base}\\ \text{sinon } f(g(x))}$$ %(avec $y<_{{}_E}x$ o\`u $\leq_{{}_E}$ est un bon ordre sur $E$ sion veut s'assurer que la fonction termine). \nfd \exs Autres exemples d\'ej\`a rencontr\'es~: \ocaml{itere f (n-1) (f x)} {\it mais pas \ocaml{f (itere f (n-1) x)}}. \sxe \exx ~ %Reprenons l'exemple de la factorielle, mais \'Ecrivons maintenant une fonction {\bf r\'ecursive terminale} qui calcule la factorielle. \begin{minted}{ocaml} let fact n = let rec aux n acc = match n with | 0 -> acc | _ -> aux (n-1) (n * acc) in fact n 1 \end{minted} \xxe %\exx ~ Encore un autre exemple du TD qui peut se traiter de la m\^eme fa\c{c}on~:\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ %\xxe \subsection{En guise de conclusion} \begin{center} Quelle est la diff\'erence entre it\'eration et r\'ecursivit\'e terminale~? \medskip {\large{Il n'y en a \emph{pas}.}} \end{center} \bigskip \section{Terminaison des fonctions r\'ecursives} \medskip \subsection{Terminaison des fonctions it\'eratives} \medskip Ce {\bf n'est pas} l'objet de ce chapitre. Mais un bref rappel (un appel~?)~: pour montrer qu'une boucle \texttt{while} termine, on utilise un {\bf variant de boucle}, \cad une expression enti\`ere d\'ependant des variables de la fonction qui d\'ecro\^it strictement \`a chaque it\'eration de la boucle. \medskip \exs~ Variant de boucle pour la dichotomie: largeur de la plage de recherche. \sxe \subsection{Un probl\`eme \`a r\'esoudre} Une fonction r\'ecursive n'a aucune raison de %terminer. Et d'ailleurs, celles qu'on a \'ecrites au dessus ne terminent pas~! En tout cas pas toujours. toujours terminer. Pourquoi~? %Par exemple~: %\begin{enumerate} %\item La fonction %\begin{lstlisting} %let rec f n = f (n-1);; %\end{lstlisting} %ne termine pas. Pourquoi~? \unemicroligne %\item La fonction %\begin{lstlisting} %let rec f n = match n with %| 0 -> 0 %| n -> f (n*n);; %\end{lstlisting} %ne termine pas non plus. Pourquoi~? \unemicroligne %\end{enumerate} \subsection{Cas des fonctions $\N\too X$} \lem Si $f : \N\too X$ est une fonction r\'ecursive telle que~: \begin{enumerate}[$\bullet$] \item le cas $n=0$ est un cas de base (la fonction ne s'appelle pas elle-m\^eme sur cet argument)~; \item les autres cas se traitent par (un nombre born\'e d') appels r\'ecursifs sur des entiers strictement plus petits~; \end{enumerate} Alors $f$ termine. \mel \demo par l'absurde: si $f$ strictement décroissante à valeurs dans $\N$, alors $|f^{\to }(\N)| = +\infty$, alors on a une suite strictement décroissante d'entiers, impossible. \cqfd \rmq M\^eme si on n'a pas $f : \N\too X$, on peut parfois s'y ramener~! \\Par exemple, pour montrer qu'une fonction d\'efinie sur les {\it 'a listes} termine, il suffit de montrer~:\\[0.1cm] %\unemicroligne\!\!...................\\ %\uneligne\\ %\uneligne\\ $\bullet$ le cas sur la liste vide est un cas de base \\ $\bullet$ ~et les appels récursifs sur la liste se font sur des listes \emph{de longueur} strictement décroissante.\\[0.25cm] Le cas de $\N\too X$ est en fait un cas particulier du cas g\'en\'eral.\\ On verra comment retrouver le cas des {\it 'a listes} comme un autre cas particulier de ce cas g\'en\'eral plus bas. \qmr %\exs~ Sauvons notre fonction qui ne termine pas.\newpage %\sxe %\ \\[-2cm] \smallskip \subsection{Bon ordre sur un type ou un ensemble} \dfn On dit que $(E,\leq_E)$ est {\bf bien ordonn\'e}, ou que {\bf $\leq_E$ est un bon ordre sur $E$} lorsque toute partie non vide de $E$ a un plus petit \'el\'ement. \nfd \exs~ \begin{itemize} \item $(\N, \le )$ \item $(\N^2, \le_\text{lex})$ avec $(a, b) \le_{\text{lex}} (c, d) \overset{\text{def}}{\iff} a < c \ \text{ou}\ (a = c \ \text{et}\ b \le d)$ \end{itemize} \sxe \thm Dans un ensemble bien ordonn\'e, toute suite strictement d\'ecroissante d'\'el\'ements est {\bf finie}. \mht \medskip \subsection{Terminaison de fonctions r\'ecursives} \medskip \col Si $E$ est bien ordonn\'e et $f : E\too F$ est une fonction r\'ecursive telle que~:\begin{enumerate}[$\bullet$] \item les \'el\'ements minimaux de $E$ sont des cas de base ($f$ ne s'appelle pas elle-m\^eme sur ces argument)~; \item les autres cas se traitent par appels r\'ecursifs sur des \'el\'ements de $E$ strictement plus petits~; \end{enumerate} Alors $f$ termine. \loc \exx~Un exemple~: le calcul des binomiaux via la formule de Pascal (\ocaml{binom}) \begin{itemize} \item Définie sur $(\N^2, \le_{\text{lex}})$ \item cas de base contient $ \min\limits_{(\N^2, \le_{\text{lex}})} \N^2 = (0, 0) $ (c'est \ocaml{| (0, n) -> 1} avec \ocaml{n} = 0) \item appels sur des entiers strictement décroissants $\begin{pmatrix} n-1\\k-1 \end{pmatrix} $ et $\begin{pmatrix} n-1 \\ k \end{pmatrix} $ or $(k-1, n-1) <_{\text{lex}} (k, n)$ et $(k, n-1) <_{\text{lex}} (k, n)$. \end{itemize} D'après le théorème de terminaison, \ocaml{binom} termine. \xxe \rmq Des fois, \c{c}a se passe mal (on ne peut pas utiliser le th\'eor\`eme pr\'ec\'edent, mais les fonctions terminent quand m\^eme... ou ne terminent pas... ou on ne sait pas...). C'est la vie. \qmr \exs \paragraph{Fonction 91 de McCarthy} \begin{minted}{ocaml} let rec f n = if n > 100 then n - 10 else f (f (n + 11)) \end{minted} \paragraph{Syracuse} \[ f := n \mapsto \begin{cases} 0 &\text{ si } n \in \{0, 1\} \\ f(3n + 1) &\text{ si } n \in 2\N + 1 \\ f(\frac{n}{2}) &\text{ si } n \in 2\N \end{cases} .\] \sxe %\begin{frame}[fragile]{Applications} %Calcul des binomiaux. \pause\\\ \\ %\begin{lstlisting} %let rec binomial k n = match (k,n) with % | (0,n) -> 1 % | (k,0) -> 0 % | (k,n) -> (binomial (k-1) (n-1)) % + (binomial k (n-1));; %\end{lstlisting}\ \\\ \\ %Pourquoi termine-t-elle~? %\end{frame} % % %\begin{frame}{Applications} %Bijection $\N^2\simeq\N$~? %\end{frame} % %\begin{frame}{Pas de miracle} %Comment faire pour la terminaison de la "fonction 91" de McCarthy~? %$$\dsp{f(n) = \lect{n-10 \text{ si } n>100\\ f(f(n+11)) \text{ sinon}}}$$ %\end{frame} % %\begin{frame}{Question ouverte} %Comment faire pour la terminaison des fonctions associ\'ees \`a la suite de Syracuse~? %\end{frame} % %\begin{frame}{La r\'eponse est triste} %Comment faire pour la terminaison d'une fonction donn\'ee en argument~?\\\ \\ %(TD $n^\circ 1$) %\end{frame} % \section{Correction des fonctions r\'ecursives} \medskip \subsection{Correction des fonctions it\'eratives} \medskip Ce {\bf n'est pas} l'objet de ce chapitre. Mais un bref rappel (un appel~?)~: pour montrer qu'une fonction it\'erative est correcte, on utilise un {\bf invariant de boucle}, \cad un \'enonc\'e d\'ependant des variables de la fonction qui reste inchang\'e \`a chaque it\'eration de la boucle, qui est vrai avant la premi\`ere it\'eration de la boucle, et qui donne le r\'esultat demand\'e \`a l'issue de la derni\`ere it\'eration de la boucle. \medskip \exx~Prenons le calcul it\'eratif d'une factorielle. \begin{minted}{ocaml} let fact n = let result = ref 1 in for i = n downto 1 do result := !result * i done; !result \end{minted} Invariant: \mint{ocaml}|!result * fact i| (à la sortie, \ocaml{!result} = \ocaml{!result * fact 1} et $\forall i, \ocaml{!result * fact $i$ = fact n}$ \begin{minted}[mathescape]{ocaml} $\forall i,$ !result * fact $i$ = fact n \end{minted} \xxe \medskip \subsection{Correction des fonctions r\'ecursives} \medskip \thm Si $E$ est bien ordonn\'e alors on a $\dsp{\Big( \forall x\in E,\ \big(\forall y 1 | n when n mod 2 = 0 -> let a = f x (n/2) in a*a | n -> let a = f x (n/2) in x*a*a \end{minted} \begin{enumerate} \item Que permet-elle de calculer~? \item Le d\'emontrer. \item Montrer qu'elle termine. \item (Introduction au prochain chapitre~:) quel est son int\'er\^et par rapport \`a une version na\"ive~? \end{enumerate} Comme on le voit avec cet exemple, il est parfois difficile de passer un algorithme en r\'ecursivit\'e terminale. %%%%%% TODO: mettre le TD ici %%%%%%% \end{document}