Fonctions récursives en Python

fonction récursive doit avoir une condition

En outre, une fonction récursive doit avoir une condition pour cesser de s'appeler elle-même. Vous devez donc ajouter une instruction if comme ceci :

Copier le code

def fn() :
    # ...
    if condition :
        # arrête de s'appeler elle-même
else :
        fn()
        # ...

Généralement, vous utilisez une fonction récursive pour diviser un gros problème difficile à résoudre en petits problèmes plus faciles à résoudre.
En programmation, vous trouverez souvent les fonctions récursives utilisées dans les structures de données et les algorithmes comme les arbres, les graphes et les recherches binaires.

Exemples de fonctions récursives Python

Prenons quelques exemples d'utilisation des fonctions récursives Python.

1) Un exemple simple de fonction récursive en Python

Supposons que vous ayez besoin de développer une fonction de compte à rebours qui effectue un décompte à partir d'un nombre spécifié jusqu'à zéro.
Par exemple, si vous appelez la fonction de décompte à partir de 3, vous obtiendrez le résultat suivant :

Copier le code

Le code suivant définit la fonction compte-a-rebours() :

Copier le code

def compte-a-rebours( debut) :
    """ Décompte à partir d'un nombre """
print( debut)

Si vous appelez la fonction compte-a-rebours() maintenant :

compte-a-rebours(3)

...elle n'affichera que le chiffre 3.
Pour afficher les nombres 3, 2, 1 et 0 vous devez :

Premièrement, appeler le compte-a-rebours(3) pour afficher le nombre 3.
Ensuite, appelez le compte-a-rebours(2) pour afficher le nombre 2.
Puis appelez le compte-a-rebours( 1) pour afficher le chiffre 1.
Enfin, appelez le compte-a-rebours(0) pour afficher le chiffre 0.
Pour ce faire, à l'intérieur de la fonction compte-a-rebours(), vous devrez définir une logique pour appeler la fonction compte-a-rebours() avec les arguments 2 , 1 et 0.

Pour ce faire, vous devez rendre la fonction compte-a-rebours() récursive.
Ce qui suit définit une fonction récursive compte-a-rebours() et l'appelle en passant le nombre 3 :

Copier le code

def compte_a_rebours(debut):
    """ Compte à rebours àpartir d'un nombre  """
    print(debut)
    compte_a_rebours(debut-1)

compte_a_rebours(3)

Si vous exécutez ce code, vous obtiendrez : soit une erreur ou le code va s'exécuter à l'infini.
La raison en est que la fonction compte_a_rebours() s'appelle elle-même indéfiniment jusqu'à ce que le système l'arrête.
Il faut donc arrêter le décompte lorsque le nombre atteint zéro. Pour ce faire, vous ajoutez une condition comme celle-ci :

Copier le code

def compte_a_rebours(debut):
    """ Compte à rebours àpartir d'un nombre  """
    print(debut)
    if debut-1 >= 0:
        compte_a_rebours(debut-1)

compte_a_rebours(3)

Dans cet exemple, la fonction compte-a-rebours() ne s'appelle que lorsque le nombre suivant est supérieur ou égal à zéro. En d'autres termes, si le prochain nombre est inférieur à zéro, elle cesse de s'appeler.

2) Utilisation d'une fonction récursive pour calculer la somme d'une séquence

Supposons que vous ayez besoin de calculer la somme d'une séquence, par exemple de 1 à 100. Une façon simple de le faire est d'utiliser une boucle for avec la fonction range() :

Copier le code

def somme(n):
    total = 0
    for index in range(n+1):
        total += index

    return total


result = somme(50)
print(result)

Pour appliquer la technique de récursion, vous pouvez calculer la somme de la séquence de 1 à n comme suit :

somme(n) = n + somme(n-1)
somme(n-1) = n-1 + somme(n-2)
...
somme(0) = 0

La fonction somme() continue à s'appeler elle-même tant que son argument est supérieur à zéro.
Ce qui suit définit la version récursive de la fonction somme() :

Copier le code

def somme(n):
    if n > 0:
        return n + somme(n-1)
    return 0

result = somme(50)
print(result)

Comme vous pouvez le constater, la fonction récursive est plus courte et plus lisible.
Si vous utilisez l'opérateur ternaire, la fonction somme() sera encore plus concise :

Copier le code

def somme(n):
    return n + somme(n-1) if n > 0 else 0

result = somme(50)
print(result)

Cours precedent

Sommaire

Cours suivant

Les fonctions récursives en Python

Cours tutoriel python

Gestion de fichiers

Python MySQL

TUTORIEL DJANGO

les biblioteques de python

fonction récursive doit avoir une condition

Exemples de fonctions récursives Python

1) Un exemple simple de fonction récursive en Python

2) Utilisation d'une fonction récursive pour calculer la somme d'une séquence

Voir aussi nos tutoriel :