La récursivité
Matière : INFO
Support : Exercice
Classe : MP2I
Année universitaire : 2024 - 2025
Exercice 1 : Trouver la somme maximale d'un chemin dans un triangle d'entiers
On vous donne un triangle d'entiers stocké dans un tableau à deux dimensions. Chaque
élément du triangle représente un nombre, et vous devez trouver la somme maximale possible
d'un chemin partant du sommet du triangle jusqu'à une des valeurs de la base. À chaque
étape, vous pouvez vous déplacer vers le bas à gauche ou vers le bas à droite dans le triangle.
Exemple d'entrée :
7
38
810
2744
45265
Le chemin avec la somme maximale est : 7 → 3 → 8 → 7 → 5, pour une somme de 30.
Exercice 2 :
Réécrire les fonctions suivantes en utilisant la récursivité, en adoptant une forme terminale
lorsque cela est possible.
int fct1(int n) { int fct2(int n) {
int S = 0; int a = 0;
for (int i = 1; i <= n; i++) { int b = 0;
S += i; for (int i = 1; i <= n; i++) {
} a += i;
return S; b += a;
} }
return b;
}
Exercice 3 : Palindrome
Un mot est un palindrome si on peut le lire dans les deux sens de gauche à droite et de droite
à gauche. Exemples : RADAR , KAYAK
Ecrire une fonction récursive permettant de vérifier si un mot est ou non un palindrome. Elle
doit renvoyer 1 ou 0
Exercice 4 : Multiplication récursive
La multiplication de deux entiers peut être réalisée à l’aide d’addition seulement.
Donner une fonction récursive permettant de multiplier deux entiers
Exercice 5 :
Soit la suite définie par :
a- Ecrire une fonction récursive « suite1 » permettant de déterminer le N ème terme de la
suite.
b- Ecrire une fonction récursive « suite2 » permettant de déterminer et de retourner
deux termes de la suite : le terme de rang N et le terme de rang (N-1).
c- En utilisant la fonction « Suite2 », écrire une fonction « Suite3 » permettant de calculer
le Nème terme de la suite.
Exercice 6 : Problème du Cavalier (Knight's Tour)
Écrivez une fonction récursive qui résout le problème du cavalier (Knight's Tour) sur un
échiquier de taille 8x 8. Le but est de déplacer un cavalier (une pièce du jeu d'échecs) sur
l'échiquier de manière qu'il visite chaque case exactement une fois.
Contraintes :
1. Le cavalier peut se déplacer en "L", c'est-à-dire deux cases dans une direction et une
case perpendiculaire, ou une case dans une direction et deux cases perpendiculaires.
2. Vous devez utiliser une approche de backtracking (la case revient non visitée si le
chemin ne mène pas à une solution) pour explorer toutes les possibilités de
mouvements.
3. La solution doit imprimer l'ordre des visites du cavalier sur l'échiquier, où chaque case
doit être marquée par le numéro de son ordre de visite
