12.1
Bases de la récursivité
Objectifs d'apprentissage
À la fin de cette section, vous devriez être capable de :
- Décrire le concept de récursivité.
- Démontrer comment la récursivité utilise des solutions simples pour construire une meilleure solution.
Récursivité
La récursivité (recursion) est une technique de résolution de problèmes qui utilise la solution d'une version plus simple du problème pour résoudre le problème plus vaste. À son tour, la même technique peut être appliquée à cette version simplifiée.
Concepts en pratique
Trois tours et récursivité
1.
Comment le problème du déplacement de deux anneaux est-il résolu en utilisant la récursivité ?
-
Déplacer le petit anneau vers la tour du milieu, déplacer le plus grand anneau vers la tour cible et déplacer le petit anneau vers la tour cible.
-
Déplacer deux anneaux de la tour source vers la tour cible.
-
Ne peut pas être résolu avec la récursivité.
2.
Comment le problème du déplacement de trois anneaux est-il résolu en utilisant la récursivité ?
-
Déplacer trois anneaux de la tour source vers la tour cible.
-
Déplacer deux anneaux vers la tour du milieu, puis déplacer le plus grand anneau vers la tour cible et enfin déplacer deux anneaux vers la tour cible.
-
Ne peut pas être résolu avec la récursivité.
3.
Combien de fois la solution à deux anneaux est-elle utilisée avec trois anneaux ?
-
1
-
2
-
0
La récursivité pour trouver une solution complète
Le processus de récursivité se poursuit jusqu'à ce que le problème soit suffisamment petit, moment auquel la solution est connue ou peut être facilement trouvée. La solution plus large peut ensuite être construite systématiquement en élaborant successivement des solutions de plus en plus grandes jusqu'à ce que le problème complet soit résolu.
Concepts en pratique
Résoudre les trois tours
4.
Combien d'étapes au total faut-il pour résoudre le problème à deux anneaux ?
-
1
-
2
-
3
5.
Combien d'étapes au total faut-il pour résoudre le problème à trois anneaux ?
-
3
-
4
-
7
6.
Combien d'étapes au total faut-il pour résoudre le problème à quatre anneaux ?
-
15
-
7
-
3