EDIT : j'ai changé le titre et la catégorie de ce message qui me semblait trop polémique et pas assez général.
 
J'ai toujours préféré la programmation récursive à la programmation impérative, et plus ça va, plus je me rends compte que je suis assez isolé    
 
Je n'ai jamais aimé les affectation ni les variables globales. Je me suis donc naturellement penché vers les langage fonctionnels, le lambda-calcul, caml, scheme, etc. J'adore le fait qu'une fonction soit un objet "comme les autres", qui puisse être passé en paramètre, créé à la volée.
 
Par exemple, je trouve la fonction map, 20 ans après, encore magique :
 

Cet exemple d'ajouteur est sans doute un peu abscons, mais il me parait donner un bon exemple de l'expressivite de la fonction lambda. f et g sont des fonctions créées à la volée. A la fin de ce programme, il y a 4 fonctions : ajouter1, ajouteur, f et g.
 
Ajouteur prends un entier en paramètre et renvoie une fonction qui prends en paramètre une liste d'entiers pour renvoyer une liste d'entiers.
 
Les types sont :
ajouter1 : liste d'entiers -> liste d'entiers
ajouteur : entier -> (liste d'entiers -> liste d'entiers)
f : liste d'entiers -> liste d'entiers
g : liste d'entiers -> liste d'entiers
 
f et ajouter1 sont deux implémentations différentes d'une même fonction.
 
 
 
Ancien post :  
---------------------------------------------------------------------------
 
Bonjour,
 
Il y a quelque chose qui me rebute très fortement dans python : il n'implante pas la recursion terminale.
 
Un exemple pour expliquer un peu ce que c'est :

 
L'appel fact(1000) renvoie une erreur. En effet, la récursivité n'est pas terminale, la pile grandit à chaque appel. Et par défaut python n'accepte pas plus de 1000 appels récursifs emboités. Tout est normal.
 

 
L'appel fact_term(1000) renvoie une erreur. Pourtant l'appel est terminal. Si python implantait la récursivité terminale, cela ne devrait pas se produire.
 
Un autre exemple :

Un appel à forever() va écrire bonjour 999 fois puis planter. La cause en est la même : dépassement de capacité de la pile. Pourtant presque tous les compilateurs arrivent à voir qu'il n'est pas nécessaire de garder le contexte.
 
Je trouve extrêmement dommage que python ne gère pas la récursion terminale. Ce ne serait vraiment pas difficile à implanter. Le pire est que c'est un choix de l'auteur du langage (voir un des liens ci-dessous)
 
--- Liens ---
 
La page wikipédia sur la récursion terminale
https://fr.wikipedia.org/wiki/R%C3%A9cursion_terminale
 
Un post de forum dans lequel j'ai pris le premier exemple :
http://www.les-mathematiques.net/p [...] 29,1160987
 
Ce blog compare différents langage face à la récursion terminale. Attention : il affirme que toute fonction récursive peut être écrite sous forme terminale, je n'en ai aucune certitude
https://blog.fastconnect.fr/?p=174
 
L'auteur de ce blog est très critique avec Python (a propos de la récursion terminale bien sur, mais on y apprends aussi que True+True renvoie 2)
http://sucre.syntaxique.fr/doku.php?id=python
 
Ici on apprends que le créateur de Python a choisi de ne pas implanter cette fonctionnalité:    
http://neopythonic.blogspot.fr/200 [...] ation.html
 
D'autres billets de blog sur le même sujet et arrivant aux même conclusions :
http://flyingfrogblog.blogspot.fr/ [...] guido.html
http://funcall.blogspot.fr/2009/04 [...] thing.html
 
Un fil reddit sur le sujet :  
https://www.reddit.com/r/programmin [...] recursion/

OK, et?

Pas difficile non, mais ça augmente la difficulté du langage pour rien, ça devient beaucoup plus complexe si on ne veut pas perdre des infos de debugging/traceback (genre un appel de fonction terminal non-récursif, on veut pas perdre les stacktraces), pour un langage qui n'est pas spécialement adapté/aimant ce style (les appels de fonction en Python sont notablement lents, et il n'y a pas de facilités dans les tests de terminalité).
 
Si tu veux coder de manière fonctionnelle/récursive, utilises un autre langage

A mon avis, c'est un faux argument, si tu veux une pile d'appel complète il suffit d'ajouter à l'interpréteur et/ou au compilateur la possibilité de désactiver la récursion terminale à la demande. Le temps de débuguer ou définitivement si tu as décidé que ça ne te plaisait pas.
 
Je ne veux pas spécialement coder de manière fonctionnelle/récursive, je veux juste que le langage que j'utilise e m'empêche pas de le faire. TOUS les langages que je connais implémentent la récursion terminale, et ce depuis les années 70. Algol, Pascal, C, Java, C#, lisp, scheme, javascript, ruby... Pourquoi python ne le fait-il pas ?
 
 
Quand à changer de langage, c'est quasiment impossible, tant python est devenu incontournable. En en TS c'est python ; en prépa c'est python ; en L1 c'est python ; sagemath est implanté comme une surcouche de python.
 
La question que j'ai envie de poser c'est plutôt : comment python a-t-il pu s'imposer ?
Pas de typage fort (un booléen et un entier sont interchangeables; True+True = 1 ; après un if on peut mettre ce qu'on veut : un entier, une liste, une chaine de caractères... Une chaine/liste vide c'est converti en False, une chaine/liste non vide est converti en True)
- Pas de récursion terminale
- Pas de véritable fonction du premier ordre :
(les fonction anonyme sont implantées mais... ne doivent pas faire plus d'une ligne). Les lambda ont été volontairement bridées. (lien : http://sametmax.com/fonctions-anon [...] u-lambda/)
 
En fait, plus je regarde comment fonctionne python, plus je vois de défauts.
 
Et j'aimerais bien éviter les argument du style "si tu n'aimes pas utilise un autre langage", j'ai envie de comprendre les arguments des gens qui utilisent et aiment python, même si je ne serais pas forcément d'accord, je cherche avant tout à échanger des points de vue.

Et d'autres ont un avis différent. Deal.

Fantastique, maintenant t'as un flag à la con qui contrôle la sémantique du langage, et c'est foireux par défaut.

Putain c'est pas l'honnêteté qui t'étouffe. Ni javascript ni ruby ni C# ni java ne font de TCO (en tout cas dans leur implémentation de référence, c'est tellement pas supporté par la JVM que Clojure a un mot clé spécial pour activer la TCO), au niveau sémantique C non plus (les implémentations peuvent le faire mais c'est absolument pas obligatoire), idem Pascal, et je doute fort qu'Algol l'ait supporté sans même parler de l'avoir spécifié. Même Common Lisp ne requiert pas la TCO, et comme déjà noté en Clojure il faut faire l'appel de manière spécifique (et si tu veux ça c'est disponible).

T'as déjà eu la réponse: parce que les mainteneurs (GvR inclus) considèrent que ça n'a pas d'intérêt ou ne vaut pas le coup.

Sucks for you.

Écosystème, communauté, simplicité, éducation.

Lol.

Tout le monde s'en tape.

Bien sûr que si.

Une expression, et dans les faits c'est pas d'une importance massive, le langage n'encourage pas à leur utilisation (même en ignorant leurs limitations) et encourage la programmation impérative et les fonctions nommées. C'est une décision, que tu l'aimes ou pas.

C'est pas l'honnêteté qui t'étouffe (bis).

Je veux bien admettre que je n'ai pas testé tous les langages que j'ai cité, c'était sans aucun doute un très mauvais argument très mal introduit.
 
Ce qui est sur c'est que lisp et scheme l'implémentaient dans les années 1970  
 
Et pour ma défense, aucun des langages que j'ai cité ne limite arbitrairement la taille de la pile d'appel à 1000.
 
Pour le reste, je ne suis pas vraiment d'accord.  
 
Typiquement ajouter un flag pour implémenter la récursivité terminale ne change en rien la sémantique du langage. Ca ne change que le fonctionnement interne de la machine virtuelle ou le code généré.
 
Un même programme exécuté avec ou sans le flag aura exactement le même comportement. De même qu'un programme compilé avec gcc, qu'on mette le flag -O0 ou -O3 on aura le même comportement, bien que l'un des deux soit plus optimisé que l'autre.

As-tu lu ce lien ? http://neopythonic.blogspot.fr/200 [...] ation.html
 
L'auteur, Guindo, le développeur de python, explique qu'il ne "crois pas" à la recursion terminale en tant que base de la programmation    
 

 
En gros, il dit fuck le lambda-calcul, fuck les fonctions récursives, je ne crois qu'à la machine de Turing et à la programmation à effets de bords.

 
Non. Dans un cas tu as un "stack overflow." et dans l'autre non. Quand tu passes de -O0 à -O3 tu n'es pas sensé avoir des segfaults qui apparaissent ou disparaissent.

J'ai jamais dit que c'était pas implémentable, juste que tu racontais de la merde, et que la TCO n'est pas un modèle qui correspond à Python ou qui intéresse les mainteneurs du langage. Des langages avec TCO garantie j'en utilise ou ai utilisé (Erlang, Elm, OCaml/ReasonML, …)

Oui

Guido, et c'est le BDFL pas "le développeur", il y a des dizaines de membres de la "core team" et des centaines de contributeurs à CPython.

1. Bah il dit ce qu'il veut, apparemment toi tu crois l'inverse mais bon voilà, lui c'est le BDFL de Python.
2. Et dans les faits il a raison, tous les langages un tant soit peu utilisés et populaires sont basés sur ce modèle

C'est exactement pareil avec gcc. Si tu choisis l'option -O1, l'appel terminal récursifs ne sont pas optimisés. L'option -O3 inclus le flag -foptimize-sibling-calls qui optimise les appels récursifs terminaux.
 
Tu peux donc avoir un dépassement de pile ou de mémoire avec -O1 et pas avec -O3. Ce n'est pas ce qu'on appelle un changement de sémantique. Le code est le même et s'il aboutit le résultat sera exactement le même avec ou sans l'optimisation.

Certes. Il y a cependant des alternatives : https://pypy.org/ par exemple.
 

Je suis clairement de l'autre côté de la barrière. Je suis toujours surpris d'être isolé, j'ai l'impression de ne pas penser comme tout le monde. Je trouve la programmation récursive donne du code infiniment plus lisible.
 
Que le BDFL ne pense pas comme moi, c'est une chose. Qu'il refuse d'implémenter une petite optimisation est je trouve très dommage.
 
Un autre défaut que je vois à python : on ne sait pas ce qu'il fait en interne. On ne peut pas connaitre la complexité de ce qu'il fait.
 
Par exemple : on a une matrice n*m. Si on veut la première ligne, facile, on écrit "a[0]". Si on veut la première colonne, on va écrire [a[1][0] for i in range(0, m)].  
Mais combien temps ça prends ? Est-ce en O(m) (si oui c'est un problème)

 
Quand j'ai le choix je programme en scheme, mais il a beaucoup de défauts aussi (d'autres). Il a un peu le défaut inverse en fait, programmer à la turing (par exemple faire deux boucles imbriquées) est très compliqué en scheme    
 
Un jour je ferais mon propre langage  

rastafia, tu devrais jeter un oeil à Kotlin.
Il y a un mot clé dans le langage, tailrec, pour indiquer au compilo que la fonction est susceptible d'optimisation par tail recursion (sinon, le compilo ne cherchera pas à faire cette optimisation).
Et avec un mot clé dans le langage, on n'est pas dans le cas de figure d'un flag qui contrôle la sémantique du langage.
 
A+,

En fait je n'ai pas vraiment le choix : le logiciel libre qui remplace à la fois maple, matlab, scilab et les autres est sagemath, qui est une surcouche de python. Comme dans ma préparation j'ai choisi l'option C (algèbre et calcul formel) je mange du python tous les jours !
 
 
Et je suis toujours pas d'accord avec le fait qu'optimiser la récursivité terminale modifierait la sémantique du langage. Les compilateurs prennent des libertés que vous ne soupçonnez sans doute pas.
 
J'ai regardé une fois le code assembleur généré par gcc pour une petite boucle en C en comparant -O0 et -O3, j'ai été très très surpris.

pypy fait pas de tail rec, et je doute qu'ils en aient quoi que ce soit à foutre.

La partie la plus importante d'un projet c'est savoir dire non à des trucs inutiles ou néfastes. Pour les mainteneurs de cpython, la tailrec est inutile

T'en as pas marre de raconter des conneries en permanence un peu? CPython est open-source et l'implémentation est relativement simple à dessein, si tu voulais savoir ce qu'il fait en interne tu pourrais trivialement aller regarder au lieu de geindre.

https://github.com/python/cpython/b [...] ect.c#L196

Et ça c'est sans compter que la réponse à ton "interrogation" est documentée…

En effet. Je l'ai lu dans un forum et je n'ai pas vérifié.
 

On a compris.
 

Ok, ce n'est pas documenté donc il faut trouver l'information en lisant le code du compilateur. Super.
 
Je n'ai pas trouvé la réponse à ma question dans ton lien. Quel est la complexité de  

 
Essaie de répondre sans m'envoyer des fions pour changer. Je n'ai pas l'impression d'avoir été impoli à ton égard.

 
"Get Item O(1)"
m iterations > O(m)
 
Je ne faisais que passer, mais... wow!  1/ Tu te prends pas pour de la merde 2/ Tu dis beaucoup de merde

Merci pour ta réponse. Pour le reste... il y a sans doute du vrai.
 
Le thread a un peu dévié... Pour en revenir au sujet initial.
 
Je trouve très dommage que ce code ne fonctionne pas :
 

 
Alors que ce serait si facile de contenter tout le monde.
 
Je n'aime pas cette implémentation :

 
C'est tout ce que je voulais dire !

Alors essaie celle ci :
 

fib = lambda n: n if n < 2 else fib(n-1) + fib(n-2)

 
Et oui, en Python 3 les lambdas peuvent se référencer récursivement

fib = lambda n: n if n < 2 else fib(n-1) + fib(n-2)

Il n'y a pas pire implémentation de la fonction fib    
C'est l'exemple parfait si on veut montrer que ça ne marche pas    
 
J'aurais du faire un topic sur la programmation récursive, ça aurait été plus constructif et beaucoup moins polémique.

Typiquement, voici trois implémentation de la fonction factorielle.

 
La première, je ne l'aime pas, vous l'avez compris.
 
La seconde est la plus claire, mais elle dépends de la pile d'appel, et elle occupe O(n) en espace mémoire.
 
La troisième est donc ma préférée. Elle allie clarté et efficacité. Elle est un peu moins claire que la seconde mais on ne peut pas tout avoir !

Celle ci te convient mieux ?
(1 milliseconde sur mon poste, si elle te convient pas je te bannis )

def fibo(n, cache):
    if n in cache:
        return cache[n]
        
    if n <= 1:
        cache[n] = n
        return n
    else:
        val = fibo(n-1, cache) + fibo(n-2, cache)
        cache[n] = val
        return val
 
n = 999
cache = dict()
print (fibo(n, cache))
print(cache.values())

 
Tu permets ?

def fac(n):
    return 1 if (n < 1) else n * fac(n-1)