Algorithmique et structures de données
TP N°8 : L A R
ECURSIVITE
Niveau : 1ère année B.C
Année universitaire : 2019/2020
Exercice 1 : Puissance
Écrire d’une fonction récursive permettant de calculer la mise en puissance de p d’un entier positif n.
L’exposant p qui est un entier positif. n et p sont considérés comme paramètres de la fonction.
Exercice 2 : Somme
Écrire une fonction récursive qui permet de calculer la somme des n (n>0) premier termes (à partir
de 1 jusqu’à n).
Publicité
Exercice 3 : Fibonacci
Écrire une fonction récursive qui permet de calculer les nombres de Fibonacci qui sont définis par :
−
−
fib (0) = 0
fib (1) = 1
− et pour tout n > 1, fib(n) = fib(n-1) + fib(n-2)
Exercice 4 : PGCD
Écrire une fonction récursive qui permet de calculer le plus grand diviseur commun de deux entiers
naturels strictement positifs.
Exercice 5 : Ackerman
Publicité
Écrire une fonction récursive qui permet de calculer la valeur de la fonction d’Ackerman A définie de
la manière suivante :
− A(m, n) = A(m-1, A(m, n-1)) pour m>0 et n>0
− A(0, n) = n+1 pour n > 0
− A(m, 0) = A(m-1, 1) pour m > 0
Exercice 6
Développer une fonction récursive qui détermine si un mot donné est palindrome ou non.
Exercice 7
Donner la variante récursive permettant d’afficher le contenu d’un tableau tab contenant N cases
remplies. On distinguera deux cas :
− Affichage du début à la fin.
Publicité
− Affichage de la fin au début.
Préparé par : Karim Kamoun
1
Exercice 8
Donner les deux variantes itérative et récursive permettant de retourner la somme des éléments d’un
tableau tab contenant N cases remplies.
Remarque : Reprendre l’exercice 8 en écrivant une fonction récursive permettant de retourner
la somme des valeurs positives seulement contenues dans le tableau.
Exercice 9
Étant donné un tableau ne contenant que N valeurs positives, écrire une fonction récursive
permettant de retourner la valeur maximale contenue dans le tableau.
Publicité
Exercice 10
Étant donné un tableau ne contenant que N entiers, écrire une fonction qui permet de retourner le
nombre d’occurrence d’un entier donné passé en paramètre.
Exercice 11
Étant donné un tableau ne contenant que N entiers, écrire une fonction qui permet d’inverser le
contenu du tableau.
Préparé par : Karim Kamoun
2