MyLeoNes™

Récursivité — Informatique, 14–17 ans

Comment résoudre un problème en créant une version plus petite du même problème, avec un point clair où le processus s’arrête.

Idée

La récursivité apparaît lorsqu’une fonction résout une tâche en s’appelant elle-même avec une donnée plus petite ou plus simple. Elle a aussi besoin d’un cas de base : une situation assez simple pour répondre directement. Chaque appel s’en approche, comme des boîtes emboîtées jusqu’à la dernière.

Pourquoi c’est important

Certains problèmes contiennent des copies plus petites d’eux-mêmes. Les dossiers contiennent des dossiers, les arbres généalogiques ont des branches et un labyrinthe peut contenir des sections à explorer. La récursivité décrit naturellement ces formes, car les mêmes instructions sont réutilisées au lieu d’écrire du code pour chaque profondeur.

Exemple guidé

Pour calculer 4 factorielle, on définit fact(1)=1 comme cas de base. Ensuite, fact(4)=4×fact(3), fact(3)=3×fact(2) et fact(2)=2×fact(1). En remplaçant de bas en haut, on obtient 2×1=2, 3×2=6 et 4×6=24 : donc 4!=24.

Piège courant

Une erreur compréhensible consiste à écrire l’appel à la fonction elle-même et à oublier le cas de base ou le pas qui y mène. Le code s’appelle alors sans fin, car l’ordinateur ne peut pas deviner quand la tâche est terminée. Même avec un cas de base, un mauvais pas peut faire grandir la donnée au lieu de la réduire.

Où cela apparaît

Les navigateurs, les outils de fichiers et les moteurs de recherche explorent souvent des dossiers imbriqués ou des pages liées avec des idées récursives. Un logiciel d’image peut aussi traiter une image en la divisant en petites régions, puis en les divisant encore. La même action s’applique à chaque niveau jusqu’à ce qu’une région soit assez petite.

Continue d'explorer

Autres langues

Chargement de MyLeoNes™…