Récursivité — Informatique, 11–13
La récursivité résout un grand problème en appliquant la même règle à une version plus petite, jusqu’à atteindre un point d’arrêt simple.
Une règle qui s’appelle elle-même
Avec la récursivité, une instruction traite une partie, puis demande à la même instruction de traiter une partie plus petite. Elle doit aussi savoir quand s’arrêter : c’est le cas de base. Un dessin de branche montre l’idée : chaque branche se divise en branches plus petites, mais le plus petit rameau ne se divise plus.
Pourquoi utiliser la récursivité ?
Certaines choses sont faites de copies plus petites du même type : des dossiers contiennent des dossiers, les arbres généalogiques se divisent en branches et les cartes contiennent des régions dans des régions. Une longue liste d’instructions séparées serait difficile à écrire et à modifier. La récursivité répond au besoin de décrire ces structures emboîtées avec une seule règle claire, plutôt que de répéter du code semblable.
Compter à rebours
Utilise une règle appelée compte(n) : si n vaut 0, arrête-toi ; sinon, affiche n et appelle compte(n−1). Commence avec compte(3). Elle affiche 3, puis appelle compte(2), qui affiche 2 et appelle compte(1). Celle-ci affiche 1 et appelle compte(0) ; le cas de base arrête tout, donc le résultat final est 3, 2, 1.
Oublier l’arrêt
Une règle récursive peut sembler élégante ; il est donc tentant de la laisser s’appeler sans vérifier un cas de base. C’est une erreur compréhensible : on croit que les petites tâches finiront forcément par disparaître. Sans arrêt, pourtant, la valeur peut ne jamais atteindre la fin et l’ordinateur crée des appels inachevés jusqu’à manquer de place ou signaler une erreur.
Dossiers et formes ramifiées
Un explorateur de fichiers peut chercher dans un dossier, puis dans chaque dossier qu’il contient, même si l’imbrication est profonde. Les programmes de dessin utilisent aussi la récursivité pour des plantes ramifiées, des formes de flocon et des chemins de labyrinthe. Tu n’as pas besoin de récursivité pour toute action répétée ; elle est surtout utile quand chaque partie contient des parties plus petites de même structure.
Continue d'explorer
Autres langues
Chargement de MyLeoNes™…