Concept de fonction récursive Python : Tutoriel Python pour les débutants

Dans le monde de l'informatique, la récursivité fait référence à la technique consistant à définir une chose dans ses propres termes. En d'autres termes, une fonction récursive s'appelle elle-même pour le traitement. Dans cet article, nous allons comprendre le concept de fonction récursive en Python , un langage de programmation largement utilisé au 21e siècle.

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

En Python, un groupe d'instructions liées qui exécutent une tâche spécifique est appelé une "fonction". Ainsi, les fonctions divisent votre programme en plus petits morceaux. Et il est de notoriété publique qu'une fonction peut appeler d'autres fonctions en Python.

Mais certaines autres fonctions peuvent s'appeler elles-mêmes. Celles-ci sont appelées fonctions récursives. Considérons deux miroirs parallèles placés face à face. Désormais, tout objet conservé entre les miroirs serait réfléchi de manière récursive.

Entrons dans le détail de la fonction récursive pour bien comprendre son fonctionnement.

La fonction récursive

Nous savons qu'une fonction récursive en Python s'appelle elle-même telle qu'elle est définie via des expressions auto-référentielles, c'est-à-dire en termes d'elle-même. Il continue de répéter son comportement jusqu'à ce qu'une condition particulière soit remplie pour renvoyer une valeur ou un résultat. Voyons maintenant un exemple pour comprendre comment cela fonctionne.

Lisez aussi: Questions et réponses de l'entretien Python

Supposons que vous souhaitiez connaître la factorielle d'un entier. La factorielle n'est rien d'autre que le produit de tous les nombres, à partir de 1 jusqu'à cet entier. Par exemple, le factoriel de 5 (écrit 5 !) serait 1*2*3*4*5*6, c'est-à-dire 720. Nous avons une fonction récursive calc_factorial(x), qui est définie comme suit :

def calc_factoriel(x):

#Fonction récursive pour trouver la factorielle d'un entier

si x == 1 :

retour 1

autre

retour (x * calc_factorial(x-1))

Que se passerait-il si vous appeliez cette fonction avec un entier positif comme 4 ? Eh bien, chaque appel de fonction ajoutera un cadre de pile jusqu'à ce que nous atteignions le cas de base (lorsque le nombre se réduit à 1). La condition de base est requise pour que la récursivité se termine et ne se poursuive pas indéfiniment. Ainsi, dans le cas donné, la valeur 24 sera renvoyée après le quatrième appel.

Implémentation de la fonction récursive en Python

Il peut y avoir diverses applications des fonctions récursives en Python. Par exemple, vous souhaitez créer un graphique avec un motif répété, par exemple un flocon de neige Koch. La récursivité peut être utilisée pour générer des motifs fractals, qui sont constitués de versions plus petites du même design.

Un autre exemple est celui de la résolution de jeux. Vous pouvez écrire des algorithmes récursifs pour résoudre le Sudoku et de nombreux jeux complexes. La récursivité est le plus souvent utilisée dans les problèmes de recherche, de tri et de parcours.

Une caractéristique frappante de la fonction est que l'implémentation récursive permet le retour en arrière. Ainsi, la récursivité consiste à construire une solution de manière incrémentielle et à supprimer les solutions qui ne satisfont à aucun moment les contraintes du problème. Deux choses sont nécessaires pour y parvenir : le maintien de l'état et une structure de données appropriée. Lisez la suite pour vous familiariser avec ces termes.

Lire : Salaire d'un développeur Python en Inde

Entretenir l'état

Chaque appel récursif en Python a son propre contexte d'exécution. Lorsque vous traitez avec des fonctions récursives en Python, vous devez enfiler l'état à travers chaque appel récursif. Avec cela, l'état actuel devient une partie du contexte d'exécution de l'appel actuel. Vous pouvez également conserver l'état dans une portée globale.

Par exemple, si vous utilisez la récursivité pour calculer 1+2+3+4+…….+10. Ici, le nombre actuel que vous ajoutez et la somme accumulée jusqu'à ce point forment l'état que vous devez maintenir. Le maintien de l'état implique de transmettre l'état actuel mis à jour en tant qu'arguments à chaque appel. Voici comment vous pouvez le faire.

def somme_nombres(nombre_actuel, somme_accumulée)

#Cas de base

#Renvoyer l'état final

si nombre actuel==11 :

retourner la somme_accumulée

#Cas récursif

#Thread l'état via un appel récursif

Autre:

renvoie sum_numbers (current_number + 1, cumul_sum + current_number)

Alternativement, vous pouvez utiliser l'état modifiable global. Pour conserver l'état à l'aide de cette méthode, vous conservez l'état dans la portée globale.

nombre_actuel = 1

somme_accumulée = 0

def sum_numbers() :

numéro_actuel global

somme_accumulée globale

#Cas de base

si numéro_actuel==11

retourner la somme_accumulée

#Cas récursif

autre:

somme_accumulée = somme_accumulée + nombre_actuel

numéro_actuel = numéro_actuel + 1

retourner somme_nombres()

Structures de données récursives

Une structure de données est considérée comme récursive si elle peut être définie en termes de versions plus petites et plus simples d'elle-même. Des exemples de structures de données récursives incluent des listes, des arbres, des structures hiérarchiques, des dictionnaires, etc. Une liste peut avoir d'autres listes comme éléments. Un arbre a des sous-arbres, des nœuds feuilles, etc.

Il est important de noter ici que la structure des fonctions récursives est souvent modélisée d'après les structures de données qu'elle prend en entrée. Ainsi, les structures de données récursives et les fonctions récursives vont de pair.

Récursivité dans le calcul de Fibonacci

Le mathématicien italien Fibonacci a défini pour la première fois les nombres de Fibonacci au 13ème siècle pour modéliser la croissance de la population de lapins. Il en a déduit qu'à partir d'un couple de lapins la première année, le nombre de couples de lapins nés une année donnée est égal au nombre de couples de lapins nés au cours de chacune des deux dernières années. Cela peut s'écrire : Fn = Fn-1 + Fn-2 (Cas de base : F0=1 et F1=1).

Lorsque vous écrivez une fonction récursive pour calculer le nombre de Fibonacci, cela peut entraîner une récursivité naïve. Cela se produit lorsque la définition de la fonction récursive est suivie naïvement et que vous finissez par recalculer les valeurs inutilement. Pour éviter le recalcul, vous pouvez appliquer le décorateur lru_cache à la fonction. Il met en cache les résultats et évite au processus de devenir inefficace.

Lire la suite : Top 10 des outils Python que chaque développeur Python devrait connaître

Avantages et inconvénients de la récursivité

La récursivité aide à simplifier une tâche complexe en la divisant en sous-problèmes. Les fonctions récursives rendent le code plus propre et simplifient également la génération de séquences. Mais la récursivité n'est pas sans limites. Parfois, les appels peuvent s'avérer coûteux et inefficaces car ils consomment beaucoup de temps et de mémoire. Les fonctions récursives peuvent également être difficiles à déboguer.

Emballer

Dans cet article, nous avons couvert le concept de Python recursion , l'avons démontré à l'aide de quelques exemples, et avons également discuté de certains de ses avantages et inconvénients. Avec toutes ces informations, vous pourrez facilement expliquer les fonctions récursives lors de votre prochaine interview Python !

Si vous êtes curieux d'en savoir plus sur la science des données, consultez le diplôme PG de IIIT-B & upGrad en science des données qui est créé pour les professionnels en activité et propose plus de 10 études de cas et projets, des ateliers pratiques, un mentorat avec des experts de l'industrie, 1- on-1 avec des mentors de l'industrie, plus de 400 heures d'apprentissage et d'aide à l'emploi avec les meilleures entreprises.