\documentclass{article}
\usepackage[dvips]{epsfig}

\newcommand{\elem}[1]{\bigskip \noindent {\bf #1}}
\newcounter{exercice}
\newcommand{\exo}{\stepcounter{exercice} \bigskip \noindent {\bf  
Exercice \theexercice . } }
\newcommand{\td}{\stepcounter{exercice} \bigskip \noindent {\bf  
Exercice \theexercice\,(TD). } }
\newcommand{\tp}{\stepcounter{exercice} \bigskip \noindent {\bf  
Exercice \theexercice\,(TP). } }
\newcounter{abclist}
\newenvironment{abc}{\begin{list}{(\alph{abclist})}{\usecounter{abclist}}}
{\end{list}}
\newcommand{\Feuille}[1] {\hfill  {\Large Feuille de TD / TP  
n$^o$\,#1} \hskip 10mm \hfill IF122
\vskip 1mm}
\newcommand{\titre}[1] {\large\hfill #1\hspace*{\fill}
\vskip 10mm}
\newcommand{\correction}[1] {\hfill  {\Large Correction du TD / TP  
n$^o$\,#1} \hskip 10mm \hfill IF122
\vskip 1mm}

\def\R{\mbox{I\hspace{-.15em}R}}
\title{TD-3 \\ Recursivite}
\date{}
\author{}


\pagestyle{empty}
\topmargin-1.7cm
\oddsidemargin  -1cm  %0.95cm
\evensidemargin 0cm  %0.95cm
\textheight             25cm
\textwidth              18cm
\parskip \medskipamount
\parindent 0pt


%---------------%
\begin{document}

\maketitle

{\bf Recursivite Simple}

Lors du Td precedent nous avons vu que {\em De facon simpliste, une
proc\'edure (ou une fonction) est un moyen de factoriser un code
souvent utilis\'e et d'utiliser ce bloc simplement \`a un autre
endroit du programme en l'appelant par son nom. En r\'ealit\'e c'est
un m\'ecanisme plus intéressant que le simple recopiage car on peut
utiliser le nom de la proc\'edure dans le code m\^eme de la
proc\'edure que l'on est en train de d\'efinir.}

Puis nous nous etions interesse essentiellement aux variables et
parametres. Cette distinction entre fonctions et factorisation est
illustree ici :


\exo :\\ Que fait le programme suivant sur des entrees positives ? sur
des entrees negatives ? Corriger le pour qu'il ait un comportement
coherent pour toute entrees. Dessiner l'arbre des appels pour ce
programme. Comment progresse le point de controle dans cet arbre ?  A
un moment donne quelles sont les procedures en cours ?


{\small\begin{verbatim} 
#include <iostream>

void f (int n){
  cout << n << `` ``;
  if (n!=0) f (n-1);
  cout << n << `` ``;
}

int main(){
  int n;
  cin >> n;
  f(n);
  cout << endl;
}
\end{verbatim}}

\exo :\\
Que fait la fonction suivante :
{\small \begin{verbatim}
int f(int n){
 if (n<0) return f(-n);
 if (n==0) return 0;
 return (1+f(n/10));
}
\end{verbatim}}

\exo :\\
\begin{enumerate}
\item Ecrire une fonction qui calcule la factorielle d'un entier.
\item Ecrire une fonction qui teste si un entier est divisible par un autre.
\item Ecrire une procedure qui affiche la decomposition d'un entier en
produit de facteur premier.
\item On rappelle qu'un entier est divisible par 3 si la somme de ses
chiffres est divisible par 3. Ecrire une fonction recursive, en
identifiant bien les cas de base, qui utilise cette propriete pour
dire si un nombre est divisible par 3.
\item Connaissez vous une regle analogue pour la divisibilite par 11 ?
Bon, alors la voila : si on numerote les chiffres de l'ecriture d'un
nombre pour leur attribuer une position, disons de droite a gauche,
alors si la somme des chiffres en position paire est egal a la somme
des chiffres en position impaire c'est que le nombre est divisible par
11.  Ecrire une fonction qui utilise cet argument pour tester la
divisibilite par 11.
\end{enumerate}


{\bf Recursivite multiple}\\

\exo Que calculent les fonctions suivantes :
{\small \begin{verbatim}
#include <iostream>

// prototypes
   bool odd (int i);
   bool even(int i);

// corps des fonctions 
   bool even (int i) {
    if (i==0) {return true;}
    else {return (odd(i-1));}
   }

   bool odd (int i) {
    if (i==0) {return false;}
    else {return (odd(i-1));}
   }

   void main(){
   cout << odd(5) << odd(^) << even (5) << even(6) << odd(-007) << endl;
   }
\end{verbatim}
}

Pour ecrire des fonctions mutuellement recursive, on a indiqu\'e au
compilateur les profils, ou prototypes, des fonctions avant de les
ecrire. C'est pour lui une aide a l'analyse statique.\\

La declaration des prototypes n'est pas une obligation theorique, on
peut trouver des langages ou elle n'est pas necessaire. Par contre
elle l'est pour le c++ que l'on utilise. Vous pouvez comparer cette
obligation a l'indicage des tableaux en c++ : ce sont obligatoirement
des entiers qui commencent a zero, alors qu'on pourrait imaginer des
tableaux dont les indices sont un intervalle [-5,3] ou des
enumerations. Gardez a l'esprit que $c++$ est un compromis.\\

{\bf Graphe de dependence}

On dit qu'une fonction $f$ appelle une fonction $g$ si la definition
de $f$ comporte un appel a la fonction $g$. Le {\em graphe de
dependence} d'un ensemble de fonction $V$ est le graphe oriente dont
l'ensemble des noeuds est $V$, et o\`u un arc relie un noeud $f\in V$
\`a un noeud $g$ si $f$ appelle $g$.

\exo Donner une definition de la recursivite bas\'ee sur le graphe de
d\'ependence, dessiner le graphe de dependance pour les fonctions
${main, odd, even}$. Quel est le rapport avec l'arbre des executions ?


\exo La procedure suivante est elle recursive :
{\small \begin{verbatim}
void  f(){
 if (2 > 3) f();
}
\end{verbatim}
}

\exo Que pensez vous du programme suivant ?
{\small \begin{verbatim}
#include <iostream>
void main(){
  int i;
  cin >> i;
  if (i>0) main(); 
}
\end{verbatim}
}

\exo Reecrire la fonction $even$ de sorte qu'elle ne contienne que des
appels recursifs a $even$. Une generalisation est possible : si un
programme contient un ensemble de fonctions $V$, il existe un
programme equivalent qui ne contient que $main$ et une autre fonction
recursive. Avez vous une idee de comment ?




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                               %%%
%%%                         Correction                            %%%
%%%                                                               %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pagebreak

{\bf Exo 1:} Si l'entier entr\'e est positif, par exemple 5, le
programme affichera ``5 4 3 2 1 0 0 1 2 3 4 5''.  Il ne s'arretera pas
sur une entree negative. On peut corriger de plusieurs facon,
{\small\begin{verbatim} 
void f (int n){
  cout << n << `` ``;
  if (n > 0) f (n-1);
  cout << n << `` ``;
}
\end{verbatim}
} ou encore :

{\small\begin{verbatim} 
void f (int n){
  cout << n << `` ``;
  if (n > 0) f (n-1);
  if (n < 0) f (n+1);
  cout << n << `` ``;
}
\end{verbatim}
}


{\bf Exo 2:} Il calcule la taille de la representation decimale de
$n$.  Demander d'ecrire la meme en base $9$.

{\bf Exo 3 :}
Pour la factorielle :
{\small \begin{verbatim}
#include <iostream>

int fact(int n){
if (n<=0) return 1;  // On prend comme convention que la factorielle de 0 et d'un negatif c'est 1
return n*fact(n-1);
}

int main(){
 int i;
 cout << ``entrez une valeur'';
 cin >> i;
 cout << ``la factorielle de '' << i << `` est '' << fact(i) << endl;
}
\end{verbatim}
}

Pas besoin de recursivite pour la divisibilite.
{\small \begin{verbatim}
bool divise(int a, int b){   // est ce que b divise a ?
 return ((a mod b)==0);
}
}
Quoi que on peut ecrire :
{\small \begin{verbatim}
bool divise (int a, int b){ // est ce que b divise a ?
 if (a<0) return divise(-a,b);
 if (b<0) return divise(a,-b);
 if (a==0) return true;
 if ( (0< a) && (a<b) ) return false;
 return (divise(a-b,b));
}
\end{verbatim}}

{\small \begin{verbatim}
void decompose (int n) {
 if (n <  0) {
   decompose (-n);
   return;
 }
 if ((n == 0)||(n==1)) {
  cout << n << endl; 
  return;
 }
 int i=2;
 while( !divise(n,i)) i++;
 cout << i << `` ``;
 decompose(n/i);
}
\end{verbatim}}


Une fonction recursive pour la somme des chiffres :
{\small \begin{verbatim}
int somme(int i){
 if (i<0) return somme(-i);
 if ( (0<= i) && ( i<=9)) return i;
 return (i mod 10) + somme (i/10);
}
\end{verbatim}
}

Une autre pour la divisibilite par 3 :
{\small \begin{verbatim}
bool divisible_par_3(int i){
 int s;
 if (i<0) return divisible_par_3(-i);
 s=somme(i);
 if ( (s==0) || (s==3) || (s==6) || (s==9) ) return true;
 if ( s<10) return false;
 return (divisible_par_3(s));
}
\end{verbatim}
}

{\small \begin{verbatim}
bool divisible_par_11(int i){
 int sp=0;
 int si=0;
 calcule_sommes(i,sp,si);
 return (sp==si);
}

void calcule_sommes(int i,int &si,int &sp){
 if (i==0) return;
 sp=sp+ (i mod 10);  // je numerote les chiffres en partant de zero a droite
 si=si+ (i/10 mod 10);
 calcule_sommes(i/100,si,sp);
}
\end{verbatim}
}

{\bf Exo 4 :} Une fonction est dite recursive si elle appartient a un
cycle du graphe de dependence.

{\bf Exo 5:} Oui, il faut comprendre qu'on a choisit de definir la
recursivite comme une notion statique. Je n'en rajoute pas, mais ca
entraine une discussion on pourrait se poser la meme question pour une
fonction dont on sait par avance que la profondeur des appels est
bornee par une constante. On voit alors que pour exprimer une
recursivite ``pure'' il faudrait savoir resoudre des problemes tres
compliques. Ce qui peut expliquer que la definition de recursivite
soit statique, pour ne pas mettre le doigt dans qq chose qui mene trop
loin.



\end{document}

