\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<x,\ P(y)\big) \Rightarrow P(x)\Big) \Longrightarrow \big(\forall x\in E,\ P(x)\big)}$.
\mht

Remarquons que pour $E = \N$, on retrouve le théorème de la récurrence forte.

\col Si $E$ est bien ordonn\'e et $f : E\too F$ est une fonction r\'ecursive qui termine, telle que~:\begin{enumerate}[$\bullet$]
\item $f$ est correcte sur ses cas de base~;
\item sur les autres cas, $f$ est correcte en supposant qu'elle l'est sur ses appels r\'ecursifs~;
\end{enumerate}
alors $f$ est correcte.
\loc

\exx~Reprenons l'exemple du calcul des binomiaux via la formule de Pascal.
\begin{itemize}
	\item \ocaml{binom} est correct sur les cas de base par définition
	\item Supposons les appels récursifs corrects. On a
		\begin{align*}
			\ocaml{binom}(n)(k) &= \ocaml{binom}(n)(k-1) + \ocaml{binom}(n-1)(k-1)&&\text{par définition} \\
					    &= \begin{pmatrix} n-1 \\ k-1 \end{pmatrix} + \begin{pmatrix} n-1 \\ k \end{pmatrix} &&\text{par hypothèse} \\
					    &= \begin{pmatrix} n\\k \end{pmatrix} &&\text{d'après Pascal} \\
		.\end{align*}
\end{itemize}
\xxe


{\bf Un algorithme du programme (on le reprend en TP)~: l'exponentiation rapide.}\\[0.25cm]
On consid\`ere la fonction suivante.
\begin{minted}{ocaml}
let rec f x n = match n with
	| 0 -> 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}
