DEUG 1ere année
MIAS 1 et MASS 1 - Programmation fonctionnelle

TD 4

But : Écriture de fonctions récursives.

\fbox{ \begin{minipage}{160mm} {\bf Id\'ee g\'en\'erale} : notons $n$\space la t... ...it r\'esoudre le probl\\lq eme quelque soit la taille. \end{itemize}\end{minipage}}

\fbox{ \begin{minipage}{160mm} {\bf Il faut imp\'erativement respecter les deux ... ...teinte en un{\bf nombre fini d'appels r\'ecursifs}. \end{itemize}\end{minipage}}


Notation : pour donner les spécifications de fonctions manipulant des listes, on pourra utiliser les notations : listevide pour désigner la liste vide, l=(x . l') pour exprimer que (car l) = x et (cdr l) = l', et (x . l) pour exprimer que l'on effectue l'opération (cons x l).



Exercice 1 : Définir en scheme une fonction permettant de calculer n'importe quel terme de la suite U définie de manière récurrente par :

\begin{displaymath}\left\{ \begin{array}{l} U_0 = 1\\ U_n = 3.U_{n-1}+2,\quad si\quad i>0 \end{array}\right.\end{displaymath}



Exercice 2 : Donner la spécification et définir en scheme une fonction ajoutetous qui prend en paramètres un nombre n et une liste plate de nombres et ajoute n à chaque nombre de la liste.
(ajoutetous 10 '( 1 2 3 4 5 6)) $\longrightarrow$ (11 12 13 14 15 16)



Exercice 3 : Donner la spécification et définir en scheme une fonction tsd qui prend une liste non vide et renvoie une liste équivalente privée de son dernier élément.
(tsd '(a d f g h)) $\longrightarrow$ (a d f g)



Exercice 4 : Donner la spécification et définir en scheme une fonction Nbocc qui renvoie le nombre d'occurences d'un objet dans une liste plate.
(Nbocc 1 '(1 1 c 1 4 h)) $\longrightarrow$ 3