Une introduction – Python réel

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

Le mot récursivité vient du mot latin recurrere, ce qui signifie courir ou accélérer en arrière, revenir, revenir en arrière ou se reproduire. Voici quelques définitions en ligne de la récursivité:

• Dictionary.com: L'acte ou le processus de retour ou de retour en arrière
• Wiktionnaire: L'action de définir un objet (généralement une fonction) en fonction de cet objet lui-même
• Le dictionnaire gratuit: Méthode de définition d'une séquence d'objets, telle qu'une expression, une fonction ou un ensemble, où un certain nombre d'objets initiaux sont donnés et chaque objet successif est défini en fonction des objets précédents

UNE récursif définition est celle dans laquelle le terme défini apparaît dans la définition elle-même. Des situations autoréférentielles surviennent souvent dans la vraie vie, même si elles ne sont pas immédiatement reconnaissables en tant que telles. Par exemple, supposons que vous vouliez décrire l'ensemble des personnes qui composent vos ancêtres. Vous pouvez les décrire de cette façon:

Remarquez comment le concept qui est défini, les ancêtres, apparaît dans sa propre définition. C'est une définition récursive.

En programmation, la récursivité a une signification très précise. Il fait référence à une technique de codage dans laquelle une fonction s'appelle elle-même.

Pourquoi utiliser la récursivité?

La plupart des problèmes de programmation peuvent être résolus sans récursivité. Donc, à proprement parler, la récursivité n’est généralement pas nécessaire.

Cependant, certaines situations se prêtent particulièrement à un autoréférentiel définition – par exemple, la définition des ancêtres indiquée ci-dessus. Si vous deviez concevoir un algorithme pour gérer un tel cas par programme, une solution récursive serait probablement plus propre et plus concise.

La traversée des structures de données arborescentes est un autre bon exemple. Comme ce sont des structures imbriquées, elles correspondent facilement à une définition récursive. Un algorithme non récursif pour parcourir une structure imbriquée est susceptible d'être quelque peu maladroit, tandis qu'une solution récursive sera relativement élégante. Un exemple de ceci apparaît plus loin dans ce didacticiel.

En revanche, la récursivité n’est pas adaptée à toutes les situations. Voici quelques autres facteurs à considérer:

• Pour certains problèmes, une solution récursive, bien que possible, sera plus délicate qu'élégante.
• Les implémentations récursives consomment souvent plus de mémoire que les implémentations non récursives.
• Dans certains cas, l'utilisation de la récursivité peut entraîner un temps d'exécution plus lent.

En règle générale, la lisibilité du code sera le principal facteur déterminant. Mais cela dépend des circonstances. Les exemples présentés ci-dessous devraient vous aider à vous faire une idée du moment où vous devez choisir la récursivité.

Récursivité en Python

Lorsque vous appelez une fonction en Python, l'interpréteur crée un nouvel espace de noms local afin que les noms définis dans cette fonction n'entrent pas en collision avec des noms identiques définis ailleurs. Une fonction peut en appeler une autre, et même si elles définissent toutes les deux des objets avec le même nom, tout fonctionne bien car ces objets existent dans des espaces de noms.

Il en va de même si plusieurs instances de la même fonction s'exécutent simultanément. Par exemple, considérez la définition suivante:

def une fonction():
    X = dix
    une fonction()

Lorsque une fonction() s'exécute la première fois, Python crée un espace de noms et attribue X la valeur dix dans cet espace de noms. Puis une fonction() s'appelle lui-même récursivement. La deuxième fois une fonction() s'exécute, l'interpréteur crée un deuxième espace de noms et attribue dix à X là aussi. Ces deux instances du nom X sont distincts les uns des autres et peuvent coexister sans se heurter car ils sont dans des espaces de noms séparés.

Malheureusement, courir une fonction() tel quel produit un résultat qui est moins qu'inspirant, comme le montre le retraçage suivant:

>>> une fonction()
Traceback (dernier appel le plus récent):
  Déposer "", ligne 1, dans 
  
  
  
  Déposer "", ligne 3, dans une fonction
  Déposer "", ligne 3, dans une fonction
  Déposer "", ligne 3, dans une fonction
  [Previous line repeated 996 more times]
RecursionError: profondeur maximale de récursivité dépassée

Comme écrit, une fonction() serait en théorie indéfiniment, se faisant appeler encore et encore sans qu'aucun des appels ne revienne jamais. En pratique, bien sûr, rien n'est vraiment éternel. Votre ordinateur n'a qu'une quantité limitée de mémoire et il finira par s'épuiser.

Python ne permet pas que cela se produise. L'interpréteur limite le nombre maximum de fois qu'une fonction peut s'appeler récursivement, et quand il atteint cette limite, il lève un RecursionError exception, comme vous le voyez ci-dessus.

>>> de sys importer getrecursionlimit
>>> getrecursionlimit()
1000

>>> de sys importer setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

Il n’ya pas beaucoup d’utilité pour une fonction de s’appeler sans distinction de manière récursive sans fin. Cela rappelle les instructions que vous trouvez parfois sur les bouteilles de shampoing: "Faire mousser, rincer, répéter." Si vous deviez suivre ces instructions à la lettre, vous feriez un shampooing pour toujours!

Ce défaut logique s'est manifestement produit chez certains fabricants de shampoing, car certains flacons de shampoing disent à la place «Faire mousser, rincer, répéter le cas échéant. » Cela fournit une condition de résiliation aux instructions. Vraisemblablement, vous finirez par sentir que vos cheveux sont suffisamment propres pour que des répétitions supplémentaires ne soient pas nécessaires. Le shampooing peut alors s'arrêter.

De même, une fonction qui s'appelle elle-même de manière récursive doit avoir un plan pour s'arrêter éventuellement. Les fonctions récursives suivent généralement ce modèle:

• Il existe un ou plusieurs cas de base qui peuvent être résolus directement sans qu'il soit nécessaire de recourir à une récursion supplémentaire.
• Chaque appel récursif rapproche progressivement la solution d'un cas de base.

Vous êtes maintenant prêt à voir comment cela fonctionne avec quelques exemples.

Commencez: comptez à zéro

Le premier exemple est une fonction appelée compte à rebours(), qui prend un nombre positif comme argument et imprime les nombres de l'argument spécifié jusqu'à zéro:

>>> def compte à rebours(n):
...     imprimer(n)
...     si n == 0:
...         revenir             # Mettre fin à la récursivité
...     autre:
...         compte à rebours(n - 1)   # Appel récursif
...

>>> compte à rebours(5)
5
4
3
2
1
0

Remarquez comment compte à rebours() correspond au paradigme d'un algorithme récursif décrit ci-dessus:

• Le cas de base se produit lorsque n est zéro, à quel point la récursivité s'arrête.
• Dans l'appel récursif, l'argument est un de moins que la valeur actuelle de n, de sorte que chaque récursion se rapproche du cas de base.

La version de compte à rebours() ci-dessus met clairement en évidence le cas de base et l'appel récursif, mais il existe une manière plus concise de l'exprimer:

def compte à rebours(n):
    imprimer(n)
    si n > 0:
        compte à rebours(n - 1)

Voici une implémentation non récursive possible à des fins de comparaison:

>>> def compte à rebours(n):
...     tandis que n > = 0:
...         imprimer(n)
...         n - = 1
...

>>> compte à rebours(5)
5
4
3
2
1
0

C'est un cas où la solution non récursive est au moins aussi claire et intuitive que la solution récursive, et probablement plus.

Calcul factoriel

L'exemple suivant concerne le concept mathématique de factorielle. La factorielle d'un entier positif n, noté n!, est défini comme suit:

Autrement dit, n! est le produit de tous les nombres entiers de 1 à n, inclus.

Factorielle se prête tellement à une définition récursive que les textes de programmation l'incluent presque toujours comme l'un des premiers exemples. Vous pouvez exprimer la définition de n! récursivement comme ceci:

Comme dans l'exemple ci-dessus, il existe des cas de base qui peuvent être résolus sans récursivité. Les cas les plus compliqués sont réductrice, ce qui signifie qu'ils se réduisent à l'un des cas de base:

• Les cas de base (n = 0 ou n = 1) sont résolubles sans récursivité.
• Pour les valeurs de n supérieur à 1, n! est défini en termes de (n – 1) !, donc la solution récursive s'approche progressivement du cas de base.

Par exemple, le calcul récursif de 4! ressemble à ça:

Les calculs de 4 !, 3 !, et 2! suspendre jusqu'à ce que l'algorithme atteigne le cas de base où n = 1. À ce stade, 1! est calculable sans autre récursivité, et les calculs différés sont exécutés jusqu'à la fin.

>>> def factorielle(n):
...     revenir 1 si n <= 1 autre n * factorielle(n - 1)
...

>>> factorielle(4)
24

>>> def factorielle(n):
...     imprimer(F"factorielle () appelée avec n = n")
...     return_value = 1 si n <= 1 autre n * factorielle(n -1)
...     imprimer(F"-> factorielle (n) Retour return_value")
...     revenir return_value
...

>>> factorielle(4)
factorielle () appelée avec n = 4
factorielle () appelée avec n = 3
factorielle () appelée avec n = 2
factorielle () appelée avec n = 1
-> factorial (1) renvoie 1
-> factorial (2) renvoie 2
-> factorielle (3) renvoie 6
-> factorielle (4) renvoie 24
24

>>> def factorielle(n):
...     return_value = 1
...     pour je dans intervalle(2, n + 1):
...         return_value * = je
...     revenir return_value
...

>>> factorielle(4)
24

>>> de functools importer réduire
>>> def factorielle(n):
...     revenir réduire(lambda X, y: X * y, intervalle(1, n + 1) ou alors [[[[1])
...

>>> factorielle(4)
24

timeit(<commander>, mettre en place= <setup_string>, numéro= <itérations>)

>>> de timeit importer timeit

>>> timeit("imprimer (chaîne)", mettre en place="string = 'foobar'", numéro=100)
foobar
foobar
foobar
            .
            . [100 repetitions]
            .
foobar
0,03347089999988384

>>> setup_string = "" "
... print ("Récursif:")
... def factorielle (n):
...                 renvoie 1 si n <= 1 sinon n * factorielle (n - 1)
... "" "

>>> de timeit importer timeit
>>> timeit("factoriel (4)", mettre en place=setup_string, numéro=10 000 000)
Récursif:
4,957105500000125

>>> setup_string = "" "
... print ("Itératif:")
... def factorielle (n):
...                 return_value = 1
...                 pour i dans la plage (2, n + 1):
...                                 return_value * = i
...                 return return_value
... "" "

>>> de timeit importer timeit
>>> timeit("factoriel (4)", mettre en place=setup_string, numéro=10 000 000)
Itératif:
3,733752099999947

>>> setup_string = "" "
... à partir de functools importer réduire
... print ("réduire ():")
... def factorielle (n):
...                 return réduire (lambda x, y: x * y, range (1, n + 1) ou [1])
... "" "

>>> de timeit importer timeit
>>> timeit("factoriel (4)", mettre en place=setup_string, numéro=10 000 000)
réduire():
8,101526299999932

>>> de math importer factorielle
>>> factorielle(4)
24

>>> setup_string = "à partir de la factorielle d'importation mathématique"

>>> de timeit importer timeit
>>> timeit("factoriel (4)", mettre en place=setup_string, numéro=10 000 000)
0,3724050999999946

Traverser une liste imbriquée

L'exemple suivant consiste à visiter chaque élément dans une structure de liste imbriquée. Considérez la liste Python suivante:

des noms = [[[[
    "Adam",
    [[[[
        "Bob",
        [[[[
            "Chet",
            "Chat",
        ],
        "Barbillon",
        «Bert»
    ],
    «Alex»,
    [[[[
        "Être un",
        "Facture"
    ],
    «Ann»
]

Comme le montre le diagramme suivant, des noms contient deux sous-listes. La première de ces sous-listes contient elle-même une autre sous-liste:

Supposons que vous vouliez compter le nombre de éléments de feuille dans cette liste – le niveau le plus bas str objets, comme si vous aviez aplati la liste. Les éléments de la feuille sont "Adam", "Bob", "Chet", "Chat", "Barbillon", «Bert», «Alex», "Être un", "Facture", et «Ann», donc la réponse devrait être dix.

Juste appeler len () sur la liste ne donne pas la bonne réponse:

len () compte les objets au niveau supérieur de des noms, qui sont les trois éléments de feuille "Adam", «Alex», et «Ann» et deux sous-listes ["Bob", ["Chet", "Cat"], "Barb", "Bert"] et ["Bea", "Bill"]:

>>> pour indice, Objet dans énumérer(des noms):
...     imprimer(indice, Objet)
...
0 Adam
1 ['Bob', ['Chet', 'Cat'], 'Barb', 'Bert']
2 Alex
3 ['Bea', 'Bill']
4 Ann

Ce dont vous avez besoin ici est une fonction qui parcourt toute la structure de la liste, sous-listes incluses. L'algorithme va quelque chose comme ceci:

1. Parcourez la liste en examinant chaque élément à tour de rôle.
2. Si vous trouvez un élément feuille, ajoutez-le au décompte accumulé.
3. Si vous rencontrez une sous-liste, procédez comme suit:
   • Descendez dans cette sous-liste et parcourez-la de la même manière.
   • Une fois que vous avez épuisé la sous-liste, remontez, ajoutez les éléments de la sous-liste au décompte accumulé, puis reprenez la navigation dans la liste parente là où vous vous êtes arrêté.

Notez la nature autoréférentielle de cette description: Parcourez la liste. Si vous rencontrez une sous-liste, alors de la même manière parcourir cette liste. Cette situation demande une récursion!

>>> des noms
['Adam'['Adam'['Adam'['Adam'['Bob', ['Chet', 'Cat'], 'Barb', 'Bert'], «Alex», ['Bea', 'Bill'], 'Ann']

>>> des noms[[[[0]
'Adam'
>>> isinstance(des noms[[[[0], liste)
Faux

>>> des noms[[[[1]
['Bob', ['Chet', 'Cat'], 'Barb', 'Bert']
>>> isinstance(des noms[[[[1], liste)
Vrai

>>> des noms[[[[1][[[[1]
['Chet', 'Cat']
>>> isinstance(des noms[[[[1][[[[1], liste)
Vrai

>>> des noms[[[[1][[[[1][[[[0]
«Chet»
>>> isinstance(des noms[[[[1][[[[1][[[[0], liste)
Faux

def count_leaf_items(liste des articles):
    "" "Compte et renvoie récursivement
                            nombre d'éléments feuille dans un (potentiellement
                            liste imbriquée).
                "" "
    compter = 0
    pour Objet dans liste des articles:
        si isinstance(Objet, liste):
            compter + = count_leaf_items(Objet)
        autre:
            compter + = 1

    revenir compter

>>> count_leaf_items([[[[1, 2, 3, 4])
4
>>> count_leaf_items([[[[1, [[[[2,1, 2.2], 3])
4
>>> count_leaf_items([])
0

>>> count_leaf_items(des noms)
dix
>>> # Succès!

    1def count_leaf_items(liste des articles):
    2    "" "Compte et renvoie récursivement
    3                            nombre d'éléments feuille dans un (potentiellement
    4                            liste imbriquée).
    5                "" "
    6    imprimer(F"Lister: liste des articles")
    7    compter = 0
    8    pour Objet dans liste des articles:
    9        si isinstance(Objet, liste):
dix            imprimer("Sous-liste rencontrée")
11            compter + = count_leaf_items(Objet)
12        autre:
13            imprimer(F"Élément feuille compté  "Objet "")
14            compter + = 1
15
16    imprimer(F"-> Nombre de retours compter")
17    revenir compter

>>> count_leaf_items(des noms)
Lister:['Adam'['Adam'['Adam'['Adam'['Bob', ['Chet', 'Cat'], 'Barb', 'Bert'], «Alex», ['Bea', 'Bill'], 'Ann']
Élément feuille compté "Adam"
Sous-liste rencontrée
Lister: ['Bob', ['Chet', 'Cat'], 'Barb', 'Bert']
Élément feuille compté "Bob"
Sous-liste rencontrée
Lister: ['Chet', 'Cat']
Élément feuille compté "Chet"
Élément feuille compté "Chat"
-> Nombre de retours 2
Objet feuille compté "Barb"
Feuille comptée "Bert"
-> Nombre de retours 5
Élément feuille compté "Alex"
Sous-liste rencontrée
Lister: ['Bea', 'Bill']
Élément feuille compté "Bea"
Élément feuille compté "Bill"
-> Nombre de retours 2
Élément feuille compté "Ann"
-> Nombre de retours 10
dix

Traverser une liste imbriquée de manière non récursive

Comme les autres exemples présentés jusqu'à présent, ce parcours de liste ne nécessite pas de récursivité. Vous pouvez également l'accomplir de manière itérative. Voici une possibilité:

def count_leaf_items(liste des articles):
    "" "Compte et renvoie de manière non récursive
                            nombre d'éléments feuille dans un (potentiellement
                            liste imbriquée).
                "" "
    compter = 0
    empiler = []
    liste_actuelle = liste des articles
    je = 0

    tandis que Vrai:
        si je == len(liste_actuelle):
            si liste_actuelle == liste des articles:
                revenir compter
            autre:
                liste_actuelle, je = empiler.pop()
                je + = 1

        si isinstance(liste_actuelle[[[[je], liste):
            empiler.ajouter([[[[liste_actuelle, je])
            liste_actuelle = liste_actuelle[[[[je]
            je = 0

        compter + = 1
        je + = 1

Si vous exécutez cette version non récursive de count_leaf_items () sur les mêmes listes que précédemment, vous obtenez les mêmes résultats:

>>>

>>> count_leaf_items([[[[1, 2, 3, 4])
4
>>> count_leaf_items([[[[1, [[[[2,1, 2.2], 3])
4
>>> count_leaf_items([])
0

>>> count_leaf_items(des noms)
dix
>>> # Succès!

La stratégie employée ici utilise une pile pour gérer les sous-listes imbriquées. Lorsque cette version de count_leaf_items () rencontre une sous-liste, il pousse la liste actuellement en cours et l'index actuel de cette liste sur une pile. Une fois qu'elle a compté la sous-liste, la fonction fait apparaître la liste parent et l'index de la pile afin qu'elle puisse reprendre le comptage là où elle s'était arrêtée.

En fait, la même chose se produit essentiellement dans l'implémentation récursive. Lorsque vous appelez une fonction de manière récursive, Python enregistre l'état de l'instance en cours d'exécution sur une pile afin que l'appel récursif puisse s'exécuter. Lorsque l'appel récursif se termine, l'état est extrait de la pile afin que l'instance interrompue puisse reprendre. C’est le même concept, mais avec la solution récursive, Python fait le travail d’économie d’état à votre place.

Notez à quel point le code récursif est concis et lisible par rapport à la version non récursive:

C'est un cas où l'utilisation de la récursivité est définitivement un avantage.

Détecter les palindromes

Le choix d'utiliser ou non la récursivité pour résoudre un problème dépend en grande partie de la nature du problème. Factorielle, par exemple, se traduit naturellement par une implémentation récursive, mais la solution itérative est également assez simple. Dans ce cas, c'est sans doute un tirage au sort.

Le problème de la traversée de liste est une autre histoire. Dans ce cas, la solution récursive est très élégante, tandis que la solution non récursive est au mieux encombrante.

Pour le problème suivant, l'utilisation de la récursivité est sans doute ridicule.

UNE palindrome est un mot qui lit la même chose en arrière qu'en avant. Les exemples incluent les mots suivants:

• Voiture de course
• Niveau
• Kayak
• Reviver
• Civique

Si on vous demande de concevoir un algorithme pour déterminer si une chaîne est palindromique, vous obtiendrez probablement quelque chose comme "Inverser la chaîne et voir si elle est la même que l'original." Vous ne pouvez pas être plus clair que cela.

Encore plus utile, Python [::-1] La syntaxe de découpage pour inverser une chaîne fournit un moyen pratique de la coder:

>>> def is_palindrome(mot):
...     "" "Renvoie True si le mot est un palindrome, False sinon." ""
...     revenir mot == mot[::[::[::[::-1]
...

>>> is_palindrome("toto")
Faux
>>> is_palindrome("voiture de course")
Vrai
>>> is_palindrome("troglodyte")
Faux
>>> is_palindrome("civique")
Vrai

C'est clair et concis. Il n’est guère nécessaire de chercher une alternative. Mais juste pour le plaisir, considérez cette définition récursive d'un palindrome:

• Cas de base: Une chaîne vide et une chaîne composée d'un seul caractère sont intrinsèquement palindromiques.
• Récursivité réductrice: Une chaîne de longueur deux ou plus est un palindrome si elle satisfait à ces deux critères:
  1. Les premier et dernier caractères sont les mêmes.
  2. La sous-chaîne entre le premier et le dernier caractère est un palindrome.

Le tranchage est aussi votre ami ici. Pour une chaîne mot, l'indexation et le découpage donnent les sous-chaînes suivantes:

• Le premier caractère est mot[0].
• Le dernier caractère est mot[-1].
• La sous-chaîne entre le premier et le dernier caractère est mot[1:-1].

Ainsi, vous pouvez définir is_palindrome () récursivement comme ceci:

>>> def is_palindrome(mot):
...     "" "Renvoie True si le mot est un palindrome, False sinon." ""
...     si len(mot) <= 1:
...         revenir Vrai
...     autre:
...         revenir mot[[[[0] == mot[[[[-1] et is_palindrome(mot[[[[1:-1])
...

>>> # Cas de base
>>> is_palindrome("")
Vrai
>>> is_palindrome("une")
Vrai

>>> # Cas récursifs
>>> is_palindrome("toto")
Faux
>>> is_palindrome("voiture de course")
Vrai
>>> is_palindrome("troglodyte")
Faux
>>> is_palindrome("civique")
Vrai

C’est un exercice intéressant de penser de manière récursive, même lorsque ce n’est pas particulièrement nécessaire.

Trier avec Quicksort

Le dernier exemple présenté, comme le parcours de liste imbriquée, est un bon exemple de problème qui suggère très naturellement une approche récursive. L'algorithme Quicksort est un algorithme de tri efficace développé par l'informaticien britannique Tony Hoare en 1959.

Quicksort est un algorithme de division et de conquête. Supposons que vous ayez une liste d'objets à trier. Vous commencez par choisir un élément de la liste, appelé le pivot Objet. Cela peut être n'importe quel élément de la liste. Toi alors cloison la liste en deux sous-listes en fonction de l'élément pivot et trier de manière récursive les sous-listes.

Les étapes de l'algorithme sont les suivantes:

• Choisissez l'élément pivot.
• Partitionnez la liste en deux sous-listes:
  1. Les éléments inférieurs à l'élément pivot
  2. Les éléments supérieurs à l'élément pivot
• Tri rapide des sous-listes de manière récursive.

Chaque partitionnement produit des sous-listes plus petites, l'algorithme est donc réducteur. Les cas de base se produisent lorsque les sous-listes sont vides ou ont un élément, car ils sont triés par nature.

Choix de l'élément pivot

L'algorithme Quicksort fonctionnera quel que soit l'élément de la liste qui est l'élément pivot. Mais certains choix sont meilleurs que d'autres. N'oubliez pas que lors du partitionnement, deux sous-listes sont créées: une avec des éléments inférieurs à l'élément pivot et l'autre avec des éléments supérieurs à l'élément pivot. Idéalement, les deux sous-listes ont à peu près la même longueur.

Imaginez que votre liste initiale à trier contienne huit éléments. Si chaque partitionnement aboutit à des sous-listes de longueur à peu près égale, vous pouvez atteindre les cas de base en trois étapes:

À l'autre bout du spectre, si votre choix d'élément de pivot est particulièrement malchanceux, chaque partition se traduit par une sous-liste qui contient tous les éléments d'origine à l'exception de l'élément de pivot et une autre sous-liste qui est vide. Dans ce cas, il faut sept étapes pour réduire la liste aux cas de base:

L'algorithme Quicksort sera plus efficace dans le premier cas. Mais vous devez savoir quelque chose à l'avance sur la nature des données que vous triez afin de choisir systématiquement les éléments de pivot optimaux. Dans tous les cas, il n’ya pas un seul choix qui conviendra le mieux à tous les cas. Donc, si vous écrivez une fonction Quicksort pour gérer le cas général, le choix de l'élément pivot est quelque peu arbitraire.

Le premier élément de la liste est un choix courant, tout comme le dernier élément. Celles-ci fonctionneront bien si les données de la liste sont distribuées de manière assez aléatoire. Cependant, si les données sont déjà triées, ou même presque, cela entraînera un partitionnement sous-optimal comme celui illustré ci-dessus. Pour éviter cela, certains algorithmes de tri rapide choisissent l'élément central de la liste comme élément pivot.

Une autre option consiste à trouver la médiane du premier, du dernier et du milieu des éléments de la liste et à l'utiliser comme élément de pivot. Il s'agit de la stratégie utilisée dans l'exemple de code ci-dessous.

Utilisation de l'implémentation Quicksort

Maintenant que les bases sont en place, vous êtes prêt à passer à l'algorithme Quicksort. Voici le code Python:

    1importer statistiques
    2
    3def tri rapide(Nombres):
    4    si len(Nombres) <= 1:
    5        revenir Nombres
    6    autre:
    7        pivot = statistiques.médian(
    8            [[[[
    9                Nombres[[[[0],
dix                Nombres[[[[len(Nombres) // 2],
11                Nombres[[[[-1]
12            ]
13        )
14        items_less, pivot_items, items_greater = (
15            [[[[n pour n dans Nombres si n < pivot],
16            [[[[n pour n dans Nombres si n == pivot],
17            [[[[n pour n dans Nombres si n > pivot]
18        )
19
20        revenir (
21            tri rapide(items_less) +
22            pivot_items +
23            tri rapide(items_greater)
24        )

C'est ce que chaque section de tri rapide() fait:

• Ligne 4: Les cas de base où la liste est vide ou n'a qu'un seul élément
• Lignes 7 à 13: Calcul de l'élément pivot par la méthode de la médiane de trois
• Lignes 14 à 18: Création des trois listes de partitions
• Lignes 20 à 24: Tri récursif et réassemblage des listes de partitions

Noter: Cet exemple a l'avantage d'être succinct et relativement lisible. Cependant, ce n’est pas la mise en œuvre la plus efficace. En particulier, la création des listes de partitions sur les lignes 14 à 18 implique une itération dans la liste trois fois distinctes, ce qui n’est pas optimal du point de vue du temps d’exécution.

Voici quelques exemples de tri rapide() en action:

>>>

>>> # Cas de base
>>> tri rapide([])
[]
>>> tri rapide([[[[42])
[42]

>>> # Cas récursifs
>>> tri rapide([[[[5, 2, 6, 3])
[2, 3, 5, 6]
>>> tri rapide([[[[dix, -3, 21, 6, -8])
[-8, -3, 6, 10, 21]

À des fins de test, vous pouvez définir une fonction courte qui génère une liste de nombres aléatoires entre 1 et 100:

importer Aléatoire

def get_random_numbers(longueur, le minimum=1, maximum=100):
    Nombres = []
    pour _ dans intervalle(longueur):
        Nombres.ajouter(Aléatoire.Randint(le minimum, maximum))

    revenir Nombres

Maintenant, vous pouvez utiliser get_random_numbers () tester tri rapide():

>>>

>>> Nombres = get_random_numbers(20)
>>> Nombres
[24, 4, 67, 71, 84, 63, 100, 94, 53, 64, 19, 89, 48, 7, 31, 3, 32, 76, 91, 78]
>>> tri rapide(Nombres)
[3, 4, 7, 19, 24, 31, 32, 48, 53, 63, 64, 67, 71, 76, 78, 84, 89, 91, 94, 100]

>>> Nombres = get_random_numbers(15, -50, 50)
>>> Nombres
[-2, 14, 48, 42, -48, 38, 44, -25, 14, -14, 41, -30, -35, 36, -5]
>>> tri rapide(Nombres)
[-48, -35, -30, -25, -14, -5, -2, 14, 14, 36, 38, 41, 42, 44, 48]

>>> tri rapide(get_random_numbers(dix, maximum=500))
[49, 94, 99, 124, 235, 287, 292, 333, 455, 464]
>>> tri rapide(get_random_numbers(dix, 1000, 2000))
[1038, 1321, 1530, 1630, 1835, 1873, 1900, 1931, 1936, 1943]

Pour mieux comprendre comment tri rapide() fonctionne, voir le diagramme ci-dessous. Cela montre la séquence de récursivité lors du tri d'une liste de douze éléments:

Dans la première étape, les valeurs de la première, du milieu et de la dernière liste sont 31, 92, et 28, respectivement. La médiane est 31, de sorte que cela devienne l'élément pivot. La première partition se compose alors des sous-listes suivantes:

Sous-liste	Articles
[18, 3, 18, 11, 28]	Les éléments inférieurs à l'élément pivot
[31]	L'élément pivot lui-même
[72, 79, 92, 44, 56, 41]	Les éléments supérieurs à l'élément pivot

Chaque sous-liste est ensuite partitionnée de manière récursive de la même manière jusqu'à ce que toutes les sous-listes contiennent un seul élément ou soient vides. Lorsque les appels récursifs reviennent, les listes sont réassemblées dans un ordre trié. Notez que dans l'avant-dernière étape à gauche, l'élément pivot 18 apparaît deux fois dans la liste, de sorte que la liste des éléments du pivot comporte deux éléments.

Conclusion

Cela conclut votre voyage à travers récursivité, une technique de programmation dans laquelle une fonction s'appelle elle-même. La récursivité n'est en aucun cas appropriée pour chaque tâche. Mais certains problèmes de programmation le crient pratiquement. Dans ces situations, c’est une excellente technique à avoir à votre disposition.

Dans ce didacticiel, vous avez appris:

• Ce que cela signifie pour une fonction de s'appeler récursivement
• Comment le conception des fonctions Python supportent la récursivité
• Quoi les facteurs à considérer lors du choix de résoudre ou non un problème de manière récursive
• Comment mettre en œuvre une fonction récursive en Python

Vous avez également vu plusieurs exemples d'algorithmes récursifs et les avez comparés aux solutions non récursives correspondantes.

Vous devriez maintenant être en bonne position pour reconnaître quand la récursion est nécessaire et être prêt à l'utiliser en toute confiance quand cela est nécessaire! Si vous souhaitez en savoir plus sur la récursivité en Python, consultez Penser récursivement en Python.