Cours sur la récursivité

Page 1
Introduction
Page 2
I. Boucles
I-A. Transformer une boucle en une procédure récursive
I-B. Transformer deux boucles imbriquées en une procédure récursive
I-C. Calculer la factorielle d'un entier
I-D. Remplir un carré en diagonale
I-E. Sources des exemples
Page 3
II. Les chaînes
II-A. L'inversion d'une chaîne de caractères
Evaluation d'un nombre écrit en chiffres romains
II-C. Palindromes
II-D. Evaluation d'une chaîne de caractères formée d'une somme de nombres
II-E. Vers une mini-calculatrice
II-F. Anagrammes
Page 4
III. Les échecs
III-A. Le parcours du fou
III-B. Le problème du cavalier
III-C. Le problème des huit reines
Page 5
IV. Divers
IV-A. Le triangle de Pascal
IV-B. Les tours de Hanoï
IV-C. La maison
IV-D. Le labyrinthe
IV-E. Les petits chiens
IV-F. Le solitaire
IV-G. Le compte est bon
IV-H. Génération récursive de courbes fractales
IV-I. Quick sort
IV-J. Décompositions en sommes de carrés
IV-K. Remplissage de volumes
IV-L. Le métro
IV-M. Ecrire un nombre en toutes lettres
Page 6
V. Contraintes
V-A. Le problème d'Einstein
V-B. Les quatre musiciens
Page 7
VI. Récursivité croisée
VI-A. Suites à récurrence double
VI-B. Tri bulle boustrophédon
Page 8
VII. Les arbres
VII-A. Les arbres binaires
VII-A-1. Affichage d'un arbre
VII-A-2. Ajout d'un noeud dans un arbre
VII-A-3. Comptage des noeuds d'un arbre
VII-A-4. Comptage des niveaux d'un arbre
VII-A-5. Equilibrage d'un arbre
VII-A-6. Comparaison de deux arbres
VII-A-7. Source de l'exemple
VII-B. Le code Morse
VII-C. Évaluation d'une expression arithmétique
VII-C-1. La structure d'arbre binaire
VII-C-2. Comment évaluer un arbre binaire
VII-C-3. Comment construire l'arbre binaire
VII-C-4. Automate de validation d'une expression arithmétique
VII-C-5. Source de l'exemple
VII-D. Les arbres n-aires : codage d'un dictionnaire
VII-D-1. Structure des données
VII-D-2. La procédure d'ajout d'un mot
VII-D-3. La procédure de chargement d'un fichier
VII-D-4. Comptage des noeuds terminaux
VII-D-5. Affichage graphique d'un arbre n-aire
VII-D-6. Affichage de texte (création d'une liste de mots du dictionnaire)
VII-D-7. Recherche d'un mot dans l'arbre
VII-D-8. Source de l'exemple
Page 9
VIII. Dérécursification
VIII-A. Dérécursification de la procédure de Fibonacci
VIII-B. La dérécursification des structures de données
VIII-C. Dérécursification du triangle de Pascal
VIII-D. Dérécursification des "tours de Hanoï"
VIII-D-1. Préliminaire
VIII-D-2. Détermination du type du k-ième mouvement
VIII-D-3. Détermination du sens du déplacement : "A" ou "a" ?
VIII-D-4. Résumé
VIII-D-5. Conclusion
VIII-D-6. Source de l'exemple
VIII-E. Dérécursification des « nombres en lettres »
Page 10
IX. Les jeux de réflexion
IX-A. Le morpion à trois pions
IX-B. Le jeu d'Othello