Dans cet article tutoriel, vous découvrirez les fonctions récursives en Python et comment les utiliser pour simplifier votre code.
Notre première fonction récursive
Une fonction récursive est une fonction qui s’appelle elle-même jusqu’à ce qu’elle ne le fasse plus.
La fonction fn() suivante est une fonction récursive, car elle a un appel à elle-même :
def fn():
# ...
fn()
# ...Pour pouvoir s’arrêter, une fonction récursive doit avoir une condition d’arrêt. Nous devons donc ajouter une instruction if comme celle-ci :
def fn():
# ...
if condition:
# ne s'appelle pas elle-même
else:
fn()
# ...En règle générale, on utilise une fonction récursive pour diviser un problème difficile à résoudre en problèmes plus petits qui sont plus faciles à résoudre.
En programmation, vous trouverez souvent les fonctions récursives utilisées dans les structures de données et les algorithmes comme les arbres, les graphiques et les recherches binaires.
Exemples de fonctions récursives Python
Prenons quelques exemples d’utilisation des fonctions récursives Python.
Un exemple de fonction récursive simple en Python
Supposons que nous ayons besoin de développer une fonction de compte à rebours qui compte à rebours à partir d’un nombre spécifié jusqu’à zéro.
Par exemple, si vous appelez la fonction qui compte à rebours à partir de 3, elle affichera la sortie suivante :
3
2
1Ce qui suit définit la fonction count_down() :
def count_down(nombre_de_depart):
""" Compte à rebours à partir d'un nombre """
print(nombre_de_depart)Si vous appelez la fonction count_down() maintenant :
count_down(3)Elle n’affichera que le numéro de départ : 3.
Pour afficher respectivement dans l’ordre les nombres 3, 2 et 1, nous devons :
Tout d’abord, appeler count_down(3) pour afficher 3.
Puis, appeler count_down(2) pour afficher 2.
Enfin, appeler count_down(1) pour afficher 1.
Pour ce faire, à l’intérieur de la fonction count_down(), nous devons définir une logique pour appeler la fonction count_down() avec les arguments 2 et 1.
Pour ce faire, nous devons rendre la fonction count_down() récursive.
Ce qui suit définit une fonction count_down() récursive et l’appelle en passant le nombre 3 :
def count_down(nombre):
""" Compte à rebours à partir d'un nombre """
print(nombre)
count_down(nombre-1)
count_down(3)Si nous exécutons le programme, nous verrons l’erreur suivante :
RecursionError: maximum recursion depth exceeded while calling a Python objectLa raison en est que count_down()s’appelle indéfiniment jusqu’à ce que le système l’arrête. Par défaut, Python considère que la limite maximale à ne pas dépasser est de 1000 appels.
Nous pouvons vérifier cette limite à l’aide de sys.getrecursionlimit() :
>>> import sys
>>>
>>> print(sys.getrecursionlimit())
1000Et au besoin, nous pouvons le modifier avec sys.setrecursionlimit() :
>>> import sys
>>>
>>> sys.setrecursionlimit(1500)
>>> print(sys.getrecursionlimit())
1500Attention, si cette limite existe, c’est qu’il y a une bonne raison.
Revenons-en à notre compte à rebours, nous devons l’arrêter une fois le nombre zéro atteint. Pour ce faire, ajoutons une condition comme celle-ci :
def count_down(nombre):
""" Compte à rebours à partir d'un nombre """
print(nombre)
# Appeler la fonction count_down si le nombre suivant à décompter est positif
nombre_suivant = nombre - 1
if nombre_suivant > 0:
count_down(nombre_suivant)
count_down(3)Sortie :
3
2
1Dans cet exemple, la fonction count_down() s’appelle uniquement lorsque le nombre suivant qui doit être décompté est supérieur à zéro. En d’autres termes, si sa valeur est zéro, la fonction arrête de s’appeler.
Utiliser une fonction récursive pour calculer la somme d'une séquence
Supposons que nous ayons besoin de calculer la somme d’une séquence, par exemple de 1 à 100. Un moyen simple de le faire est d’utiliser une boucle for avec la fonction range() :
def somme(n):
total = 0
for index in range(n+1):
total += index
return total
result = somme(100)
print(result)Sortie :
5050Pour faire la même chose en utilisant la récursivité, nous pouvez calculer la somme de la séquence de 1 à n comme suit :
- somme(n) = n + somme(n-1)
- somme(n-1) = n-1 + somme(n-2)
- …
- somme(0) = 0
La fonction somme() continuera de s’appeler tant que son argument sera supérieur à zéro.
Ce qui suit définit la version récursive de la fonction somme() :
def somme(n):
if n > 0:
return n + somme(n-1)
return 0
result = somme(100)
print(result)Comme vous pouvez le voir, la fonction récursive est beaucoup plus courte et plus lisible.
Si vous utilisez l’opérateur ternaire, le code de la fonction somme() sera encore plus concis :
def somme(n):
return n + somme(n-1) if n > 0 else 0
result = somme(100)
print(result)Performance et cas d'usage classique de la récursivité
En général, la récursivité est plus coûteuse en mémoire que son homologue itératif, car chaque appel récursif nécessite généralement de placer une adresse mémoire sur la pile de sorte que le programme puisse ultérieurement revenir à ce point. Afin de ne pas saturer la mémoire, comme nous l’avons vu précédemment, Python possède une limite explicite aux nombres d’appels récursifs que nous pouvons faire. Cette limite est configurée par défaut à 1000 et doit être modifié avec parcimonie !
Néanmoins, malgré la contrainte de mémoire et même si vous êtes limité par le nombre d’appels que vous pouvez faire, cela ne devrait pas vous décourager d’utiliser la récursivité, car il existe de nombreux cas dans lesquels elle est beaucoup plus naturelle et lisible que les boucles, comme lorsque l’on travaille avec des arbres. En effet, la récursivité est meilleure que l’itération pour les problèmes qui peuvent être décomposés en multiples morceaux plus petits.
C’est généralement le cas avec les arbres puisque le problème de l’analyse du nœud parent peut être décomposé en multiple plus petits problèmes d’analyse de chaque nœud enfant.
Alors oui, la récursivité est préférable à l’itération pour les problèmes qui peuvent être décomposés en plusieurs problèmes plus petits, indépendants et similaires.
Pour en finir avec la récursivité, malgré la perte de temps liée à la somme des coûts des appels de chaque fonction, une approche récursive peut, en fonction du contexte et de la complexité de l’algorithme, facilement obtenir de meilleures performances en vitesse qu’une approche itérative notamment grâce à l’utilisation de la mise en cache de données. Un bon exemple est l’utilisation du décorateur @lru_cache.
Le mot de la fin
Ce qu’il faut retenir de la récursivité :
- Une fonction récursive est une fonction qui s’appelle elle-même jusqu’à ce qu’elle ne le fasse plus ;
- Une fonction récursive doit toujours avoir une condition d’arrêt ;
- Privilégier une approche récursive pour les problèmes qui peuvent être décomposés en plusieurs problèmes plus petits ;
- Mettre en cache des données avec
@lru_cachequand c’est possible ; - Ne pas dépasser la taille de la pile.
Maintenez que vous savez tout sur la récursion, si vous avez des questions ou un commentaire à partager, n’hésitez pas à commenter cet article.
Enfin, le format des articles évolue un peu et je mettrai systématiquement des idées d’exercices à la fin des articles.
Pour les corrigés, ça sera dans les commentaires si vous êtes bloqués.
Bonne journée à vous !
5 idées d'exercices pour pratiquer :
- Calculer une suite de Fibonacci avec une approche itérative ;
- Calculer une suite de Fibonacci avec une approche récursive ;
- Mesurer la différence de vitesse entre :
- approche itérative ;
- approche récursive ;
- approche récursive + décorateur
@lru_cache
- Faire un algorithme de tri par sélection (approche itérative) d’une liste de 10000 entiers ;
- Faire un algorithme de tri rapide (approche récursive) d’une liste de 10000 entiers ;
merci