La récursion est une technique de programmation spéciale où une fonction s'appelle elle-même pour résoudre un problème.
Au début, cette idée peut sembler un peu magique — ou un peu étrange — mais c'est un outil très puissant une fois que vous la comprenez.

Pensez-y comme regarder dans deux miroirs face à face. Vous voyez un reflet dans un reflet, qui continue à l'infini… jusqu'à ce qu'il s'estompe finalement. En récursion, cet « estompage » est crucial — on l'appelle le cas de base, et c’est ce qui arrête la répétition.

Comment fonctionne la récursion

Une fonction récursive :

1. Vérifie si elle doit s’arrêter — c’est le cas de base.
2. Sinon, elle s’appelle elle-même, mais avec une version plus petite ou plus simple du problème original.

En décomposant un problème en morceaux plus petits de manière répétée, la récursion atteint la version la plus simple possible du problème, la résout, puis reconstruit la réponse en remontant de tous les appels.

Exemple : Calcul du factoriel

Prenons le factoriel d’un nombre.
En mathématiques, le factoriel de n (noté n!) signifie :

n! = n × (n-1) × (n-2) × ... × 1

Par exemple :

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

Voici la version récursive en Python :

def factorial(n):
    if n == 0:  # cas de base
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # 120

Ce qui se passe ici :

• Si n est 0, on a atteint le cas de base — par définition, 0! vaut 1.
• Sinon, on multiplie n par factorial(n - 1) (une version plus petite du même problème).
• Cela se répète jusqu’à atteindre le cas de base.

Pourquoi utiliser la récursion ?

La récursion peut être :

• Élégante et concise pour les problèmes naturellement répétitifs dans leur structure.
• Parfaite pour les problèmes mathématiques (factoriels, nombres de Fibonacci).
• Essentielle pour naviguer dans des données en forme d’arbre (systèmes de fichiers, arbres généalogiques, recherche en IA de jeu).

Parfois, la récursion peut même remplacer des boucles, bien que ce ne soit pas toujours l’option la plus efficace.

ASTUCE : La récursion est souvent plus facile à comprendre quand on la voit comme « diviser le problème en versions plus petites de lui-même jusqu’à pouvoir le résoudre directement ».

Pièges courants

IMPORTANT ! : Toujours définir un cas de base — sans cela, la fonction s’appellera indéfiniment jusqu’à ce que Python génère une RecursionError.

Dépannage :

• « RecursionError : maximum recursion depth exceeded » → Vous n’avez pas atteint le cas de base ou votre cas de base est incorrect.
• Si la récursion semble trop complexe pour le problème, essayez une boucle à la place.

La récursion peut sembler déconcertante au début, mais c’est simplement une autre façon de rendre votre code plus intelligent et adaptable. Après l’avoir pratiquée avec quelques problèmes, vous verrez qu’elle n’est pas seulement puissante, mais peut aussi rendre votre code surprenamment court et élégant.