À propos de cette expérience
Un arbre est un tronc surmonté de deux arbres plus petits. Cette seule phrase constitue un programme complet : une fonction qui dessine une branche, puis s’appelle elle-même deux fois. La récursion transforme de courtes règles en images riches. Observe la construction, appel après appel, d’un arbre, d’un triangle de Sierpiński et d’un flocon de Koch ; suis les variations de la pile d’appels, qui grandit puis rétrécit, et compte à quelle vitesse le nombre d’appels explose lorsque la profondeur augmente.
Objectifs pédagogiques
- Identifier le cas de base et le cas récursif d’une fonction récursive
- Suivre l’ordre dans lequel les appels récursifs s’exécutent et retournent
- Expliquez ce que contient la pile d’appels et pourquoi sa profondeur est importante
- Calculez le nombre d’appels pour une profondeur donnée, par exemple 2^(n+1) − 1 pour un arbre binaire
- Décrivez l’autosimilarité et calculez une dimension fractale simple
Comment l’utiliser
- 1Choisissez l’arbre de profondeur 3 et observez les appels lentement. Quelle branche est dessinée en premier : la gauche ou la droite ? Pourquoi ?
- 2Mettez en pause lorsque la pile atteint sa profondeur maximale. Que représente chaque cadre de la pile ? Combien y a-t-il de cadres par rapport à la profondeur ?
- 3Remplissez un tableau indiquant la profondeur et le nombre d’appels pour l’arbre. Trouvez la règle et vérifiez-la à la profondeur 10.
- 4Modifiez l’angle des branches et le rapport de longueur. Quels réglages font se chevaucher les branches ?
- 5Passez au triangle de Sierpinski. Où se trouve le cas de base dans le code ? Combien de triangles sont dessinés à la profondeur 5 ?
- 6Construisez le flocon de Koch à la profondeur 5. Utilisez les valeurs affichées pour expliquer comment le périmètre peut continuer à croître alors que l’aire reste limitée.
Le modèle
Hypothèses
- Les appels s’exécutent un par un, dans l’ordre du programme et en profondeur, exactement comme dans un langage de programmation ordinaire.
- Le pseudocode transmet les positions et les directions comme paramètres ; il n’est donc pas nécessaire de rétablir l’état de la tortue lorsqu’un appel se termine.
- La dimension fractale de l’arbre, log 2 / log(1/r), ne décrit que les extrémités lorsque les branches ne se chevauchent pas.
- Les profondeurs maximales sont limitées afin que la relecture pas à pas reste rapide : 12 pour l’arbre, 7 pour le triangle et 6 pour le flocon.
À essayer en classe
- Q1Que se passerait-il si la fonction de l’arbre n’avait pas de cas de base ?
- Q2Combien d’appels la fonction de Sierpinski effectue-t-elle à la profondeur 4 ? Expliquez votre réponse à l’aide d’une somme.
- Q3Pourquoi la pile d’appels ne dépasse-t-elle jamais une profondeur égale à la profondeur de récursion plus un, même si des milliers d’appels sont effectués ?
- Q4Écrivez une fonction récursive qui calcule n! et identifiez son cas de base.
- Q5Le littoral de la Grande-Bretagne semble d’autant plus long que la règle utilisée pour le mesurer est courte. Comment le flocon de Koch explique-t-il ce phénomène ?
Foire aux questions
La récursion est-elle plus lente qu’une boucle ?
Chaque appel consomme un peu de temps et de mémoire pour son cadre de pile, si bien qu’une boucle est souvent légèrement plus rapide. Mais pour les structures ramifiées comme les arbres, les dossiers imbriqués ou l’analyse syntaxique, la récursion est beaucoup plus simple à écrire, et toute récursion peut être réécrite à l’aide d’une pile explicite que l’on gère soi-même.
Qu’est-ce qu’un débordement de pile ?
Chaque appel inachevé conserve un cadre dans la pile d’appels. Si la récursion devient trop profonde, par exemple parce que le cas de base n’est jamais atteint, la pile manque de mémoire et le programme plante avec une erreur de débordement de pile.
Où trouve-t-on des fractales dans la nature ?
Les fougères, le chou romanesco, les réseaux fluviaux, les éclairs, les vaisseaux sanguins et les ramifications des voies respiratoires des poumons sont approximativement autosimilaires à plusieurs échelles. C’est pourquoi on utilise des règles récursives pour les générer en infographie.