Deux façons d'écrire un one-liner récursif : (1) écrivez la fonction avec l'instruction de retour sur une seule ligne, comme dans def f(x): return f(x+1) , ou (2) attribuer une fonction lambda à un nom de variable et utiliser le nom de la variable dans l'expression de retour de la fonction lambda, comme dans f = lambda x: f(x) . Pour définir un cas de base de récursivité, vous pouvez utiliser l'opérateur ternaire x if c else y pour retourner x si état c est remplie, sinon y .
Plongeons-nous dans le problème et plusieurs exemples détaillés !
Problème :Comment écrire une fonction récursive en une seule ligne de code ?
Vous pouvez trouver cela difficile car vous devez définir le nom de la fonction, le cas de base et l'appel de fonction récursif, le tout sur une seule ligne de code Python !
Article connexe :Pour rafraîchir vos compétences générales en récursivité, consultez mon article de blog détaillé (y compris la vidéo).
Voici un aperçu des différents algorithmes, nous avons one-linerized récursivement! 😉
Exercice :Exécutez le code et testez les résultats. Sont-ils corrects ? Modifiez maintenant les entrées des cas de base de récursivité et exécutez à nouveau le code ! Sont-ils corrects ?
Plongeons-nous dans chacune de ces méthodes !
Méthode 1 :Fibonacci récursif
Que sont les nombres de Fibonacci ? Les nombres de Fibonacci sont les nombres de la série de Fibonacci. La série commence par les chiffres 0 et 1. Chaque élément de série suivant est la somme des deux éléments de série précédents. C'est déjà l'algorithme pour calculer la série de Fibonacci !
On considère le problème suivant :Soit un nombre n>2 . Calculez une liste des n premiers nombres de Fibonacci dans une seule ligne de code (en commençant par le premier nombre de Fibonacci 0) !
# Method 1: Recursive Fibonacci
def fib(n): return 1 if n in {0, 1} else fib(n-1) + fib(n-2)
print(fib(10))
# 89 Ce one-liner est basé sur ce référentiel Github mais rendu plus concis et plus lisible. Il utilise l'opérateur ternaire pour compresser la valeur de retour de la fonction.
Ternaire d'explication :l'opérateur ternaire le plus basique x if c else y se compose de trois opérandes x , c , et y . C'est une expression avec une valeur de retour. L'opérateur ternaire renvoie x si l'expression booléenne c évalue à True . Sinon, si l'expression c évalue à False , l'opérateur ternaire renvoie l'alternative y .
Méthode 2 :factorielle récursive
Considérez le problème suivant :il y a 20 équipes de football dans la première ligue anglaise. Chaque équipe peut éventuellement atteindre l'un des 20 rangs à la fin de la saison. Combien de classements possibles existe-t-il en Premier League, étant donné 20 équipes fixes ?
Figure :Exemple de trois classements possibles des équipes de football de la Premier League anglaise.
La figure montre trois classements différents des équipes. Dans la terminologie informatique, vous désigneriez chaque classement comme une "permutation". Une permutation est définie comme un ordre spécifique d'éléments d'ensemble (ici :équipes de football). En utilisant cette terminologie, notre objectif est de trouver le nombre de permutations d'un ensemble donné (l'ensemble de toutes les équipes de football). Le nombre de ces permutations a des implications importantes dans la pratique, telles que les applications de paris, la prédiction des matchs et l'analyse des matchs. Par exemple, en supposant 100 classements différents avec une probabilité égale, la probabilité d'un classement spécifique est de 1/100 =1 %. Cela peut être utilisé comme probabilité de base (probabilité a priori) pour les algorithmes de prédiction de jeu. Sous ces hypothèses, un classement deviné au hasard a une probabilité de 1 % d'être le résultat correct après une saison.
Comment calculer le nombre de permutations d'un ensemble donné ? Il s'avère que la fonction factorielle n! calcule le nombre de permutations d'un ensemble donné de n éléments. La factorielle est définie comme suit :
Par exemple :
Pourquoi la factorielle compte-t-elle le nombre de permutations d'un ensemble donné d'éléments ? La réponse est très simple :disons, vous avez un ensemble de dix éléments S = {s0, s1, ..., s9} et dix seaux B = {b0, b1, ..., b9} . Dans l'exemple du football, il y a vingt équipes (les éléments) et vingt rangs de table (les seaux). Pour obtenir une permutation de S
- Tout d'abord, vous prenez un élément aléatoire de l'ensemble
S. Dans combien de buckets pouvez-vous placer cet élément ? Il y a dix compartiments vides, vous avez donc dix options. - Deuxièmement, vous prenez l'élément suivant de l'ensemble. Dans combien de buckets pouvez-vous placer cet élément ? Il y a neuf compartiments vides, vous avez donc neuf options.
- …
- Enfin, vous prenez le dernier élément de l'ensemble. Dans combien de buckets pouvez-vous placer cet élément ? Il n'y a qu'un seul seau vide, vous n'avez donc qu'une seule option.
Au total, vous avez 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 =10 ! différentes options. Chaque option de placement d'éléments dans les compartiments représente une permutation des éléments définis. Le nombre de permutations d'un ensemble avec n éléments est n ! .
Vous savez maintenant tout ce que vous devez savoir pour résoudre le problème suivant :écrivez une solution Python à une ligne qui calcule le nombre de permutations n ! d'un ensemble avec n éléments.
# Method 2: Recursive Factorial def fac(x): return 1 if x<=1 else x * fac(x-1) print(fac(10)) # 3628800
Ce one-liner est basé sur ce post du forum mais, encore une fois, j'ai amélioré la lisibilité et la concision. Par exemple, c'est généralement une bonne idée de gérer d'abord le cas de base de la récursivité.
La fonction factorielle peut être définie récursivement comme
avec les cas de base de récursivité définis comme
L'intuition derrière ces cas de base est la suivante :un ensemble avec un élément a une permutation. Et un ensemble avec zéro élément a une permutation (il existe une façon d'affecter zéro élément à zéro compartiment).
Méthode 3 :Factorielle One-Liner avec Lambda
Une alternative pour calculer la factorielle récursive en une seule ligne est la suivante :
# Method 3: Recursive Factorial with Lambda fac = lambda n: 1 if n<=1 else n * fac(n-1) print(fac(10)) # 3628800
Le code utilise la définition récursive discutée précédemment. Il crée une fonction lambda avec un argument n . Il attribue la fonction lambda au nom fac . Enfin, il appelle la fonction nommée fac(n-1) pour calculer le résultat de la fonction appelez fac(n) . En utilisant la solution au problème le plus simple fac(n-1) , on peut construire la solution du problème le plus difficile fac(n) en le multipliant par l'argument d'entrée n . Dès que nous atteignons le cas de base de la récursivité n <= 1 , nous renvoyons simplement la solution codée en dur fac(1) = fac(0) = 1 .
Plongeons-nous dans un one-liner récursif plus avancé :l'algorithme Quicksort !
Méthode 4 :tri rapide récursif sur une seule ligne
Ensuite, vous découvrirez l'algorithme de tri populaire Quicksort. Étonnamment, une seule ligne de code Python suffit pour écrire l'algorithme Quicksort ! Ce code est basé sur ce tutoriel de blog détaillé. Si vous voulez plus d'explications, allez-y !
Quicksort trie une liste en divisant de manière récursive le gros problème (tri de la liste) en problèmes plus petits (tri de deux listes plus petites) et en combinant les solutions des problèmes plus petits de manière à résoudre le gros problème. Afin de résoudre chaque problème plus petit, la même stratégie est utilisée de manière récursive :les problèmes plus petits sont divisés en sous-problèmes encore plus petits, résolus séparément et combinés. En raison de cette stratégie, Quicksort appartient à la classe des algorithmes "Divide and Conquer". Approfondissons l'algorithme Quicksort :
L'idée principale de Quicksort est de sélectionner un élément pivot, puis de placer tous les éléments supérieurs ou égaux à l'élément pivot à droite et tous les éléments inférieurs à l'élément pivot à gauche. Maintenant, vous avez divisé le gros problème du tri de la liste en deux sous-problèmes plus petits :trier les partitions droite et gauche de la liste. Ce que vous faites maintenant est de répéter cette procédure de manière récursive jusqu'à ce que vous obteniez une liste avec zéro élément. Cette liste est déjà triée, donc la récursivité se termine.
La figure suivante montre l'algorithme Quicksort en action :
Figure :L'algorithme Quicksort sélectionne un élément pivot, divise la liste en (i) une sous-liste non triée avec tous les éléments inférieurs ou égaux au pivot, et (ii) une sous-liste non triée avec tous les éléments supérieurs à le pivot. Ensuite, l'algorithme Quicksort est appelé récursivement sur les deux sous-listes non triées pour les trier. Dès que les sous-listes contiennent au maximum un élément, elles sont triées par définition – la récursivité se termine. À chaque niveau de récursivité, les trois sous-listes (gauche, pivot, droite) sont concaténées avant que la liste résultante ne soit transmise au niveau de récursivité supérieur.
Cela nous amène au problème suivant :
Créer une fonction q qui implémente l'algorithme Quicksort dans une seule ligne de code Python - et trie ainsi tout argument donné sous la forme d'une liste d'entiers.
## The Data unsorted = [33, 2, 3, 45, 6, 54, 33] ## The One-Liner q = lambda l: q([x for x in l[1:] if x <= l[0]]) + [l[0]] + q([x for x in l if x > l[0]]) if l else [] ## The Result print(q(unsorted))
Liste :solution en une seule ligne pour l'algorithme Quicksort utilisant la récursivité.
Nous avons déjà discuté de l'algorithme récursif Quicksort ci-dessus. Le one-liner ressemble exactement à l'algorithme discuté. Tout d'abord, nous créons une nouvelle fonction lambda q qui ne prend qu'un seul argument de liste l . La fonction lambda a la structure suivante :
lambda l: q(left) + pivot + q(right) if l else []
La fonction lambda renvoie la liste vide [] dans le cas de base de la récursivité (c'est-à-dire que la liste à trier est vide et, par conséquent, triée trivialement). Dans tous les autres cas, il sélectionne l'élément pivot comme premier élément de la liste l , divise tous les éléments en deux sous-listes (gauche et droite) selon qu'ils sont plus petits ou plus grands que le pivot. Pour ce faire, nous utilisons la compréhension de liste simple. Comme les deux sous-listes ne sont pas nécessairement triées, nous exécutons récursivement l'algorithme Quicksort sur celles-ci. Enfin, nous combinons les trois listes et renvoyons la liste triée.
Par conséquent, le résultat est :
## The Result print(q(unsorted)) # [2, 3, 6, 33, 33, 45, 54]
Livre Python One-Liners :maîtrisez d'abord la ligne unique !
Les programmeurs Python amélioreront leurs compétences en informatique avec ces lignes utiles.
Python One-Liners vous apprendra à lire et à écrire des « lignes simples » :des déclarations concises de fonctionnalités utiles regroupées dans une seule ligne de code. Vous apprendrez à décompresser et à comprendre systématiquement n'importe quelle ligne de code Python, et à écrire du Python éloquent et puissamment compressé comme un expert.
Les cinq chapitres du livre couvrent (1) les trucs et astuces, (2) les expressions régulières, (3) l'apprentissage automatique, (4) les principaux sujets de science des données et (5) les algorithmes utiles.
Des explications détaillées des one-liners introduisent les concepts clés de l'informatique etdéveloppez vos compétences en matière de codage et d'analyse . Vous découvrirez les fonctionnalités Python avancées telles que la compréhension de liste , tranchage , fonctions lambda , expressions régulières , carte et réduire fonctions et affectations de tranches .
Vous apprendrez également à :
- Exploiter les structures de données pour résoudre des problèmes réels , comme utiliser l'indexation booléenne pour trouver des villes avec une pollution supérieure à la moyenne
- Utiliser les bases de NumPy comme tableau , forme , axe , tapez , diffusion , indexation avancée , tranchage , tri , recherche , agrégation , et statistiques
- Calculer des statistiques de base de tableaux de données multidimensionnels et les algorithmes K-Means pour l'apprentissage non supervisé
- Créer davantage d'expressions régulières avancées en utilisant le regroupement et groupes nommés , anticipations négatives , caractères échappés , espaces blancs, jeux de caractères (et jeux de caractères négatifs ) et opérateurs gourmands/non gourmands
- Comprendre un large éventail de sujets informatiques , y compris les anagrammes , palindromes , surensembles , permutations , factorielles , nombres premiers , Fibonacci chiffres, obscurcissement , recherche , et tri algorithmique
À la fin du livre, vous saurez comment écrire Python dans sa forme la plus raffinée , et créez de belles pièces concises d'"art Python" en une seule ligne.
Obtenez vos Python One-Liners sur Amazon !!
