\documentclass[10pt,twoside]{article}
%\usepackage{etex}

\usepackage[width=170mm,height=240mm]{geometry}
\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{preambule-utf8}

\usepackage[boldsans]{ccfonts}
\usepackage{beton,euler}
\usepackage{luximono}

\usepackage{bbding,filecontents}
 \usepackage{wasysym,marvosym,keystroke}
\definecolor{0.95white}{rgb}{0.95,0.95,0.95}


% pour algorithm
\incmargin{1em}
\dontprintsemicolon
%\SetCommentSty{\small\sffamily}


\graphicspath{{/home/moi/Photos/Maths/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}}

\entete{TD Maple n°8}{Algorithmes récursifs}{PCSI 2 - Lycée Clemenceau}%g,d,b

 \usepackage{index}
  \makeindex
 \renewindex{default}{idx}{ind}{Index des commandes vues aujourd'hui}

\newcommand{\indexkeywordsmaple }[1]{\index[default]{maple@\textbf{\large Commandes}!#1@\textcolor{red}{\texttt{#1}}|textbf}}

\newcommand{\indn }[1]{\index[default]{maple@{\large
      Notions }!#1@ #1}}

\newcommand{\indt }[1]{#1\index[default]{maple@{\large
      Touches }!#1@ #1}}


%%% Environnement des réponses du logiciel
\DefineVerbatimEnvironment{boxedverbatim}{Verbatim}{fontsize=\small,formatcom=\color{blue},fontshape=it,gobble=2,frame=single,framesep=4mm,label=\textit{\small \textcolor{black}{Réponse du logiciel}},xleftmargin=10pt,rulecolor=\color{black}}




\newcommand\Com[1]{%
\shorthandoff{;:}\textcolor{red}{{ \ttfamily #1}}\index[default]{maple@\textbf{\large Commandes}!#1@\textcolor{red}{\texttt{#1}}|textbf}}


%%% Com avec syntaxe
\newcommand\Comsi[2]{%
\shorthandoff{;:}\textcolor{red}{{ \ttfamily #1}}(\textcolor{red}{\texttt{#2}})\index[default]{maple@\textbf{\large Commandes}!#1@\textcolor{red}{\texttt{#1}}|textbf}}





%%%%%%  Commande personnelle ou bout de code

\renewcommand{\code}[1]{\textcolor{red}{\bfseries \texttt{#1}}}


\newcommand\MAPLE{\lstset{numbers=none,language=Maple,xleftmargin=10pt,%
keywordstyle
=\color{red}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{red},commentstyle=\normalfont\small\itshape,breaklines=true,frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,backgroundcolor=\color{white}}
}





\newcommand\caml{\lstset{numbers=none,language=caml,xleftmargin=10pt,%
keywordstyle
=\color{0.2white}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{0.2white},commentstyle=\normalfont\small\itshape,breaklines=true,frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,backgroundcolor=\color{creme}}
}

% %%% Environnement des réponses du logiciel
% \DefineVerbatimEnvironment{boxedverbatim}{Verbatim}{fontsize=\small,formatcom=\color{blue},fontshape=it,gobble=2,frame=single,framesep=4mm,label=\textit{\small \textcolor{black}{Réponse du logiciel}},xleftmargin=10pt,rulecolor=\color{black}}



% %\newlength{\moitie}
% \newlength{\longmot}
% \newenvironment{BoxedVerbatim}[1][(\linewidth)/2-1em]{%
%   \setlength{\margegauche}{#1}
% \setlength{\moitie}{(\widthof{\texttt{Réponse du logiciel}})/2}%
% \setlength{\longmot}{\widthof{\texttt{Réponse du logiciel}}} 
%  \par
%   \begin{lrbox}{\dangerbox}
%     \begin{minipage}{\linewidth-2\marge-2\pslinewidth}
%       \par\vspace*{\margehaut}  %\fontfamily{ccm}\selectfont
% }
% {%
%     \end{minipage}%
%   \end{lrbox}
%   % Affiche le texte dans un cadre en couleur.
%   \rput[tl](0,0){%
%     \psframebox[framesep=\marge,linewidth=.5\pslinewidth]{%
%       \usebox{\dangerbox}%
%     }%
%   }%
%  %  Efface le trait juste ce qu'il faut
%   \rput(\marge,0){%
%     \rput(\margegauche,0){%
%       \psline[linewidth=2\pslinewidth,linecolor=white](-\moitie,0)(\moitie,0)
%     }
%   }
% \rput(\marge,0){\rput(\margegauche,0){{\ttfamily \itshape \small Réponse du logiciel}}}
%   % Réserve la place verticale pour la suite
%  \par
%   \setlength{\marge}{\ht\dangerbox+\dp\dangerbox+2\marge+\extraline}
%   \vspace{\marge}
% }




%biblio

% \usepackage[super,idem=strict,ibidem=name]{jurabib}
% \usepackage{url}
% \bibliographystyle{jurabib}



\begin{document}
\setlength{\parindent}{0pt}
\thispagestyle{empty}



%%%%%% TITRE{vide}{intitule chapitre : lecon, chapitre ...}{debut titre}{fin titre}{titre toc}{dessin}
%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%% TITREs{vide}{intitule chapitre : lecon, chapitre ...}{debut titre}{fin titre}{titre toc}
%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\setcounter{NumLecon}{7}

\TITREs{}{TD  \includegraphics[height=0.8cm]{maple.eps}
}{Algorithmes récursifs}{}{Algorithmes récursifs}
        

\MAPLE

%\begin{multicols}{2}

\section{Programmation impérative/fonctionnelle}


Jusqu'à  maintenant,   nous  avons  surtout   utilisé  des  algorithmes
\emph{itératifs}  ou \emph{impératifs}  employant des  \emph{boucles} et
des \emph{affectations}.

Ces algorithmes ont plusieurs défauts~:

\begin{itemize}
\item    ils     s'éloignent    des    mathématiques     en    utilisant
  l'\emph{affectation}  comme base de  programmation. Une  même variable
  peut prendre des valeurs tout à fait différentes selon le
  moment où on l'évalue~;
\item  la   mémoire  est  constamment  modifiée   par  le  programme~:~le
  programmeur doit  à chaque instant  connaître son état pour  savoir ce
  que représentent les variables affectées~;
\item  on  est  obligé  de  créer des  variables  temporaires  pour  que
  certaines zones de la mémoire  restent dans un certain état~:~cela est
  source  de  nombreux  bogues  dus   à  une  mauvaise  maîtrise  de  la
  chronologie des affectations.
\end{itemize}


Les  langages fonctionnels bannissent  totalement les  affectations. Ils
utilisent   des  fonctions   \emph{au  sens   mathématique   du  terme},
c'est-à-dire qu'une fonction  associe une unique valeur de  sortie à une
valeur  donnée  en  entrée.  Les  effets  négatifs  listés  précédemment
disparaissent donc. Les  fonctions peuvent être testées une  par une car
elle ne  changent pas  selon le  moment où elles  sont appelées  dans le
programme. On parle  de \emph{transparence référentielle}. Au contraire,
une procédure  avec \emph{effets de  bord} ne dépend pas  uniquement des
arguments entrés et donc peut changer de comportement au cours du programme.


Par  exemple,  définissons une  fonction  \texttt{plus} dépendant  d'une
entrée \texttt{k}~:


\begin{lstlisting}
n:=1:

plus:=proc(k)
global n;
n:=n+k;
end:
\end{lstlisting}

Alors 

\begin{lstlisting}
plus(3)
\end{lstlisting}


 renvoie 4 et si on demande à nouveau 

 \begin{lstlisting}
plus(3)
 \end{lstlisting}

on obtient 7.
Ainsi \texttt{plus}  n'est pas une  fonction au sens mathématique  car 3
peut avoir des images distinctes~!

\medskip


La  récursivité est  le  mode  habituel de  programmation  avec de  tels
langages~:~il s'agit  de fonctions qui  s'appellent elles-mêmes. Pendant
longtemps,  la  qualité des  ordinateurs  et  des langages  fonctionnels
n'était pas  suffisante et limitaient les domaines  d'application de ces
langages.

MAPLE  n'est  pas  un  langage  fonctionnel mais  permet  de  créer  des
fonctions récursives~:

\begin{lstlisting}
suivant:=proc(n)
if n=0 then 1
else 1+suivant(n-1)
fi
end:
\end{lstlisting}

Ainsi, 

\begin{lstlisting}
suivant(700)
\end{lstlisting}

renvoie bien 701  mais pour 7000 on obtient  \textit{Error, (in suivant)
  too many levels of recursion}.

Et oui, MAPLE ne traite  pas efficacement les récursions, comme beaucoup
d'autres langages,  c'est pourquoi pendant longtemps  seuls les langages
impératifs ont prévalus. 

Utilisons  par  exemple  le  langage  fonctionnel CAML  étudié  par  vos
camarades de MP ayant choisi l'option informatique. 

\caml

\begin{lstlisting}
# let rec suivant(n)=
  if n=0 then 1
  else 1+suivant(n-1);;  
\end{lstlisting}

Alors par exemple~:

\begin{lstlisting}
# suivant(36000);;
- : int = 36001
\end{lstlisting}

Mais

\begin{lstlisting}
# suivant(3600000);;
Stack overflow during evaluation (looping recursion?).
\end{lstlisting}


Aujourd'hui, les langages fonctionnels  sont très efficaces et gèrent de
manière  intelligente  la  \emph{pile}  où  sont  accumulés  les  appels
récursifs afin de ne pas  l'encombrer. Ils le font soit automatiquement,
soit si la fonction utilise une \emph{récursion terminale}, c'est-à-dire
si l'appel récursif à la fonction n'est pas \emph{enrobé} dans une autre
fonction. 

Ici, ce  n'est pas le  cas car l'appel récursif  \code{suivant(n-1)} est
enrobé dans la fonction $x\mapsto 1+x$.


On peut y  remédier en introduisant une fonction  intermédiaire qui sera
récursive totale~:

\begin{lstlisting}
# let rec suivant_rec(n,resultat)=
        if n=0 then resultat
        else suivant_rec(n-1,resultat+1)
\end{lstlisting}


puis on appelle cette fonction en prenant comme résultat de départ 1, le
suivant de 0~:

\begin{lstlisting}
# let suivant(n)=
  suivant_rec(n,1);;
\end{lstlisting}

Alors~:


\begin{lstlisting}
# suivant(360000000);;
- : int = 360000001
\end{lstlisting}





\MAPLE


MAPLE n'étant pas un langage fonctionnel, la différence est moins visible...


\begin{lstlisting}
suivant_rec:=proc(n,resultat)
  if n=0 then resultat
         else suivant_rec(n-1,resultat+1)
  fi
end:
\end{lstlisting}


\begin{lstlisting}
suivant_total:=proc(n)
  suivant_rec(n,1)
end:
\end{lstlisting}


\section{Écrire des algorithmes récursifs avec MAPLE}


Même  si nous n'avons  pas affaire  à un  langage traitant  la récursion
efficacement,  nous   pouvons  malgré  tout  réécrire   la  plupart  des
algorithmes vus cette année sous forme récursive.




\subsection{Factorielle}

Donnez une  version récursive  du calcul de  la factorielle  d'un entier
puis imaginez une version récursive terminale.


\subsection{Partie entière}

Il est inutile de vous rappeler  que $\lfloor x\rfloor=1+\lfloor x-1\rfloor=\lfloor x+1\rfloor-1$.

Imaginez alors un programme récursif déterminant la partie entière d'un nombre
réel positif puis d'un nombre réel quelconque.




\subsection{Méthode d'Euler pour la résolution des EDO}


Vous vous souvenez  de la méthode d'Euler pour résoudre  une EDO du type
$y'=f(y,x)$.

Que pensez-vous du programme~:

\begin{lstlisting}
euler_rec:=proc(f,x,xmax,y,h,liste_points)
if x>=xmax then liste_points
else euler_rec(f,x+h,xmax,y+f(y,x)*h,h,[op(liste_points),[x,y]])
fi
end:
\end{lstlisting}


Comment l'utiliser  pour représenter graphiquement  une approximation de
la solution de $y'=f(y,x)$ avec $y(x_0)=y_0$~?

\subsection{Spirale d'Archimède}

Imaginez  une procédure  récursive pour  tracer une  spirale d'Archimède
comme dans le TD n°2. 

On pourra l'appeler \Com{spirale\_rec:=proc(n,z,liste\_points)}.

On l'utilisera ensuite avec~:

\begin{lstlisting}
spirale:=proc(n)
  plot([spirale_rec(n,-I,[])])
end:
\end{lstlisting}




\subsection{Dichotomie, méthode de Newton}


Ces  méthodes sont  par essence  récursives. Rien  de plus  naturel que
d'écrire l'algorithme récursif correspondant.
On  ne s'encombrera  pas de  compteur mais  on affichera  directement le
résultat.

Normalement, en entrant~:

\begin{lstlisting}
 dicho_rec(x->x^2-2,1.0,2.0,0.00000001); 
\end{lstlisting}

on obtient \Com{1.414213559}

et en entrant 

\begin{lstlisting}
 newton_rec(x->x^2-2,1.0,10.0^(-50));
\end{lstlisting}

on obtient \Com{1.4142135623730950488016887242096980785696718753769}


Il faudra faire attention à \Com{evalf}


%\subsection{Étude des suites logistiques}



\subsection{Développements limités}

Il  s'agit de  trouver une  bonne relation  de récurrence.  Petit rappel
MAPLE~:~la  \emph{fonction}  dérivée d'ordre  $n$  de  $f$ s'obtient  en
entrant \verb+(D@@n)(f)+.


Alors, en entrant~:

\begin{lstlisting}
DL(x->tan(x),15);
\end{lstlisting}

vous devez obtenir~:

\begin{Verbatim}
929569           21844           1382         62        17         2       1      
--------- x^15 + ------- x^13 + ------ x^11+ ---- x^9 + --- x^7 + -- x^5 + - x^3 + x
638512875        6081075        155925       2835       315       15       3       
\end{Verbatim}



\subsection{Intégration~:~méthode des rectangles }

Vous vous souvenez~:~pour obtenir l'approximation de l'intégrale d'une fonction $f$ entre $a$ et $b$ on peut faire la somme des aires de rectangles particuliers. Imaginez un algorithme récursif permettant de calculer l'approximation d'une intégrale par cette méthode.

Par exemple~:

\begin{lstlisting}
  4*rectangles(x->1/(1+x^2),0,1,0.0001);
\end{lstlisting}

donne \Com{3.141892663}

%\end{multicols}
\end{document}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
