Une fonction qui s'appelle elle-même

Une fonction qui s'appelle elle-même

La récursivité est une technique de programmation où une fonction s'appelle elle-même à l'intérieur de son propre corps, pour résoudre un problème en le décomposant en une version plus petite du même problème.

L'idée peut sembler étrange au premier abord : comment une fonction peut-elle s'appeler elle-même sans tourner indéfiniment ? La réponse tient dans le principe suivant : à chaque appel récursif, le problème traité doit être plus petit (plus proche d'être résolu), jusqu'à atteindre un cas suffisamment simple pour être résolu directement, sans nouvel appel.

Un exemple classique : calculer la factorielle d'un nombre n (notée n!), c'est-à-dire le produit de tous les entiers de 1 à n. Par définition mathématique :

# (n! = n multiplie par (n-1) multiplie par (n-2) ... multiplie par 1)
# (autrement dit : n! = n multiplie par (n-1)!)

Cette définition est déjà récursive : la factorielle de n se définit à partir de la factorielle de n moins 1. En Python, cela se traduit directement :

def factorielle(n):
    return n * factorielle(n - 1)

Mais attention : telle quelle, cette fonction ne s'arrête jamais ! Elle va appeler factorielle(n-1), qui va appeler factorielle(n-2), et ainsi de suite, sans fin, jusqu'à provoquer une erreur (dépassement de la profondeur d'appels autorisée). Il manque un ingrédient essentiel, que tu vas découvrir dans la prochaine leçon : le cas de base.