Université des Sciences et Technologies de Lille
Licence Miage - Programmation 1 - TP


Un peu de récursivité

Avec des entiers

Ex 1   Écrire une fonction exponentielle Exp, qui calcule xy sans utiliser l'opérateur ** mais en exploitant la définition récursive
xy = 1, si y=0,
xy = (x*x)y/2, si y est pair,
xy = (x*x)y/2*x, si y est impair.

Avec des tableaux

Dans tous ces exercices, on dispose d'un type Tab

     type Tab is array(Positive range <>) of Integer;
Ex 2   Écrire une fonction Min qui recherche l'élément minimal d'un tableau.

Ex 3   Écrire une fonction Appartient qui teste si un élément appartient à un tableau.

Ex 4   Écrire une procédure Put qui affiche les éléments d'un tableau.

Ex 5   Écrire une fonction Fusion qui prend en argument deux tableaux triés et construit l'union ordonnée de ces tableaux.

Ex 6   Écrire une procédure Renverse qui prend en argument un tableau, et le modifie ainsi
4 2 7 1
Þ
1 7 2 4

Ex 7   Écrire une fonction Facteur_premier qui prend en argument un entier n et calcule l'ensemble de ses facteurs premiers, en les stockant dans un tableau. Le tableau tient compte de la multiplicité des facteurs, c'est-à-dire que si 4 divise n, alors 2 apparait deux fois dans le tableau.

Avec des chaînes de caractères

Ex 8   Écrire une fonction récursive Palindrome qui teste si un mot est un palindrome.

Ex 9   Écrire une procédure récursive Nettoyage, qui prend en argument une chaîne de caractères, et y supprime tous les caractères d'espace.

Ex 10   Écrire une fonction Paire_E qui teste si un mot contient un nombre pair de 'E'.

Ex 11   Écrire une fonction Premiere_occurrence(S:STRING; C:CHARACTER), qui renvoie la position de la première occurrence du caractère C dans la chaîne S. Dans le cas où C ne figure pas dans S, on déclenche une exception.

Les limites de la récursivité

Ex 12  

fibo(0) = 1
fibo(1) = 1
fibo(n) = fibo(n-1) + fibo(n-2), si n ³ 2
Écrire une fonction récursive qui calcule la fonction de Fibonacci. Évaluer la complexité, en comptant le nombre d'appels récursifs.

Réécrire la fonction de Fibonacci avec un algorithme itératif. Quelle est la complexité de votre nouvelle fonction ?