École Supérieure de Technologie
et d’Informatique
A.U. 2010/2011
TD algo 2 : La récursivité
Informatique Appliquée 1ère année
Exercice 1 : Factorielle d’un nombre N
Écrire un algorithme récursif qui permet de calculer le factorielle d’un nombre N donné au
clavier sachant que : N ! = 12……(N-1)N.
Exercice 2 : PGCD de deux nombres
Écrire un algorithme récursif permettant de calculer le plus grand dénominateur commun de
deux entiers naturels a et b (au moins un des deux nombres n'est pas nul). On rappelle la
définition récursive d'Euclide :
PGCD(a,b) = a si b = 0
PGCD(a,b) = PGCD(b, a mod b) sinon.
Exercice 3 : Suite de Fibonacci
Les nombres de Fibonnaci sont définis par la relation suivante :
Publicité
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 pour n ≥ 2
1. Écrire une fonction récursive Fib qui calcule nième nombre de Fibonacci
2. Déterminer le nombre d’appels de Fib pour calculer Fn dans les cas où n = 2, 6, 11 et
30
Exercice 4 : Nombre de combinaisons de p éléments parmi n
Écrire une fonction récursive CNP qui calcule le nombre de combinaisons de p éléments
parmi n éléments différents sachant que :
C1
n = n ; Cn
n = 1 ; Cn
p = Cp n-1 + Cp-1 n-1
Exercice 5 : Fonction d’Ackermann
Écrire une fonction récursive Ack qui calcule Ack(n,m) selon la formule suivante :
• Ack(0,m)=m+1
Publicité
• Ack(n,0) = Ack(n-1 , 1)
• Ack(n,m)=Ack(n-1 , ack(n,m-1))
1
Exercice 6 :
Écrire un algorithme récursif permettant de détecter si un mot ou une phrase est palindrome.
L’algorithme travaillera sur un tableau de caractères et testera si les deux caractères opposés
sont identiques, si oui, il fait un appel récursif pour traiter la chaîne restante. Les espaces
seront ignorés.
Exercice 7 :
Écrire une fonction récursive chiffre (n, k) qui permet de retourner le kième chiffre à partir de
la droite d’un nombre positif n. Exemples :
Le 3ième chiffre à partir de la droite de 8724 est 7
Le 5ième chiffre à partir de la droite de 21327 est 2
Exercice 8 :
Les tours de Hanoi sont un jeu constitué de trois tours sur lesquels peuvent êtres enpilés des
disques de tailles différentes. Le but de cet exercice est de déplacer les disques situés
Publicité
initialement sur la tour 1 vers la tour 3 comme l’illustre le graphique suivant :
Tour 1
Tour 2
Tour 3
Les règles du jeu sont les suivantes :
les disques sont de diamètres différents
-
- on déplace un seul disque à la fois
- on n'a pas le droit de placer un disque de diamètre supérieur sur un de diamètre
inférieur.
Écrire l’algorithme de ce jeu et plus particulièrement la procédure récursive de déplacement
d’une pile de disques dep (nbdisq, init, final, intermed) où nbdisq est le nombre de disques à
déplacer, init est le numéro du tour où se trouvent ces disques, final est celui de la tour cible et
intermed est le numéro de la tour intermédiaire.
2