Récursivité Python

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 soi.

Un exemple du monde physique serait de placer deux miroirs parallèles face à face. Tout objet entre eux serait reflété de manière récursive.

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 .

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))

Sortie

The factorial of 3 is 6

Dans l'exemple ci-dessus, factorial() est une fonction récursive comme 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.

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

Regardons une image qui montre un processus étape par étape de ce qui se passe :

Notre récursivité se termine lorsque le nombre se 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é, sinon la fonction s'appelle elle-même à l'infini.

L'interpréteur Python limite les profondeurs de récursivité pour aider à éviter les récursions infinies, entraînant des débordements de pile.

Par défaut, la profondeur maximale de récursivité est 1000 . Si la limite est franchie, cela donne RecursionError . Examinons une de ces conditions.

def recursor():
    recursor()
recursor()

Sortie

Traceback (most recent call last):
  File "<string>", line 3, in <module>
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Avantages de la récursivité

Les fonctions récursives rendent le code propre et élégant.
Une tâche complexe peut être décomposée en sous-problèmes plus simples à l'aide de la récursivité.
La génération de séquences 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 consomment beaucoup de mémoire et de temps.
Les fonctions récursives sont difficiles à déboguer.

Arguments de la fonction Python Fonction Python Anonyme/Lambda

Python