Les fonctions récursives sont une technique de programmation avancée qui permet à une fonction de s’appeler elle-même pour effectuer une tâche particulière. Dans cet article, nous allons vous montrer trois exemples (somme des éléments d’une liste, recherche d’un élément dans une liste et Tri par fusion) de fonctions récursives en Python.
Fonctions récursive pour calculer la somme des éléments d’une liste
La somme des éléments d’une liste peut être calculée en utilisant une fonction récursive en Python. La fonction prend une liste en entrée et renvoie la somme de tous les éléments de la liste.
def somme_liste(liste):
if len(liste) == 0:
return 0
else:
return liste[0] + somme_liste(liste[1:])
#exemple
somme_liste([1,2,3,4,5,6,7,8,9])
La première ligne vérifie si la liste est vide. Si c’est le cas, la fonction renvoie 0. Sinon, la fonction ajoute le premier élément de la liste à la somme des éléments restants, qui est calculée en appelant récursivement la fonction sur la sous-liste contenant tous les éléments de la liste, sauf le premier élément.
Recherche d’un élément dans une liste
La recherche d’un élément dans une liste peut également être effectuée en utilisant une fonction récursive en Python. La fonction prend une liste et un élément à rechercher en entrée et renvoie True si l’élément est présent dans la liste, sinon elle renvoie False.
def recherche_element(liste, element):
if len(liste) == 0:
return False
elif liste[0] == element:
return True
else:
return recherche_element(liste[1:], element)
#exemple
recherche_element([1,2,3,4,5,6,7,8,9], 10)
La première ligne vérifie si la liste est vide. Si c’est le cas, la fonction renvoie False, car l’élément ne peut pas être présent dans une liste vide. Sinon, la fonction vérifie si le premier élément de la liste est l’élément que nous cherchons. Si c’est le cas, la fonction renvoie True. Sinon, la fonction appelle récursivement elle-même sur la sous-liste contenant tous les éléments de la liste, sauf le premier élément.
Tri par fusion
Le tri par fusion est un algorithme de tri efficace qui utilise une fonction récursive pour trier une liste d’éléments. L’idée est de diviser la liste en deux sous-listes, de trier chacune des sous-listes récursivement, puis de fusionner les sous-listes triées pour obtenir la liste triée finale.
def tri_fusion(liste):
if len(liste) <= 1:
return liste
else:
milieu = len(liste) // 2
gauche = tri_fusion(liste[:milieu])
droite = tri_fusion(liste[milieu:])
return fusionner(gauche, droite)
def fusionner(gauche, droite):
resultat = []
i = j = 0
while i < len(gauche) and j < len(droite):
if gauche[i] < droite[j]:
resultat.append(gauche[i])
i += 1
else:
resultat.append(droite[j])
j += 1
resultat.extend(gauche[i:])
resultat.extend(droite[j:])
return resultat
#exemple
tri_fusion([1,2,3,4,5,6,7,8,9,94,87,15,13,45,65])
fusionner([1,2,3,4,5,6,7,8,9],[10,11,12,13,14,15,16,17,18,19])
Cette fonction divise récursivement la liste en deux parties jusqu’à ce que chaque partie ne contienne qu’un seul élément. Ensuite, elle fusionne les parties triées dans l’ordre croissant.
Conclusion
les fonctions récursives sont un outil puissant dans le développement de logiciels en Python. Elles permettent de résoudre des problèmes complexes en les décomposant en tâches plus simples et en les résolvant de manière répétitive.
Les exemples que nous avons vus dans cet article ont montré comment les fonctions récursives peuvent être utilisées pour résoudre différents problèmes liés aux listes, tels que la somme des éléments, la recherche d’un élément et le tri par fusion.
Vous pouvez cliquez ici pour voir un exemple sur une fonction récursive pour afficher la suite de Fibonacci
