La récursivité en Python : Concepts, exemples et conseils

La récursivité est un concept fondamental en programmation, et elle revêt une importance particulière en Python. Il s'agit de la technique selon laquelle une fonction s'appelle elle-même pour résoudre un problème, en le décomposant en sous-problèmes plus petits et plus faciles à gérer. 

Cette méthode permet de trouver des solutions élégantes et concises, en particulier lorsqu'il s'agit de problèmes impliquant des tâches répétitives ou des structures hiérarchiques. En Python, la récursivité est utilisée dans une grande variété d'applications, du tri aux de tri à l'exploration de données complexes.

Les solutions récursives reflètent souvent les définitions mathématiques des problèmes, ce qui les rend intuitives pour les personnes familiarisées avec le raisonnement mathématique. La beauté de la récursivité réside dans sa capacité à exprimer des algorithmes complexes en quelques lignes de code seulement, créant ainsi des solutions à la fois élégantes et lisibles. Cependant, la maîtrise de la récursivité nécessite un changement de mentalité par rapport aux approches itératives les plus courantes.

Dans cet article, je vais explorer le concept de récursion, son fonctionnement en Python et ses applications pratiques, y compris une discussion des problèmes courants et des comparaisons avec l'itération. Si vous êtes novice en matière de Python, envisagez de suivre l'un de nos cours, tels que Introduction à Python, Concepts de paradigme de programmationou Principes de base de la programmation Python.

Qu'est-ce que la récursivité en Python ?

En Python, la récursivité fait référence à une fonction qui s'appelle elle-même pour résoudre un problème. Il comporte deux éléments essentiels :

• Cas de base: C'est la condition qui met fin à la récursivité. Sans cela, les appels récursifs se poursuivraient indéfiniment, entraînant finalement le blocage de la fonction ou l'épuisement de la mémoire disponible.
• Cas récursif: Cette partie de la fonction consiste à décomposer le problème en plusieurs parties et à rappeler la fonction avec ces parties.

Voici une façon simple de penser à la récursion : imaginez une fonction qui résout un problème complexe en résolvant des versions plus petites du même problème, pour finalement parvenir à une solution qui ne nécessite pas de récursion supplémentaire.

L'approche récursive suit la stratégie "diviser pour régner", en décomposant les problèmes complexes en versions plus simples jusqu'à ce que l'on parvienne à un cas trivial. Cette approche reflète souvent la façon dont nous pensons naturellement à résoudre les problèmes. Par exemple, lorsque vous triez un jeu de cartes, vous pouvez naturellement trier des groupes plus petits, puis les combiner, ce qui est essentiellement la façon dont les algorithmes de tri récursif tels que tri par fusion fonctionnent.

Toute fonction récursive doit avoir au moins un cas de base et au moins un cas récursif. Le cas de base permet d'éviter la récursivité infinie en fournissant une condition qui ne nécessite pas d'autres appels de fonction. Le cas récursif réduit la taille du problème à chaque appel, garantissant que le cas de base est finalement atteint.

Comment fonctionne la récursivité en Python ?

La récursivité permet à une fonction de s'appeler elle-même avec des arguments modifiés, ce qui permet de résoudre progressivement le problème par petites étapes. Pour comprendre cela plus concrètement, considérez la tâche consistant à calculer la somme des nombres compris entre 1 et num.

Voici une approche récursive simple pour calculer la somme :

def sum_recursive(num):
    if num == 1:  # Base case
        return num
    return num + sum_recursive(num - 1)  # Recursive case

print(sum_recursive(3)) # 3 + 2 + 1 

6

Dans cette fonction, le cas de base est lorsque num == 1, ce qui arrête la récursivité. Sinon, la fonction s'appelle elle-même à l'adresse num - 1 jusqu'à ce qu'elle atteigne le cas de base.

Comment ça marche, étape par étape :

1. sum_recursive(3) appelle sum_recursive(2).
2. sum_recursive(2) appelle sum_recursive(1).
3. sum_recursive(1) rend 1 (cas de base).
4. Maintenant, sum_recursive(2) peut renvoyer 2 + 1 = 3, et sum_recursive(3) peut renvoyer 3 + 3 = 6.

Un autre exemple serait une fonction récursive permettant de calculer la puissance d'un nombre :

def power(base, exponent):
    if exponent == 0:  # Base case
        return 1
    else:
        return base * power(base, exponent - 1)  # Recursive case

print(power(2, 3))

8

Explication pas à pas de cette fonction de puissance :

• power(2, 3) appelle power(2, 2).
• power(2, 2) appelle power(2, 1).
• power(2, 1) appelle power(2, 0).
• power(2, 0) rend 1 (cas de base).
• Maintenant, si l'on travaille à l'envers : power(2, 1) renvoie à 2 * 1 = 2.
• Ensuite, power(2, 2) renvoie 2 * 2 = 4.
• Enfin, power(2, 3) renvoie 2 * 4 = 8.

Lorsqu'une fonction récursive est appelée, chaque appel récursif crée une nouvelle entrée sur la pile d'appels. Ce cursus garde la trace de tous les appels de fonctions et de leurs variables. Lorsque le cas de base est atteint, la pile commence à résoudre chaque appel dans l'ordre inverse, en calculant le résultat final étape par étape.

La compréhension de ce comportement de la pile est cruciale car elle explique à la fois la puissance et les limites de la récursivité en Python. Elle préserve élégamment le contexte, mais peut également entraîner des problèmes de mémoire en cas de récursion profonde.

Implémentation de la factorielle en Python à l'aide de la récursivité

La fonction factorielle est un exemple classique utilisé pour démontrer la récursivité. La factorielle d'un nombre n, noté n!, est le produit de tous les entiers positifs inférieurs ou égaux à n. Mathématiquement :

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

De manière récursive, la fonction factorielle peut être définie comme suit :

n ! = n × (n - 1) !

Mettons cela en œuvre en Python :

def compute_factorial(num):
    if num == 0:  # Base case
        return 1
    return num * compute_factorial(num - 1)  # Recursive case

print(compute_factorial(4)) # 4 * 3 * 2 * 1

24

Explication du code étape par étape :

• La fonction compute_factorial(num) vérifie si num == 0 et renvoie 1 dans ce cas.
• Sinon, elle renvoie num * compute_factorial(num - 1), où la fonction s'appelle elle-même avec une valeur plus petite de num.

La fonction factorielle illustre parfaitement l'élégance de la récursivité. La définition mathématique elle-même est récursive, ce qui rend la mise en œuvre du code intuitive et étroitement liée au concept mathématique. C'est l'une des forces de la récursivité, qui permet au code d'exprimer directement des définitions mathématiques.

Il convient de noter qu'il existe des cas limites à prendre en considération. Par exemple, la factorielle n'est généralement définie que pour les entiers non négatifs. Une implémentation robuste pourrait inclure une gestion des erreurs pour les entrées négatives ou une vérification de type. 

En outre, pour de grandes valeurs de num, la solution récursive peut conduire à un dépassement de pile, ce qui constitue une limitation que je discuterai plus en détail.

Questions communes : Comment corriger les erreurs de récursivité en Python

Bien que la récursivité soit un outil puissant, elle est sujette à quelques problèmes courants, tels que :

Dépassement de la profondeur maximale de récursion

Python a une limite de récursivité par défaut de 1000 appels. Si une fonction récursive s'appelle elle-même trop de fois, un message RecursionError sera émis.

Voici comment y remédier :

Vous pouvez augmenter la profondeur de récursion en utilisant sys.setrecursionlimit(). Toutefois, cela n'est pas recommandé, sauf en cas de nécessité, car cela peut entraîner un débordement de la pile.

import sys  

# Get the current recursion limit
current_limit = sys.getrecursionlimit()
print(f'Current limit: {current_limit}')  

# Set a new recursion limit to 200
new_limit = 200
sys.setrecursionlimit(new_limit)  

# Get the new recursion limit
changed_current_limit = sys.getrecursionlimit()
print(f'Current limit after change: {changed_current_limit}')  

Current limit: 1000
Current limit after change: 200

Cas de base manquant

Un cas de base manquant ou incorrect entraînera une récursivité infinie de la fonction, ce qui provoquera un débordement de la pile.

Pour y remédier, assurez-vous que votre cas de base est bien défini et réalisable.

Comment arrêter la récursivité en Python

La clé pour arrêter la récursivité en Python est de définir un cas de base approprié. Sans cela, la récursion ne se terminera jamais et entraînera une erreur.

Par exemple, dans la fonction factorielle que j'ai mise en œuvre précédemment, le cas de base était if num == 0, ce qui arrête la récursivité. En général, vous devez vous assurer que chaque fonction récursive est soumise à une condition de terminaison.

La conception de cas de base efficaces nécessite une réflexion approfondie. Voici quelques lignes directrices :

• Identifiez la version la plus simple du problème qui peut être résolue directement.
• Veillez à ce que tous les chemins récursifs aboutissent à un cas de base.
• Testez les cas limites séparément pour vérifier qu'ils sont traités correctement.
• Envisagez plusieurs cas de base si le problème l'exige.

Parfois, des techniques de programmation défensives sont utiles, en ajoutant des garde-fous contre les entrées non valides ou des contrôles d'exécution pour éviter une profondeur de récursion excessive. Par exemple :

def safe_factorial(num, depth=0, max_depth=100):
    # Check if recursion is too deep
    if depth > max_depth:
        raise ValueError("Maximum recursion depth exceeded")
   
    # Base case
    if num <= 0:
        return 1
   
    # Recursive case with depth tracking
    return num * safe_factorial(num - 1, depth + 1, max_depth)

# Calculate factorial of 5 with default depth limits
result = safe_factorial(5)

print(result) 

120

# Calculate factorial of 5 with depth > max_depth
result = safe_factorial(5, depth=20, max_depth=10)

print(result) 

ValueError: Maximum recursion depth exceeded

Cette approche vous permet de fixer des limites personnalisées et de fournir des messages d'erreur plus significatifs que ceux proposés par défaut à l'adresse RecursionError.

Voici un autre exemple qui illustre une manière différente de définir les cas de base : trouver le plus grand diviseur commun (PGCD) de deux nombres à l'aide de la récursivité.

Le PGCD de deux nombres x et y peut être calculé à l'aide de l'algorithme d'Euclide, avec l'opérateur modulo opérateur modulo %:

• Cas de base : Si y == 0, le PGCD est x.
• Cas récursif : Sinon, le PGCD de x et y est le même que le PGCD de y et x % y.

def find_gcd(x, y):
    # Base case: if y is 0, the GCD is x
    if y == 0:
        return x
    # Recursive case: GCD of y and x % y
    return find_gcd(y, x % y)

print(find_gcd(48, 18))  

6

Récursion vs. L'itération en Python

La récursivité et l'itération permettent toutes deux de résoudre un grand nombre de problèmes identiques, mais chacune a ses avantages et ses inconvénients :

• La récursivité est souvent plus élégante et plus facile à comprendre, en particulier pour les problèmes qui ont une structure récursive naturelle (par ex, traversées d'arbresfactorielles, nombres de Fibonacci).
• L'itération peut être plus efficace parce qu'elle n'implique pas le surcoût de multiples appels de fonctions et peut éviter les problèmes liés au débordement de la pile. Les solutions itératives sont généralement plus efficaces en termes de mémoire.

Quand utiliser la récursivité:

• Lorsque le problème peut être naturellement divisé en sous-problèmes plus petits.
• Pour les problèmes impliquant des structures de données hiérarchiques, comme les arbres.
• Lorsque la solution est présentée sous forme récursive, elle est plus intuitive et permet d'obtenir un code plus propre.
• Lorsque la lisibilité du code est prioritaire par rapport à l'optimisation des performances.
• Lorsque vous travaillez avec des données dont la profondeur est inconnue (comme l'analyse de données JSON ou XML imbriquées).

Quand utiliser l'itération:

• Pour les problèmes qui nécessitent des tâches répétitives sans diviser le problème en sous-problèmes plus petits.
• Pour les tâches critiques en termes de performances, où la récursivité profonde pourrait entraîner une utilisation élevée de la mémoire.
• Lorsque vous travaillez avec de grands ensembles de données susceptibles de dépasser la limite de récursivité.
• Lorsque l'utilisation de la mémoire est une préoccupation majeure.
• Pour les problèmes qui sont naturellement séquentiels plutôt que hiérarchiques.

Comparons les implémentations récursives et itératives du même problème, en calculant la somme des nombres compris entre 1 et num:

Récursif:

def sum_recursive(num):
    if num == 1:
        return 1
    else:
        return num + sum_recursive(num - 1)

Itératif:

def iterative_sum(num):
    total = 0
    for i in range(1, num + 1):
        total += i
    return total

La version itérative utilise une boucle pour accumuler la somme, tandis que la version récursive décompose le problème en ajoutant n à la somme des nombres compris entre 1 et num - 1. Bien que les deux solutions fonctionnent, la version itérative sera plus efficace pour les grandes valeurs de num, car elle n'implique pas la surcharge de plusieurs appels de fonction.

Certains problèmes naturellement récursifs peuvent être transformés en solutions itératives à l'aide d'une pile ou d'une file d'attente pour simuler les appels récursifs. Cette technique est particulièrement utile lorsqu'il s'agit de parcourir des arbres ou des graphes.

Exemples pratiques de récursion en Python

La récursivité peut être appliquée à toute une série de problèmes intéressants :

1. Calculer les nombres de Fibonacci

La suite de Fibonacci est définie récursivement comme suit :

• F(0) = 0
• F(1) = 1
• F(n) = F(n − 1) + F(n − 2)

Vous obtiendrez ainsi la séquence suivante :

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...

Voici comment vous pourriez le mettre en œuvre :

def compute_fibonacci(num):
    if num <= 0:
        return 0
    elif num == 1:
        return 1
    return compute_fibonacci(num - 1) + compute_fibonacci(num - 2)

print(compute_fibonacci(6))

8

Cependant, cette mise en œuvre naïve recalcule les valeurs plusieurs fois. Une approche plus efficace utilise la mémorisation, qui stocke les résultats précédemment calculés (mise en cache) afin d'éviter les calculs redondants et de réduire considérablement le temps de calcul :

def optimized_fibonacci(num, cache=None):
    if cache is None:
        cache = {}
    if num in cache:
        return cache[num]
    if num <= 1:
        return num
    cache[num] = optimized_fibonacci(num - 1, cache) + optimized_fibonacci(num - 2, cache)
    return cache[num]

Ceci peut être simplifié en utilisant le décorateur lru_cache() du module functools:

from functools import lru_cache

@lru_cache(maxsize=None)  # Cache all computed values
def cached_fibonacci(num):
    if num <= 1:
        return num
    return cached_fibonacci(num - 1) + cached_fibonacci(num - 2)

2. Traverser des structures de données imbriquées

La récursivité est également pratique pour travailler avec des structures de données imbriquées, telles que des listes de listes ou des objets JSON. Par exemple, la traversée d'une arborescence de répertoires ou l'aplatissement récursif d'une liste imbriquée.

def flatten(nested):
    result = []
    for element in nested:
        if isinstance(element, list):
            result.extend(flatten(element))
        else:
            result.append(element)
    return result

nested_structure = [1, [2, 3], [4, [5, 6]]]

print(flatten(nested_structure))  

[1, 2, 3, 4, 5, 6]

3. Algorithmes de tri (par exemple, tri rapide ou tri par fusion) 

Les algorithmes de tri tels que le tri rapide et le tri par tri par fusion s'appuient fortement sur la récursivité. Dans ces algorithmes, le problème est décomposé en sous-problèmes plus petits, qui sont triés de manière récursive.

Voici une implémentation simple du tri sélectif :

def quicksort_algo(array):
    if len(array) <= 1:
        return array
    pivot = array[len(array) // 2]
    lower = [item for item in array if item < pivot]
    equal = [item for item in array if item == pivot]
    greater = [item for item in array if item > pivot]
    return quicksort_algo(lower) + equal + quicksort_algo(greater)

array = [220, 33, 400, 150, 16]

print(quicksort_algo(array))

[16, 33, 150, 220, 400]

Conclusion

La récursivité est un concept puissant de Python qui permet de résoudre des problèmes complexes en les décomposant en sous-problèmes plus simples. Lorsqu'elle est utilisée correctement, la récursivité permet d'obtenir un code propre, concis et facile à comprendre. 

Toutefois, il est essentiel de définir des cas de base appropriés et de tenir compte de la profondeur de récursion afin d'éviter les erreurs les plus courantes. 

Bien que la récursion soit parfois moins efficace que l'itération, elle constitue un outil précieux pour résoudre certains types de problèmes, en particulier ceux qui impliquent des données hiérarchiques ou qui se prêtent naturellement à des solutions récursives.

En comprenant la récursion et en vous exerçant avec des exemples comme les factorielles, les suites de Fibonacci et les algorithmes de tri, vous serez bien équipé pour tirer parti de la récursion dans vos projets Python.

Si vous êtes intéressé par des sujets Python plus avancés où vous pourriez mettre en œuvre la récursivité, consultez les parcours d'apprentissage suivants : Programmation en Python, Analyste de données en Pythonet Associé(e) Data Scientist en Python