Tutoriel Python - Fonction récursive

1. Qu’est-ce que la fonction récursive Python
2. Limitation de la récursivité
3. Avantage de la récursion
4. Inconvénient de la récursivité

Dans cette section, vous apprendrez les fonctions récursives de Python.

Qu’est-ce que la fonction récursive Python

Une fonction récursive est une fonction qui s’appelle elle-même et ce processus est appelé récursion de fonction.

Par exemple, calculons la factorielle d’un nombre, par exemple, 6.

6 * 5 * 4 * 3 * 2 * 1

Dans le code suivant, une fonction récursive est créée qui trouve la factorielle d’un nombre:

def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


a = 6
print("Factorial of", a, "=", fact(a))

Factorial of 6 = 720

La fonction fact(n) est une fonction récursive. La fonction fact se nomme elle-même avec l’argument n-1 jusqu’à ce que le nombre devienne 1 et c’est ainsi que la factorielle est calculée, c’est-à-dire en multipliant le nombre par la factorielle de un de moins que le nombre.

Dans cette fonction récursive, il y a une condition de base qui est que lorsque le nombre devient 1, 1 est retourné et de cette façon l’appel récursif devient fini.

Lors de la création d’une fonction récursive, il doit y avoir une condition de base pour terminer cet appel récursif.

Limitation de la récursivité

Comme vous l’avez remarqué, à chaque fois que la fonction s’appelle, elle a besoin de mémoire pour stocker quelques valeurs intermédiaires. Par conséquent, une fonction récursive consomme beaucoup plus de mémoire qu’une fonction non récursive normale. Python fixe la limitation des appels récursifs à 3000.

>>> import sys
>>> sys.getrecursionlimit()
3000

Il lève une ErreurRécursive si la récursion dépasse 3000.

def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


print(fact(4000))

Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    print(factorial(4000))
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  [Previous line repeated 989 more times]
  File "<pyshell#1>", line 2, in factorial
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

Solution pour supprimer la limitation de récursion

Vous pouvez résoudre la limitation de la récursion en la fixant à un nombre supérieur à la récursion requise.

import sys

sys.setrecursionlimit(5000)


def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


print(fact(4000))

Avantage de la récursion

• En utilisant des fonctions récursives, le problème peut être divisé en sous-problèmes qui peuvent être résolus facilement.
• Le code devient propre et net.

Inconvénient de la récursivité

• Il est parfois difficile de suivre la logique de la fonction récursive.
• La résolution de chaque sous-problème prendra beaucoup de temps et les fonctions récursives sont donc inefficaces.