Python - Récursivité : Guide Ultime pour les Débutants

Bonjour à tous, futurs sorciers Python !aujourd'hui, nous allons entreprendre un voyage passionnant dans le monde de la récursivité. Ne vous inquiétez pas si cela vous semble un peu intimidant – je promets que nous allons le rendre amusant et facile à comprendre. Alors, prenez votre boisson favorite, mettez-vous à l'aise, et plongeons-y !

Qu'est-ce que la Récursivité ?

Imaginez que vous êtes debout entre deux miroirs face à face. Vous voyez un nombre infini de reflets, non ? C'est un peu comme la récursivité en programmation ! En termes simples, la récursivité est lorsqu'une fonction s'appelle elle-même pour résoudre un problème.

Commençons par un exemple simple :

def countdown(n):
if n <= 0:
print("Décollage !")
else:
print(n)
countdown(n - 1)

countdown(5)

Si vous exécutez ce code, vous verrez :

5
4
3
2
1
Décollage !

Maintenant, décomposons cela :

1. Nous définissons une fonction appelée countdown qui prend un nombre n.
2. Si n est 0 ou moins, nous imprimons "Décollage !"
3. Sinon, nous imprimons n puis nous appelons countdown à nouveau avec n - 1.

Voilà la récursivité en action ! La fonction continue à s'appeler elle-même avec un nombre plus petit jusqu'à ce qu'elle atteigne zéro.

Composants de la Récursivité

Chaque fonction récursive a deux composants principaux :

1. Cas de base : C'est la condition qui arrête la récursivité.
2. Cas récursif : C'est l'endroit où la fonction s'appelle elle-même.

Dans notre exemple de compte à rebours :

• Le cas de base est if n <= 0
• Le cas récursif est countdown(n - 1)

Regardons un autre exemple classique : le calcul du factorial.

def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)

print(factorial(5))  # Sortie : 120

Voici ce qui se passe :

1. Si n est 0 ou 1, nous renvoyons 1 (ceci est notre cas de base).
2. Sinon, nous multiplions n par le factorial de n - 1 (ceci est notre cas récursif).

Donc, factorial(5) devient : 5 factorial(4) 5 (4 factorial(3)) 5 (4 (3 factorial(2))) 5 (4 (3 (2 factorial(1)))) 5 (4 (3 (2 1))) 5 4 3 2 1 = 120

Le Pouvoir de la Récursivité

La récursivité peut rendre certains problèmes complexes beaucoup plus faciles à résoudre. Regardons un exemple légèrement plus avancé : la suite de Fibonacci.

def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)

for i in range(10):
print(fibonacci(i), end=" ")
# Sortie : 0 1 1 2 3 5 8 13 21 34

Cette fonction calcule le nième nombre de Fibonacci. La suite de Fibonacci commence par 0 et 1, et chaque nombre suivant est la somme des deux nombres précédents.

Recherche Binaire Utilisant la Récursivité

Maintenant, abordons un exemple plus pratique : la recherche binaire. Il s'agit d'un moyen efficace de trouver un élément dans une liste triée.

def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2

if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1

arr = [2, 3, 4, 10, 40]
x = 10

result = binary_search(arr, 0, len(arr)-1, x)

if result != -1:
print(f"Element est présent à l'index {result}")
else:
print("Element n'est pas présent dans le tableau")

Cette fonction fonctionne en divisant répétitivement l'intervalle de recherche par deux. Si la valeur de la clé de recherche est inférieure à l'élément au milieu de l'intervalle, réduisez l'intervalle à la moitié inférieure. Sinon, réduisez-le à la moitié supérieure. Vérifiez répétitivement jusqu'à ce que la valeur soit trouvée ou que l'intervalle soit vide.

Quand Utiliser la Récursivité

La récursivité est particulièrement utile pour :

1. Les problèmes qui peuvent être décomposés en sous-problèmes similaires
2. Les structures de données en forme d'arbre (par exemple, les systèmes de fichiers, HTML DOM)
3. Les algorithmes comme QuickSort, MergeSort, etc.

Cependant, la récursivité n'est pas toujours la meilleure solution. Elle peut être gourmande en mémoire pour des récursions très profondes, et parfois un simple boucle peut être plus efficace et plus facile à comprendre.

Tableau des Méthodes de Récursivité

Méthode	Description	Exemple
Récursivité Directe	Une fonction s'appelle elle-même directement	Nos exemples countdown et factorial
Récursivité Indirecte	Fonction A appelle fonction B, qui appelle ensuite fonction A	Voir exemple ci-dessous
Récursivité en Queue	L'appel récursif est la dernière chose exécutée par la fonction	Notre exemple countdown
Récursivité non en Queue	L'appel récursif n'est pas la dernière chose exécutée par la fonction	Notre exemple factorial

Voici un exemple de récursivité indirecte :

def is_even(n):
if n == 0:
return True
else:
return is_odd(n - 1)

def is_odd(n):
return not is_even(n)

print(is_even(4))  # Sortie : True
print(is_odd(4))   # Sortie : False

Dans cet exemple, is_even appelle is_odd, qui appelle ensuite is_even.

Conclusion

Félicitations ! Vous venez de faire vos premiers pas dans le monde fascinant de la récursivité. Souvenez-vous, comme toute arme puissante, la récursivité doit être utilisée avec sagesse. Elle peut rendre votre code plus élégant et résoudre des problèmes complexes avec facilité, mais elle peut également rendre des problèmes simples inutilement compliqués.

Au fur et à mesure de votre parcours en Python, vous rencontrerez de nombreuses situations où la récursivité peut être appliquée. Continuez à pratiquer, et bientôt, vous serez en récursivité comme un pro !

Credits: Image by storyset