CoursAvancé11 min de lecture

La récursion - quand une fonction s'appelle elle-même

Dessiner des fractales (arbres, flocons, Sierpiński) en quelques lignes avec une technique mentalement vertigineuse

§1.Une idée bizarre mais puissante

La récursion, c'est quand une fonction S'APPELLE ELLE-MÊME. Oui, tu as bien lu : dans le corps de la fonction, tu mets un appel à la même fonction. Sur le papier, ça a l'air d'un truc impossible — comme un serpent qui se mord la queue. En pratique, c'est une des techniques les plus élégantes de la programmation.

Pourquoi ça ne plante pas l'ordinateur ? Parce qu'il y a TOUJOURS une CONDITION D'ARRÊT : un cas de base où la fonction ne se rappelle PAS. Sans ça, oui, ça boucle à l'infini et ça plante.

La récursion est parfaite pour dessiner des FRACTALES : des formes dont chaque petite partie ressemble au tout. Un arbre se décompose en deux branches, chaque branche en deux branches plus petites, et ainsi de suite. Une fonction récursive exprime ça naturellement.

Premier exemple : compte à rebours

Avant de dessiner, regardons la récursion sur un exemple SANS dessin pour comprendre le principe.

javascript

1function compter(n) {
2  // Cas de base : on arrête quand n atteint 0
3  if (n === 0) return
4 
5  // Sinon : on dessine un petit trait
6  avancer(n * 3)
7  tourner_droite(90)
8 
9  // Et on s'appelle nous-même avec n - 1
10  compter(n - 1)
11}
12 
13compter(20)

Résultat : 20 traits de longueurs décroissantes, formant une spirale carrée qui rétrécit.

À chaque appel, n diminue de 1. Quand n atteint 0, on renvoie sans appeler à nouveau : c'est le cas de base. Sans ce return, la fonction continuerait à s'appeler à l'infini.

§3.Anatomie d'une fonction récursive

Le cas de base: La condition qui dit « arrête-toi, ne te rappelle pas ». Sans elle, récursion infinie = crash.; Exemple. if (taille < 5) return — si la taille devient trop petite, on s'arrête.
L'appel récursif: La fonction s'appelle avec des paramètres PLUS PETITS ou PLUS PROCHES du cas de base. C'est ce qui garantit qu'on finira par s'arrêter.; Exemple. branche(taille * 0.7) — chaque appel réduit la taille de 30%.
Avant vs après l'appel récursif: Ce qui se trouve AVANT l'appel récursif se fait à la descente. Ce qui est APRÈS se fait au retour, dans l'ordre inverse. Subtil et puissant.

§4.L'arbre fractal

Maintenant, le grand classique : un arbre. Un tronc, qui se divise en deux sous-branches, qui se divisent elles-mêmes en deux sous-sous-branches, etc.

La fonction branche(taille) avance, dessine deux sous-branches plus petites en orientant à gauche puis à droite, puis revient à la base.

Arbre fractal

javascript

1function branche(taille) {
2  if (taille < 10) return       // cas de base
3 
4  avancer(taille)
5  tourner_droite(25)
6  branche(taille * 0.7)          // sous-branche droite
7  tourner_gauche(50)
8  branche(taille * 0.7)          // sous-branche gauche
9  tourner_droite(25)
10  reculer(taille)                // retour à la base
11}
12 
13aller_a(0, -150)
14orienter(0)
15branche(80)

Résultat : Un arbre stylisé qui se ramifie à chaque niveau.

§7.Comprendre la pile d'appels

Imagine que tu poses branche(80) sur un papier. La fonction démarre, avance de 80, tourne à droite, PUIS elle s'appelle avec branche(56). Pendant ce nouvel appel, le premier branche(80) est en PAUSE — il attend que branche(56) finisse pour continuer.

branche(56) à son tour s'appelle avec branche(39.2). Et ainsi de suite, jusqu'à ce que taille descende sous 10 (le cas de base). À ce moment-là, on remonte progressivement : branche(13.7) finit, puis branche(19.6), etc., jusqu'à ce que le premier branche(80) puisse terminer.

L'ordinateur garde la trace de tous ces appels en attente dans une PILE (call stack). Quand tu écris une récursion mal conçue, la pile déborde — c'est la fameuse erreur « Maximum call stack size exceeded ».

§8.Le triangle de Sierpiński

Encore plus spectaculaire : un triangle composé de 3 triangles plus petits, chacun composé de 3 triangles encore plus petits…

Triangle de Sierpiński

javascript

1function triangle(taille) {
2  for (let i = 0; i < 3; i++) {
3    avancer(taille)
4    tourner_gauche(120)
5  }
6}
7 
8function sierp(taille, niveau) {
9  if (niveau === 0) {
10    triangle(taille)
11    return
12  }
13  // Trois petits Sierpinski aux trois coins
14  sierp(taille / 2, niveau - 1)
15  avancer(taille / 2)
16  sierp(taille / 2, niveau - 1)
17  reculer(taille / 2)
18  tourner_gauche(60)
19  avancer(taille / 2)
20  tourner_droite(60)
21  sierp(taille / 2, niveau - 1)
22  tourner_gauche(60)
23  reculer(taille / 2)
24  tourner_droite(60)
25}
26 
27aller_a(-130, -100)
28orienter(90)
29sierp(260, 4)

Résultat : Un triangle de Sierpiński avec 81 petits triangles (3 puissance 4).

Le paramètre niveau contrôle la profondeur. Niveau 0 = un seul triangle. Niveau 1 = 3 triangles. Niveau N = 3^N triangles. À niveau 4, on a déjà 81 triangles.

§10.Quand utiliser la récursion ?

Fractales et auto-similarité: Arbre, flocon de Koch, Sierpiński, Mandelbrot — tout ce qui se décompose en versions plus petites de lui-même.
Structures hiérarchiques: Arbres généalogiques, dossiers/fichiers, menus imbriqués. Naturellement récursifs.
Algorithmes diviser-pour-régner: Découper un gros problème en sous-problèmes plus petits, traiter chaque sous-problème de la même façon, combiner les résultats. Tri rapide, tri fusion, recherche dichotomique.

§12.Récursion vs boucle

Beaucoup de problèmes peuvent se résoudre avec une boucle OU avec une récursion. Comment choisir ?

RÉCURSION : quand le problème se décompose naturellement en sous-problèmes identiques plus petits (fractales, arbres). Le code est souvent plus court et plus élégant.

BOUCLE : quand tu fais juste « répéter N fois » sans hiérarchie. Plus efficace en mémoire (pas de pile à empiler).

Avec l'expérience, tu sentiras laquelle est plus naturelle. Et tu peux toujours convertir l'une en l'autre.

§14.La fin du parcours

Bravo ! Tu as parcouru les 6 chapitres : commandes de base, boucles, variables, conditions, fonctions, récursion. C'est exactement les briques que tu retrouveras dans n'importe quel langage de programmation (JavaScript, Python, C, Java…). La syntaxe change, les concepts restent.

Maintenant, va dans l'atelier de code ou de blocs, ouvre la galerie d'inspiration, et essaie de reproduire chaque dessin par toi-même. Quand tu bloques, demande à l'assistant. C'est en codant que tu apprends, pas en lisant.

À retenir

Une fonction récursive s'appelle elle-même avec des paramètres plus petits.
Toujours un CAS DE BASE qui arrête la récursion — sinon, plantage.
L'appel récursif doit se rapprocher progressivement du cas de base.
Ce qui est AVANT l'appel récursif se fait à l'aller, ce qui est APRÈS au retour.
Parfait pour les fractales (arbre, Koch, Sierpinski) — auto-similarité.
Toute récursion peut s'écrire avec une boucle, mais c'est souvent moins lisible.