Forum |  HardWare.fr | News | Articles | PC | Prix | S'identifier | S'inscrire | Aide | Shop Recherche
1966 connectés 

  FORUM HardWare.fr
  Programmation
  Divers

  Programmation récursive ou itérative

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Programmation récursive ou itérative

n°2315786
rastafia
raphia
Posté le 24-05-2018 à 17:48:01  profilanswer
 

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é  :o  
 
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 :
 

Code :
  1. map (lambda(x) : x+1, [10, 20, 30])
  2. > [11, 21, 31]
  3. def ajouter1(l):
  4.     return map( lambda(x) : x+1, l)
  5. ajouter1([10, 20, 30])
  6. > [11, 21, 31]
  7. def ajouteur(k):
  8.     return lambda(l): map( lambda(x) : x+k, l)
  9. f = ajouteur(3)
  10. g = ajouter(7)
  11. f([10, 20, 30])
  12. > [13, 23, 33]
  13. g([10, 20, 30])
  14. > [17, 27, 37]


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 :

Code :
  1. def fact(n):
  2.     if n==0:
  3.         return 1
  4.     else:
  5.         return n*fact(n-1)


 
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.
 

Code :
  1. def fact_term(n,k=1):
  2.     if n==0:
  3.         return k
  4.     else:
  5.         return fact_term(n-1,k*n)


 
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 :

Code :
  1. def forever():
  2.     print("bonjour" )
  3.     forever()


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é:  [:louloup2]  
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/


Message édité par rastafia le 05-07-2018 à 11:06:26

---------------
Cantor est devenu fou
mood
Publicité
Posté le 24-05-2018 à 17:48:01  profilanswer
 

n°2315851
masklinn
í dag viðrar vel til loftárása
Posté le 25-05-2018 à 15:13:05  profilanswer
 

OK, et?

Citation :

Ce ne serait vraiment pas difficile à implanter.


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 [:spamafote]


---------------
I've never understood the compulsion to use Web technologies minus the Web's security and deployment models. It seems a bit like throwing the orange away and eating the peel. — @ justinschuh‬
n°2315855
rastafia
raphia
Posté le 25-05-2018 à 15:41:37  profilanswer
 

masklinn a écrit :

OK, et?

Citation :

Ce ne serait vraiment pas difficile à implanter.


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 [:spamafote]


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.

Message cité 1 fois
Message édité par rastafia le 25-05-2018 à 15:44:32

---------------
Cantor est devenu fou
n°2315857
masklinn
í dag viðrar vel til loftárása
Posté le 25-05-2018 à 16:03:44  profilanswer
 

rastafia a écrit :

A mon avis, c'est un faux argument


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

rastafia a écrit :

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.


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

rastafia a écrit :

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…


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).

rastafia a écrit :

Pourquoi python ne le fait-il pas ?


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.

rastafia a écrit :

Quand à changer de langage, c'est quasiment impossible, tant python est devenu incontournable. En prépa, c'est python ; en TS c'est python ; en L1 c'est python ; Sagemath est implanté comme une surcouche de python.


Sucks for you.

rastafia a écrit :

La question que j'ai envie de poser c'est plutôt : comment python a-t-il pu s'imposer ?


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

rastafia a écrit :

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…)


Lol.

rastafia a écrit :

- Pas de récursion terminale


Tout le monde s'en tape.

rastafia a écrit :

- Pas de véritable fonction du premier ordre


Bien sûr que si.

rastafia a écrit :

(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/)


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.

rastafia a écrit :

je cherche avant tout à échanger des points de vue.


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


Message édité par masklinn le 25-05-2018 à 16:07:45

---------------
I've never understood the compulsion to use Web technologies minus the Web's security and deployment models. It seems a bit like throwing the orange away and eating the peel. — @ justinschuh‬
n°2315858
rastafia
raphia
Posté le 25-05-2018 à 16:14:45  profilanswer
 

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 :D  
 
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.

Message cité 2 fois
Message édité par rastafia le 26-05-2018 à 17:11:34

---------------
Cantor est devenu fou
n°2315861
rastafia
raphia
Posté le 25-05-2018 à 16:19:06  profilanswer
 

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  :pt1cable:  
 

Citation :

I don't believe in recursion as the basis of all programming. This is a fundamental belief of certain computer scientists, especially those who love Scheme and like to teach programming by starting with a "cons" cell and recursion. But to me, seeing recursion as the basis of everything else is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool.


 
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.

Message cité 1 fois
Message édité par rastafia le 25-05-2018 à 16:44:08

---------------
Cantor est devenu fou
n°2315869
Anonymouse
Posté le 25-05-2018 à 17:00:09  profilanswer
 

rastafia a écrit :

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 :D  
 
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.

 


 
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.

n°2315870
masklinn
í dag viðrar vel til loftárása
Posté le 25-05-2018 à 17:02:44  profilanswer
 

rastafia a écrit :

Ce qui est sur c'est que lisp et scheme l'implémentaient dans les années 1970 :D


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 [:spamafote]

rastafia a écrit :

L'auteur, Guindo, le développeur de python, explique qu'il ne "crois pas" à la recursion terminale en tant que base de la programmation  :pt1cable:


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.

rastafia a écrit :

Citation :

I don't believe in recursion as the basis of all programming. This is a fundamental belief of certain computer scientists, especially those who love Scheme and like to teach programming by starting with a "cons" cell and recursion. But to me, seeing recursion as the basis of everything else is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool.

 

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.


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 [:spamafote]

Message cité 1 fois
Message édité par masklinn le 25-05-2018 à 17:08:26

---------------
I've never understood the compulsion to use Web technologies minus the Web's security and deployment models. It seems a bit like throwing the orange away and eating the peel. — @ justinschuh‬
n°2315873
rastafia
raphia
Posté le 25-05-2018 à 17:23:35  profilanswer
 

Anonymouse a écrit :


 
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.


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.


---------------
Cantor est devenu fou
n°2315875
rastafia
raphia
Posté le 25-05-2018 à 17:50:50  profilanswer
 

masklinn a écrit :


1. Bah il dit ce qu'il veut, apparemment toi tu crois l'inverse mais bon voilà, lui c'est le BDFL de Python.


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

masklinn a écrit :

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 [:spamafote]


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)

Code :
  1. >>> a = [[1, 2, 3], [4, 5, 6]]
  2. >>> a[0]
  3. [1, 2, 3]
  4. >>> [a[i][0] for i in range(0, 2)]
  5. [1, 4]


 
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  [:tinostar]  
 
Un jour je ferais mon propre langage  [:ach_lette]

Message cité 1 fois
Message édité par rastafia le 26-05-2018 à 10:10:45

---------------
Cantor est devenu fou
mood
Publicité
Posté le 25-05-2018 à 17:50:50  profilanswer
 

n°2315892
gilou
Modérateur
Modzilla
Posté le 26-05-2018 à 09:55:22  profilanswer
 

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+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --    In umbra igitur pugnabimus. --
n°2315894
rastafia
raphia
Posté le 26-05-2018 à 12:16:11  profilanswer
 

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.


Message édité par rastafia le 26-05-2018 à 12:24:56

---------------
Cantor est devenu fou
n°2315895
masklinn
í dag viðrar vel til loftárása
Posté le 26-05-2018 à 12:33:22  profilanswer
 

rastafia a écrit :

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


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

rastafia a écrit :

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.


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 [:spamafote]

rastafia a écrit :

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)

Code :
  1. >>> a = [[1, 2, 3], [4, 5, 6]]
  2. >>> a[0]
  3. [1, 2, 3]
  4. >>> [a[i][0] for i in range(0, 2)]
  5. [1, 4]



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

Message cité 1 fois
Message édité par masklinn le 26-05-2018 à 12:35:21

---------------
I've never understood the compulsion to use Web technologies minus the Web's security and deployment models. It seems a bit like throwing the orange away and eating the peel. — @ justinschuh‬
n°2315897
rastafia
raphia
Posté le 26-05-2018 à 12:42:54  profilanswer
 

masklinn a écrit :


pypy fait pas de tail rec


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

masklinn a écrit :


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 [:spamafote]


On a compris.
 

masklinn a écrit :


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


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  

Code :
  1. [a[i][0] for i in range(0, m)] ?


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


---------------
Cantor est devenu fou
n°2317439
potemkin
Optimisateur relativiste.
Posté le 28-06-2018 à 00:36:32  profilanswer
 

rastafia a écrit :


Je n'ai pas trouvé la réponse à ma question dans ton lien. Quel est la complexité de  

Code :
  1. [a[i][0] for i in range(0, m)] ?


 
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! :ouch:  1/ Tu te prends pas pour de la merde 2/ Tu dis beaucoup de merde [:cerveau cinoque]

n°2317453
rastafia
raphia
Posté le 28-06-2018 à 17:04:30  profilanswer
 

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 :
 

Code :
  1. def fibg(u0, u1, n):
  2.     if n==0:
  3.         return u0
  4.     else:
  5.         return fibg(u1, u0+u1, n-1)
  6.    
  7. def fib(n):
  8.     return fibg(0, 1, n)
  9. fib(1000)


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

Code :
  1. def fib(n):
  2.     a = 0
  3.     b = 1
  4.     for i in range(0, n):
  5.         c = b
  6.         b = a+b
  7.         a = c
  8.     return a
  9. fib(1000)


 
C'est tout ce que je voulais dire !


Message édité par rastafia le 28-06-2018 à 17:05:58

---------------
Cantor est devenu fou
n°2317683
Harkonnen
Modérateur
Un modo pour les bannir tous
Posté le 05-07-2018 à 10:40:10  profilanswer
 

Alors essaie celle ci :
 

Code :
  1. 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


---------------
J'ai un string dans l'array (Paris Hilton)
n°2317684
rastafia
raphia
Posté le 05-07-2018 à 10:43:51  profilanswer
 

Harkonnen a écrit :

Alors essaie celle ci :
 

Code :
  1. 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


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


Message édité par rastafia le 05-07-2018 à 10:44:59

---------------
Cantor est devenu fou
n°2317687
rastafia
raphia
Posté le 05-07-2018 à 10:53:32  profilanswer
 

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

Code :
  1. def fact1(n):
  2.     r = 1
  3.     for i in range(2, n+1):
  4.         r = r * i
  5.     return r


 

Code :
  1. def fact2(n):
  2.     if n <= 1:
  3.         return 1
  4.     else:
  5.         return n*fact(n-1)


 

Code :
  1. def fact_acc(n,a):
  2.     if n <= 1:
  3.         return a
  4.     else:
  5.         return fact_acc(n-1, a*n) # appel terminal
  6. def fact3(n):
  7.     return fact_acc(n, 1)


 
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 !


---------------
Cantor est devenu fou
n°2317688
Harkonnen
Modérateur
Un modo pour les bannir tous
Posté le 05-07-2018 à 11:01:32  profilanswer
 

Celle ci te convient mieux ? :o
(1 milliseconde sur mon poste, si elle te convient pas je te bannis [:petrus75])

 
Code :
  1. def fibo(n, cache):
  2.    if n in cache:
  3.        return cache[n]
  4.        
  5.    if n <= 1:
  6.        cache[n] = n
  7.        return n
  8.    else:
  9.        val = fibo(n-1, cache) + fibo(n-2, cache)
  10.        cache[n] = val
  11.        return val
  12.  
  13. n = 999
  14. cache = dict()
  15. print (fibo(n, cache))
  16. print(cache.values())



Message édité par Harkonnen le 05-07-2018 à 11:01:54

---------------
J'ai un string dans l'array (Paris Hilton)
n°2317689
Harkonnen
Modérateur
Un modo pour les bannir tous
Posté le 05-07-2018 à 11:03:48  profilanswer
 

rastafia a écrit :

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


 
Tu permets ?

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


---------------
J'ai un string dans l'array (Paris Hilton)
mood
Publicité
Posté le   profilanswer
 


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Divers

  Programmation récursive ou itérative

 

Sujets relatifs
programmation pythonPython Qgis et encodage UFT-8
Installation module python sans internetChallenge Python en ligne - 30 questions
[Python] Contrôle de saisie finExercice Python.
Python tkinter quizz calcul mentallentille convergente ^python
Gestion d'un planning PythonProblèmes pour commencer en python
Plus de sujets relatifs à : Programmation récursive ou itérative


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite) / Groupe LDLC / Shop HFR