La récursivité en Python
Les tâches les plus complexes en Python peuvent être décomposés en plusieurs sous-tâches plus simples. La récursivité contribue à atteindre cet objectif, ce qui rend le code plus propre et soigné. Ce tutoriel va présenter la récursivité, leurs avantages et comment les utiliser en Python.
Qu’est ce que la récursivité ?
La récursivité est une méthode de résolution d’un problème avec les solutions de plus petites instances de ce même problème. Cette approche peut être appliquée à plusieurs types de problème en programmation.
Les avantages de la récursivité
Certains des avantages de l’utilisation de la récursivité sont:
- La simplicité lors de l’écriture de code, ce qui facilite le débogage.
- La durée d’exécution d’un algorithme en fonction de la longueur de l’entrée.
- Préférée lors de la résolution de problèmes très complexes, en particulier les problèmes sur les structures arborescentes.
Les fonctions récursive en Python
Bien que la récursivité semble être une procédure simple. Supposons que nous avons deux rectangles A et B. Si nous les ajoutons ensemble, ils forment un rectangle C. C’est en soi une procédure récursive. Nous avons utilisé des instances plus petites d’u rectangle pour se définir, et si nous devions écrire une fonction Python, ce serait comme suit:
|
|
Étant donné qu’une fonction récursive s’appelle elle-même, nous avons besoin d’une règle ou un point d’arrêt auquel prendrait fin le processus ou la boucle. Une telle condition est connue comme une condition ou scenario de base. Une condition de base est une exigence dans chaque programme récursif, sinon la procédure aboutirait à une boucle infinie.
La deuxième exigence est le cas récursif lorsque la fonction s’appelle elle-même.
Regardons un exemple:
Dans cet exemple, nous allons écrire une fonction factorielle. Cette fonction mathématiques prend en entrée un entier positif, et renvoie le produit des entiers inférieurs jusqu’à 1, lui compris. Le factoriel d’un nombre est donc obtenu en multipliant le nombre par tous les entiers positifs en dessous. Par exemple, factorial(3) = 3 x 2 x 1, factorial(2) = 2 x 1, et factorial(0) = 1.
La première étape est de définir notre cas de base, qui sera factoriel (0) = 1.
Comme nous pouvons le voir ci-dessus, il existe une relation entre chaque scénario factoriel consécutif. Nous remarquons que factoriel (4) = 4 x factoriel (3). De même, factorielle (5) = 5 x factorielle (4).
La deuxième partie sera l’écriture d’une fonction qui s’appelle elle-même.
Maintenant que nous l’avons simplifié, la fonction résultante sera:
|
|
Maintenant que nous savons écrire des fonctions récursives, examinons plusieurs cas d’études qui consolideront votre compréhension de la récursivité.
Cas d’étude 1 : Fibonacci
Dans une suite de Fibonacci, chaque nombre est la somme des deux nombres précédents, tels que : 1 + 1 = 2 ; 1 + 2 = 3 ; 2 + 3 = 5 ; 3 + 5 = 8. La suite de Fibonacci a été appliquée dans de nombreux domaines, et la plus courante est la prédiction du prix des actions sur le marché boursier.
La suite de Fibonacci commence par 0 et 1. Le premier nombre dans une suite de Fibonacci est 0, le deuxième nombre est 1, et le troisième terme de la séquence est 0 + 1 = 1. Le quatrième est 1 + 1 = 2 et ainsi de suite.
Afin d’utiliser une fonction récursive, nous devons avoir deux scénarios de base: 0 et 1. Nous pouvons ensuite traduire le modèle d’ajout en autre cas.
La fonction résultante sera :
|
|
Cas d’étude 2 : Inversion d’une chaîne de caractère
Dans cet exemple, nous allons écrire une fonction qui prend une chaîne en entrée et renvoie l’inverse de cette chaîne.
La première étape est de définir notre scénario de base, qui vérifiera si la chaîne est égale à 0 et, si oui, retourne la chaîne elle-même.
La deuxième étape est d’appeler de manière récursif la fonction d’inversion afin d’extraire le premier caractère et ensuite l’ajouter à la fin de la chaîne.
La fonction qui en résulte est :
|
|
Cas d’étude 3 : Somme de plusieurs éléments
Dans cet exemple, nous allons écrire une fonction qui prend un tableau comme entrée et retourne ensuite la somme des éléments dans la liste.
La première chose à faire est de définir notre scénario de base, qui vérifiera si la taille de la liste est égal à zéro et si oui retourne 0.
La deuxième étape renvoie l’élément et un appel à la fonction sum() moins un élément de la liste.
La solution est indiqué ci-dessous :
|
|
La récursivité est un concept puissant en programmation. Cependant, Il est également important de noter que la récursivité a ses propres limites:
- Les récursions prend beaucoup d’espace dans la pile (stack), ce qui le rend un peu plus lent.
- Les fonctions récursive requièrent plus d’espace et de temps pour s’exécuter.
Articles Similaires
Ubuntu 24.04 LTS - Une version qui fait débat entre déception et enthousiasme
Ubuntu 24.04 LTS, “Noble Numbat”, a récemment été déployée, apportant son lot de nouveautés et de changements. Cette version suscite à la fois de l’enthousiasme et de la déception au sein de la communauté des utilisateurs et des développeurs.
Lire la SuiteLe concours de beauté Miss AI : un cauchemar dystopique ou le futur de la beauté ?
Dans un monde où la technologie et la beauté fusionnent, le concours de beauté Miss AI fait son apparition. Ce concours, organisé par The World AI Creator Awards, récompense les créateurs d’images et d’influenceurs générés par intelligence artificielle (IA).
Lire la SuiteLe gouvernement du Salvador prend un coup dur : les hackers divulguent le code source et les accès VPN du portefeuille bitcoin national Chivo !
Le programme bitcoin du gouvernement du Salvador, Chivo , a été victime d’une série d’attaques informatiques ces derniers jours. Les hackers ont déjà divulgué les données personnelles de plus de 5 millions de Salvadoriens.
Lire la Suite