Exercices de Programmation en Lisp
Récursion Naïve - Niveau Débutant
Introduction
Ces exercices vous permettront de pratiquer la récursion naïve en Lisp. La récursion
naïve consiste à résoudre un problème en le divisant en sous-problèmes plus simples,
jusqu’à atteindre un cas de base.
Rappels de syntaxe Lisp
En Lisp, une fonction se définit avec defun. Exemple :
(defun nom-fonction (param1 param2)
corps-de-la-fonction)
Exercices
1. Factorielle
Écrivez une fonction factorielle qui calcule la factorielle d’un nombre n.
Rappel : n! = n × (n-1) × (n-2) × ... × 1, et 0! = 1.
Exemple :
(factorielle 5) => 120
(factorielle 0) => 1
2. Somme des n premiers entiers
Écrivez une fonction somme qui calcule la somme des entiers de 1 à n : somme(n) = 1
+ 2 + 3 + ... + n.
Exemple :
(somme 5) => 15
(somme 10) => 55
3. Puissance
Écrivez une fonction puissance qui calcule x élevé à la puissance n (x^n). Par exemple
: 2^3 = 8.
Exemple :
(puissance 2 3) => 8
(puissance 5 0) => 1
4. Longueur d’une liste
Écrivez une fonction longueur qui calcule le nombre d’éléments dans une
liste. Utilisez les fonctions car (premier élément) et cdr (reste de la liste).
Exemple :
(longueur ’(1 2 3 4)) => 4
(longueur ’()) => 0
5. Somme d’une liste
Écrivez une fonction somme-liste qui additionne tous les éléments d’une liste
de nombres.
Exemple :
(somme-liste ’(1 2 3 4 5)) => 15
(somme-liste ’()) => 0
6. Maximum d’une liste
Écrivez une fonction maximum qui trouve le plus grand élément d’une liste de
nombres.
Exemple :
(maximum ’(3 1 4 1 5 9 2)) => 9
7. Inverser une liste
Écrivez une fonction inverser qui inverse l’ordre des éléments d’une
liste.
Exemple :
(inverser ’(1 2 3 4)) => (4 3 2 1)
8. Nombre de Fibonacci
Écrivez une fonction fibonacci qui calcule le n-ième nombre de Fibonacci. La suite de
Fibonacci est : 0, 1, 1, 2, 3, 5, 8, 13...
Exemple :
(fibonacci 6) => 8
(fibonacci 0) => 0
Indices et Conseils
Structure générale d’une fonction récursive :
(defun ma-fonction (n)
(if (cas-de-base? n)
valeur-de-base
(operation n (ma-fonction (sous-probleme n)))))
Conseils :
1. Identifiez toujours le cas de base (condition d’arrêt)
2. Définissez comment réduire le problème à un sous-problème plus simple
3. Utilisez if ou cond pour tester les conditions
4. Pour les listes, testez si elle est vide avec (null liste)
Exemple de solution : Factorielle
(defun factorielle (n)
(if (<= n 1)
1 ; cas de base
(* n (factorielle (- n 1))))) ; cas récursif
Explication :
• Cas de base : si n ≤ 1, retourner 1
• Cas récursif : multiplier n par la factorielle de (n-1)
• L’appel récursif réduit toujours le problème (n-1 est plus petit que n)