Qu’est-ce que la récursivité ?

La récursivité est le processus de définition de quelque chose en soi.

Un exemple de monde physique serait de placer deux miroirs parallèles l’un en face de l’autre. Tout objet entre eux serait réfléchi 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.

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 entiers de 1 à ce nombre. Par exemple, la factorielle de 6 (notée 6!) est 1*2*3*4*5*6 = 720.

Exemple d’une 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 = 3print("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 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 avec 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 33 * factorial(2) # 2nd call with 23 * 2 * factorial(1) # 3rd call with 13 * 2 * 1 # return from 3rd call as number=13 * 2 # return from 2nd call6 # 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 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 à l’infini.

L’interpréteur Python limite les profondeurs de récursivité pour éviter les récursions infinies, ce qui entraîne des débordements de pile.

Par défaut, la profondeur maximale de récursivité est de 1000. Si la limite est franchie, il en résulte RecursionError. Regardons une telle condition.

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 RecursionError: maximum recursion depth exceeded

Les avantages de la récursivité

1. Les fonctions récursives rendent le code propre et élégant.
2. Une tâche complexe peut être décomposée en sous-problèmes plus simples en utilisant la récursivité.
3. La génération de séquences est plus facile avec la récursivité que d’utiliser une itération imbriquée.

Inconvénients de la récursivité

1. Parfois, la logique derrière la récursivité est difficile à suivre.
2. Les appels récursifs sont coûteux (inefficaces) car ils prennent beaucoup de mémoire et de temps.
3. Les fonctions récursives sont difficiles à déboguer.