Recursion en Python (Recursion)

Dans cet article, vous apprendrez à créer des fonctions récursives (les fonctions qui appellent elles-mêmes).

Qu'est-ce que la récursion en Python ?

La récursion est le processus de définir quelque chose en fonction de soi-même.

Un exemple physique du monde réel est l'placement de deux miroirs parallèles face à face. Tout objet entre eux sera reflété récursivement.

Fonction récursive Python

En Python, nous connaissons unFonctionIl est possible d'appeler d'autres fonctions. Une fonction peut même appeler elle-même. Ces types de constructions sont appelés fonctions récursives.

Voici un exemple de fonction récursive pour trouver le factoriel d'un entier.

Le factoriel d'un nombre est16,6）est1 * 2 * 3 * 4 * 5 * 6 = 720"."

Exemple de fonction récursive

def calc_factorial(x):
　　　　"""Ceci est
　　　　"Fonction récursive pour le factoriel d'un entier"
　　　　if x ==　1:
　　　　　　　　return　1
　　　　else:
　　　　　　　　return (x　*　calc_factorial(x-1))
num =　4
print("Le factoriel de", num, "est", calc_factorial(num))

In the above example, calc_factorial() is a recursive function that calls itself.

When we call this function with a positive integer, it will recursively call itself by reducing the number.

Each function multiplies the number by the factorial of the number below it until it equals1. The following steps can explain this recursive call.

calc_factorial(4) #　1st call with　4
4　*　calc_factorial(3) #　2nd call with　3
4　*　3　*　calc_factorial(2) #　3rd call with　2
4　*　3　*　2　*　calc_factorial(1) #　4th call with　1
4　*　3　*　2　*　1　　　　　　　　　　　　　　　　　　# return from　4th call as number=1
4　*　3　*　2　　　　　　　　　　　　　　　　　　　　　　# return from　3rd call
4　*　6　　　　　　　　　　　　　　　　　　　　　　　　　　# return from　2nd call
24　　　　　　　　　　　　　　　　　　　　　　　　　　　　　# return from　1st call

When the number is reduced to1When this condition is met, recursion ends. This is called a basic condition.

Each recursive function must have a basic condition to stop recursion, otherwise the function will call itself infinitely.

The Python interpreter limits the depth of recursion to help avoid infinite recursion, which can lead to stack overflow.

By default, the maximum recursion depth is 1000. If it exceeds the limit, the result is RecursionError. Let's look at such a condition.

def recursor():
　　　　recursor()
recursor()

Output result

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

The advantages of recursion

1. Recursive functions make the code look clean and tidy.

2. Using recursion can decompose complex tasks into simpler subproblems.

3. Compared to using nested nesting, recursion is easier to generate sequences.

The disadvantages of recursion

1. Sometimes, the logic behind recursion is difficult to follow.

2. Recursive calls are expensive (inefficient) because they consume a large amount of memory and time.

3. Recursive functions are difficult to debug.