Comprendre la récursivité : comment fonctionne l'un des sujets les plus mystérieux de la programmation

Si vous avez déjà regardé une fonction récursive et que vous avez eu l'impression d'être tombé dans un reflet infini dans un miroir, bienvenue ! Cet article est pour toi. Aujourd'hui, nous allons mettre la récursivité sur les étagères. Simple, amusant, facile à comprendre et avec plein d'exemples. Allons-y ! 🚀

🔎 Qu'est-ce que la récursion, en termes humains ?

La récursion, c'est quand une fonction s'appelle elle-même (pas de panique !). Cela est nécessaire pour résoudre le problème en le divisant en sous-tâches plus petites. Cela se répète jusqu'à ce que nous atteignons le soi-disant cas de base — points d'arrêt.

🎭 Imaginez une réflexion infinie entre deux miroirs. Vous, puis un peu moins vous, puis un tout petit peu — et ainsi de suite. C'est ça la récursion. Seulement au lieu de réflexions, il y a des appels de fonctions. De plus, chacun de ces appels est un peu plus simple que le précédent, jusqu'à ce que nous arrivions à celui que même une théière peut gérer (je veux dire, une fonction théière !).

📦 Ou un autre exemple : imaginez une boîte dans une boîte, et une autre boîte dedans, et ainsi de suite jusqu'à ce que vous atteigniez la dernière, la plus petite. En programmation, cette dernière boîte est notre cas de base. C'est tout, il n'y a plus rien à « déballer », il est temps de récupérer le résultat.

📌 Exemple 1 : la factorielle est la favorite des récursions

Factorielle les nombres n (désignés par n!) sont le produit de tous les nombres de 1 à n.

Exemple :

5! = 5 × 4 × 3 × 2 × 1 = 120

Implémentation récursive en Python :

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

Chaque appel réduit n jusqu'à ce que nous atteignons 1 ou 0, puis la fonction commence à renvoyer le résultat. C'est très similaire à une descente de colline avec un retour en arrière dans les escaliers.

📌 Exemple 2 : somme des nombres jusqu'à n

Et maintenant, additionnons tous les nombres de 1 à n :

def sum_to(n):
    if n == 1:
        return 1
    else:
        return n + sum_to(n - 1)

Appel sum_to(5):

sum_to(5)
= 5 + sum_to(4)
= 5 + (4 + sum_to(3))
= 5 + (4 + (3 + sum_to(2)))
= 5 + (4 + (3 + (2 + sum_to(1))))
= 5 + 4 + 3 + 2 + 1 = 15

C'est ça, la magie de la récursion : le problème est « réduit » à un problème compréhensible, puis « plié » en réponse.

📌 Exemple 3 : compte à rebours (et compétence utile)

def countdown(n):
    if n == 0:
        print("Let's go!")
    else:
        print(n)
        countdown(n - 1)

Lancez countdown(5) et vous verrez :

5
4
3
2
1
Поехали!

La récursion ne doit pas toujours renvoyer des valeurs, elle peut simplement effectuer des actions. C'est une excellente façon de commencer à l'utiliser !

🧨 Les erreurs que presque tout le monde fait (et comment les éviter)

1. ❌ Vous avez oublié le cas de base — et bonjour à la récursion infinie. Vérifiez où la fonction doit s'arrêter.

2. ❌ Condition incorrecte — par exemple, if n == 0 au lieu de n <= 0, et vous êtes de nouveau parti à l'infini.

3. ❌ La récursivité là où il est plus facile de s'en passer — demandez-vous toujours : « Ai-je vraiment besoin de récursivité ici ? »

🌟 Quand la récursion règne vraiment

La récursion est pratique lorsque :

• Il faut contourner structures imbriquées, par exemple des dossiers ou JSON.

• Tâche se divise naturellement en parties (par exemple, tri, arbre de recherche).

• Il faut essayer tous les chemins - idéal pour trouver des solutions dans les puzzles (labyrinthe, sudoku, etc.).

📈 Inconvénients de la récursivité (pas de panique, soyez simplement conscient de leur existence)

• Chaque appel récursif est une mémoire supplémentaire (pile d'appels).

• Plusieurs niveaux → la pile est pleine (surtout en Python).

• Fonctionne plus lentement que les cycles normaux s'il n'est pas optimisé.

✨ Comment se lier d'amitié avec la récursivité pour toujours

1. ✏️ Dessinez — arbre d'appels, pile, séquence d'actions.

2. 🎮 Entraîne-toi - résoudre des problèmes, même les plus simples : factorielle, somme, ligne dans l'ordre inverse.

3. 🔍 Suivre l'exécution - étape par étape, avec print() ou dans le débogueur.

4. 🧪 Comparer avec les cycles — écrivez les deux versions pour voir les avantages et les inconvénients.

🧪 Exemple 4 : renversement de ligne

def reverse_string(s):
    if len(s) == 0:
        return ""
    return s[-1] + reverse_string(s[:-1])

reverse_string("Code") → "kidoK"

Ainsi, vous pouvez retourner les lignes, et de manière élégante et compréhensible.

🎬 Résumons

La récursion est :

• une méthode pour diviser une tâche en étapes simples ;

• fonction qui s'appelle elle-même jusqu'à ce que la condition de base soit atteinte ;

• la magie que vous pouvez apprivoiser.

Si vous ne comprenez toujours pas complètement, relisez l'article. C'est aussi une récursion 😉