La récursivité : résoudre un problème avec des versions plus petites de lui-même — Technologie, 14–17 ans
La récursivité permet à un programme de répéter une idée en se rappelant sur un cas plus petit. Il doit aussi savoir quand s’arrêter, sinon le processus ne finit jamais.
Une version plus petite du même problème
Imagine ouvrir des boîtes emboîtées : dans chacune se trouve une boîte plus petite, jusqu’à la dernière, qui est vide. Un programme récursif fait quelque chose de semblable en résolvant une version plus petite de sa tâche. Il lui faut un cas de base qui donne une réponse directe.
Pourquoi utiliser la récursivité ?
Certains problèmes ont déjà une forme ramifiée ou imbriquée : des dossiers contiennent des dossiers, des pages renvoient vers d’autres pages et les arbres généalogiques se divisent en branches. La récursivité suit cette forme et peut être plus claire qu’une longue liste de cas particuliers.
Exemple guidé : la factorielle
Pour calculer 4!, on définit 1! comme égal à 1, puis on utilise n! = n × (n−1)!. Ainsi, 4! devient 4 × 3!, puis 4 × 3 × 2!, puis 4 × 3 × 2 × 1!, soit 24. Le cas de base 1! arrête la chaîne.
Le point d’arrêt oublié
Une erreur courante consiste à écrire l’appel à soi-même en oubliant le cas de base, ou à modifier si peu la valeur qu’il n’est jamais atteint. C’est compréhensible, car l’étape répétée semble être l’idée principale. Le résultat est souvent un dépassement de pile : trop d’appels restent ouverts.
Où la trouve-t-on ?
Les explorateurs de fichiers peuvent chercher dans des dossiers placés dans d’autres dossiers, et les logiciels de dessin peuvent créer des formes ramifiées comme des arbres ou des flocons. Ces tâches sont imbriquées, donc la récursivité les décrit naturellement. Elle n’est pas toujours la plus rapide : une méthode itérative peut utiliser moins de mémoire.
Continue d'explorer
Autres langues
Chargement de MyLeoNes™…