Récursivité, cours et problèmes corrigés
Le processus dans lequel une fonction appelle elle-même directement ou indirectement est appelée récursion et la fonction correspondante est appelée une fonction récursive.
En utilisant un algorithme récursif, certains problèmes peuvent être résolus assez facilement. Tours de Hanoi (TOH), traversées d’arbres en ordre / en pré-ordre / post-ordre, DFS du graphe, etc. sont des exemples de ces problèmes.
Par exemple, nous pouvons définir l'opération "trouver le chemin du retour" comme suit:
- Si vous êtes à la maison, arrêtez de bouger.
- Faites un pas.
- "trouve ton chemin à la maison".
Ici, la solution pour trouver votre chemin de retour est de deux étapes (en faite trois étapes). D'abord, nous ne rentrons pas à la maison si nous sommes déjà à la maison. Deuxièmement, nous faisons une action très simple qui rend notre situation plus simple à résoudre. Enfin, refaire l'ensemble de l'algorithme.
Parties d'un algorithme récursif
Tous les algorithmes récursifs doivent avoir les éléments suivants:
- Scénario de référence ou de base (c.-à-d. quand arrêter)
- Travailler vers le cas de base
- Appel récursif (c'est-à-dire appeler lui-mêmes)
Le "Travailler vers le cas de base" consiste à simplifier le problème (par exemple, diviser la liste en deux parties, chacune plus petite que l'originale).
L'appel récursif est l'endroit où nous utilisons le même algorithme pour résoudre une version plus simple du problème.
Le cas de base est la solution au problème "le plus simple" possible (par exemple, le cas de base du problème 'trouver le plus grand nombre dans une liste' serait si la liste ne comportait qu'un seul numéro ... et par définition s'il y avait un seul nombre, c'est le plus grand).
- Exercices corrigés sur les fonctions récursives -TD1-
- Exercices corrigés sur les fonctions récursives-TD2-
- Exercices corrigés sur les fonctions récursives-TD3-
- Exercices corrigés de récursivité en Python ( Série 12)
- Exercices corrigés sur la récursivité (TD 01)
- Exercices corrigés sur la récursivité (TD 02)
- Exercices corrigés sur la récursivité (TD 03)