Introduction
Lorsque nous pensons à répéter une tâche, nous pensons généralement aux boucles For et While. Ces constructions nous permettent d’effectuer des itérations sur une liste, une collection, etc.
Cependant, il existe une autre forme de répétition d’une tâche, d’une manière légèrement différente. En appelant une fonction sur elle-même, pour résoudre une petite instance du même problème, nous effectuons une récursion.
Ces fonctions s’appellent elles-mêmes jusqu’à ce que le problème soit résolu, divisant pratiquement le problème initial en de nombreuses petites instances de lui-même; comme par exemple, prendre de petites bouchées d’un plus gros morceau de nourriture.
L’objectif final est de manger toute l’assiette. Vous le faites en prenant une bouchée encore et encore. Chaque bouchée est une action récursive, après laquelle vous entreprenez la même action la fois suivante. Vous faites cela pour chaque bouchée, en évaluant que vous devez en prendre une autre pour atteindre le but, jusqu’à ce qu’il n’y ait plus de nourriture dans votre assiette.
Pour un aperçu, 👉 cliquez sur une couverture pour feuilleter le livre sur Amazon 📚.
Qu’est-ce que la récursion ?
Comme indiqué dans l’introduction, la récursion implique un processus qui s’appelle lui-même par définition. Une fonction récursive comporte généralement deux composantes :
- Le cas de base, qui est une condition qui détermine quand la fonction récursive doit s’arrêter
- L’appel à soi-même
Prenons un petit exemple pour démontrer les deux composantes :
Le cas de base pour nous est que si la variable i est égale à 0, c’est-à-dire combien de chaînes “Bonjour !” restantes nous devons imprimer. La fonction s’arrêtera tout simplement.
Après l’instruction print, nous appelons à nouveau bonjour_recursive mais avec une valeur i réduite. C’est important ! Si nous ne réduisons pas la valeur restante, la fonction sera exécutée indéfiniment. En général, lorsqu’une fonction récursive s’appelle elle-même, les paramètres sont modifiés pour être plus proches du cas de base.
Visualisons comment cela fonctionne lorsque nous appelons bonjour_recursive(5) :
Après que la fonction ait affiché “Bonjour !”, elle s’appelle elle-même avec une valeur inférieure pour rester jusqu’à ce qu’elle atteigne 0. À zéro, la fonction retourne à l’endroit où elle a été appelée dans bonjour_recursive(1), qui retourne à l’endroit où elle a été appelée dans bonjour_recursive(2) … et qui retourne finalement à l’endroit où elle a été appelée dans bonjour_recursive(5).
Pourquoi ne pas utiliser une boucle ?
Toutes les opérations peuvent être effectuées à l’aide de boucles. Néanmoins, certains problèmes sont souvent plus faciles à résoudre avec la récursion plutôt qu’avec l’itération. Un cas d’utilisation courant de la récursion est le parcours d’un arbre :
Il est généralement plus facile de penser à la traversée des nœuds et des branches d’un arbre en utilisant la récursion. Même si les boucles et la récursivité parcourent toutes les deux l’arbre, elles ont des objectifs différents : les boucles sont destinées à répéter une tâche alors que la récursivité est destinée à décomposer une grande tâche en tâches plus petites.
La récursion avec les arbres par exemple fonctionne bien parce que nous pouvons traiter l’arbre entier en traitant individuellement des parties plus petites de l’arbre.
Exemples
La meilleure façon de se familiariser avec la récursion, ou tout autre concept de programmation, est de la pratiquer. La création de fonctions récursives est simple : veillez à inclure dans votre programme votre cas de base et à appeler la fonction de manière à ce qu’elle se rapproche du cas de base.
Somme d’une liste
Python inclut une fonction de somme pour les listes. L’implémentation par défaut de Python, utilise une boucle de for-loop en C pour créer cette fonction.
Voyons comment faire avec la récursion :
Le cas de base est la liste vide – la meilleure somme pour cela est 0. Une fois que nous avons traité notre cas de base, nous supprimons le dernier élément de la liste. Nous appelons enfin la fonction sum_recursive avec la liste réduite, et nous ajoutons le nombre que nous avons retiré au total.
Conclusion
La récursivité nous permet de décomposer une grande tâche en de plus petites en s’appelant de façon répétitive. Une fonction récursive nécessite un cas de base pour arrêter l’exécution, et l’appel à soi-même qui conduit progressivement à la fonction au cas de base. Elle est couramment utilisée dans les arbres, mais d’autres fonctions peuvent être écrites avec la récursivité pour fournir des solutions élégantes.
