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

TP 4 : Fonctions récursives

Dans les exercices qui suivent vous détaillerez les spécifications en donnant explicitement la variable d'induction d'induction, la (les) condition(s) d'arrêt les équations de récurrences permettant de résoudre les problèmes posés.

Exercice 1 : Spécifier et écrire une fonction puissance (sans utiliser la fonction prédéfinie expt) qui calcule xⁿ où x est un réel et n un entier relatif. Cette fonction doit rendre un résultat correct dans tous les cas.

Exercice 2 : On considère la suite U qui, étant donnée trois réels a, b et u₀ est définie par :

$$\left\{\begin{array}{l} U_0= u_0\\ U_{n}=a.U_{n-1}+b,\quad pour\quad n>0 \end{array}\right.$$

et V la série définie par : $\forall n\geqslant 0 : V_n=U_0+U_1+\ldots +U_n$.
Spécifier et écrire deux fonctions suite et serie permettant de calculer, pour des valeurs quelconques de a, b et u0, la valeur du nième terme de U et de V.

Dans les exercices qui suivent, on ne considère que des listes dont les éléments sont des atomes et qu'on appelle listes plates.

Exercice 3 : Spécifier er écrire une fonction fois2 qui multiplie par deux tous les éléments d'une liste de nombres.

Exercice 4 : Spécifier et écrire un prédicat appartient qui prend un élément et une liste et renvoie vrai si l'élément est dans la liste et faux sinon.

Exercice 5 : Spécifier et écrire une fonction nieme qui renvoie le nième élément d'une liste. Tenir compte du cas où la liste ne contient pas assez d'éléments.

Exercice 6 : Spécifier et écrire une fonction dernier qui renvoie le dernier élément d'une liste.

Exercice 7 : Spécifier et écrire une fonction ajoutefin qui ajoute un élément à la fin dúne liste.

Exercice 8 : Sécifier et écrire une fonction concat qui renvoie la concaténation de deux listes sans utiliser la fonction append. (Utiliser la fonction ajoutefin).

Exercice 9 : Spécifier et ecrire une fonction supprime qui supprime toutes les occurences d'un élément dans une liste.

Exercice 10 : Dans cet exercice, on désire manipuler des listes qui représente des ensembles, c'est à dire des listes dans lesquelles chaque atome n'apparaît qu'un fois.
Spécifier et écrire :

a)

un prédicat est-ensemble? qui teste si une liste E représente un ensemble;

b)

une fonction union qui réalise l'union de deux ensembles E et F;

c)

et une intersection qui réalisel'intersection de deux ensembles E et F.