Dans ce didacticiel, vous apprendrez à créer une fonction récursive (une fonction qui s'appelle elle-même).
Qu'est-ce que la récursivité?
La récursivité est le processus de définition de quelque chose en termes de lui-même.
Un exemple de monde physique serait de placer deux miroirs parallèles face à face. Tout objet entre eux serait reflété récursivement.
Fonction récursive Python
En Python, nous savons qu'une fonction peut appeler d'autres fonctions. Il est même possible que la fonction s'appelle elle-même. Ces types de construction sont appelés fonctions récursives.
L'image suivante montre le fonctionnement d'une fonction récursive appelée recurse.
Fonction récursive en Python
Voici un exemple de fonction récursive pour trouver la factorielle d'un entier.
La factorielle d'un nombre est le produit de tous les nombres entiers de 1 à ce nombre. Par exemple, la factorielle de 6 (notée 6!) Est 1 * 2 * 3 * 4 * 5 * 6 = 720.
Exemple de fonction récursive
def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))
Production
La factorielle de 3 est 6
Dans l'exemple ci-dessus, factorial()est une fonction récursive telle qu'elle s'appelle elle-même.
Lorsque nous appelons cette fonction avec un entier positif, elle s'appellera récursivement en diminuant le nombre.
Chaque fonction multiplie le nombre par la factorielle du nombre en dessous jusqu'à ce qu'il soit égal à un. Cet appel récursif peut être expliqué dans les étapes suivantes.
factoriel (3) # 1er appel avec 3 3 * factoriel (2) # 2ème appel avec 2 3 * 2 * factoriel (1) # 3ème appel avec 1 3 * 2 * 1 # retour du 3ème appel comme numéro = 1 3 * 2 # retour du 2ème appel 6 # retour du 1er appel
Regardons une image qui montre un processus étape par étape de ce qui se passe:
Travail d'une fonction factorielle récursive
Notre récursivité se termine lorsque le nombre est réduit à 1. C'est ce qu'on appelle la condition de base.
Chaque fonction récursive doit avoir une condition de base qui arrête la récursivité ou bien la fonction s'appelle elle-même indéfiniment.
L'interpréteur Python limite les profondeurs de récursivité pour éviter des récursions infinies, entraînant des débordements de pile.
Par défaut, la profondeur maximale de récursivité est de 1 000. Si la limite est franchie, il en résulte RecursionError. Regardons une de ces conditions.
def recursor(): recursor() recursor()
Production
Traceback (dernier appel le plus récent): Fichier "", ligne 3, dans le fichier "", ligne 2, dans un fichier "", ligne 2, dans un fichier "", ligne 2, dans un (Ligne précédente répétée 996 fois de plus ) RecursionError: profondeur maximale de récursivité dépassée
Avantages de la récursivité
- Les fonctions récursives donnent au code un aspect propre et élégant.
- Une tâche complexe peut être décomposée en sous-problèmes plus simples en utilisant la récursivité.
- La génération de séquence est plus facile avec la récursivité qu'avec une itération imbriquée.
Inconvénients de la récursivité
- Parfois, la logique derrière la récursivité est difficile à suivre.
- Les appels récursifs sont coûteux (inefficaces) car ils prennent beaucoup de mémoire et de temps.
- Les fonctions récursives sont difficiles à déboguer.
