OVH Cloud OVH Cloud

tail recursivity - recursivite terminale

57 réponses
Avatar
R12y
[ Attention: Xpost + follow-up ]

Bonjour,

A la Fac, on nous enseigne des langages, mais pas Python.
Sur certains de ces langages (Ocaml, mais c'est pas pour troller) faire un
truc "récursif terminal" permet de faire de la récursivité "très
profonde", en repoussant les limites du stack overflow.

J'aime bien ce "truc", moi. La récursivité ça m'a impressionné :-).

Le problème:
Au niveau professionel, OCaml n'est pas très implanté, et d'ailleurs je
suis plutot dans une boite où c'est Python qui règne en maître. Ce
n'est pas un mal, mais je recherche des exemples à difficulté
progressive de cas de recursivité terminale, et je cherche à savoir si
faire de la récursivité terminale sous Python procure (presque) les
mêmes avantages.

Auriez-vous des pistes?

PS: Je programme, c'est tout. Je ne connais pas _exactement_ pourquoi la
récursivité terminale permet ceci ou cela. Cela viendra un jour,
peut-etre, mais pour l'instant j'apprends :-)

--
SPIP, phpNuke, Plone, opengroupware... c'est bien
CPS c'est mieux: http://www.cps-project.org/
Hébergement de sites CPS: http://www.objectis.org/

10 réponses

1 2 3 4 5
Avatar
Laurent Pointal
Jacti wrote:
De toute façon, je considère Python comme un très mauvais langage
(je sais je vais à contre courant de l'avis de beaucoup de gens...) mais
j'ai travailler dans les compilateurs et je connais plus de 30 langages de
programmation et, donc,
je sais de quoi je parle...
Pourquoi les informaticiens ont-ils toujours des attirances pour les plus
mauvais langages
(C, C++, Python, Visual Basic, par exemple) ? Seraient-ils tous d'infâmes
bidouilleurs ?


Les informaticiens sont comme beaucoup de personnes, ils utilisent ce
qu'ils connaissent, ce qu'ils ont à leur disposition, ce qu'on leur
impose, ce qui peut s'adapter facilement à l'existant, ce qui permet de
s'interfacer avec des choses écrites ailleurs...

En effet, il y a une part de bidouille, mais pas forcément infâme.

La notion de 'bon' et 'mauvais' langage... est tout de même une
appréciation très personnelle. Le bon langage pour monsieur X est celui
qui lui permet de faire ce qu'il doit en un temps limité. Et le langage
est meilleur si cette production est réutilisable ailleurs et facilement
maintenable.

A+

Laurent, qui utilise Python de préférence... et d'autres langages quand
nécessaire.

Avatar
Laurent Pointal
bruno modulix wrote:

une préférence marquée pour la simplicité et la lisibilité...


Et ils le prouvent :-)

python -c "print '@'.join(['.'.join([w[::-1] for w in p.split('.')]) for
p in ''.split('@')])"

Avatar
Marc Lasson
[X-POST: f.c.l.python, f.c.l.caml. FU2: f.c.l.caml]
Do Re Mi chel La Si Do wrote:

OCaML a été développé avec des fonds publics français, et quelques capitaux
privés français. Cela n'a guère influencé ses créateurs de réaliser les
annonces aux USA d'abord, de ne produire que des versions et documentations
en anglais (le livre en français est une initiative privée de quelques
personnes, comme les rares textes et tutoriaux en français).

Je ne critique pas le fait de publier anglais, mais l'absence de publication
simultanée en français.

De plus, il faut voir comment est reçu, par l'INRIA, un développeur
indépendant (français, et qui paye ses impôts), qui voudrait quelques
renseignements. On lui suggère simplement de s'adresser ailleurs.


Peut-on savoir de quel nature sont ces renseignements ?
Je me vois mal contacter Denis Ritchie parce qu'un de mes programmes C
ne compile pas :). Plus serieusement, il existe deux mailing lists (une
est réservée aux débutants) remplies toutes deux de gens pleins de bonne
volonté certainement prêt à répondre à beaucoup de vos questions.

Tout ça n'encourage pas à regarder ce langage.


Je redirige votre post sur le groupe du langage caml, peut-être s'y
trouve-t-il des gens intéréssés par votre expérience.

De même, ce comportement discrédite un pan entier de la recherche française...
Hum, c'est certainement un problème de fond.

Les instituts de recherche sont-ils aujourd'hui adaptés pour répondre
aux besoins de tous les intêrets privés français ? Est-ce leur rôle ?
Je n'en sais rien.

--
Marc L.

Avatar
bruno modulix
Laurent Pointal wrote:
bruno modulix wrote:

une préférence marquée pour la simplicité et la lisibilité...


Et ils le prouvent :-)

python -c "print '@'.join(['.'.join([w[::-1] for w in p.split('.')]) for
p in ''.split('@')])"


Pour ceux qui tendraient à être imperméables à l'humour glacial et
sophistiqué, je précise que cette signature est une tentative - hélas
avortée - de faire du Perl en Python !-)

Sinon, en Ruby, c'est pas mal aussi...
--
bruno desthuilliers
ruby -e "print ''.split('@').collect{|p|
p.split('.').collect{|w| w.reverse}.join('.')}.join('@')"


Avatar
Blaise Li
Bruno Desthuilliers wrote in message
<4314beab$0$10020$:

C'est réellement plus efficace de faire comme ça


Je ne suis pas sûr que ça fasse une différence notable au point de vue
perfs, mais ça évite de polluer l'espace de nommage avec des détails
d'implémentation.

ou bien c'est limité
par l'intelligence du compilateur ?


???


Excusez-moi, j'ai mal formulé ma question, je parlais de l'efficacité du
fait de faire de la récursivité terminale avec python.

bli


Avatar
bruno modulix
Blaise Li wrote:
Bruno Desthuilliers wrote in message
<4314beab$0$10020$:


C'est réellement plus efficace de faire comme ça


Je ne suis pas sûr que ça fasse une différence notable au point de vue
perfs, mais ça évite de polluer l'espace de nommage avec des détails
d'implémentation.


ou bien c'est limité
par l'intelligence du compilateur ?


???



Excusez-moi, j'ai mal formulé ma question, je parlais de l'efficacité du
fait de faire de la récursivité terminale avec python.

Non, en Python ça n'apporte rien.


--
bruno desthuilliers
python -c "print '@'.join(['.'.join([w[::-1] for w in p.split('.')]) for
p in ''.split('@')])"



Avatar
bruno modulix
bruno modulix wrote:
Blaise Li wrote:

Bruno Desthuilliers wrote in message
<4314beab$0$10020$:



C'est réellement plus efficace de faire comme ça


Je ne suis pas sûr que ça fasse une différence notable au point de vue
perfs, mais ça évite de polluer l'espace de nommage avec des détails
d'implémentation.



ou bien c'est limité
par l'intelligence du compilateur ?


???



Excusez-moi, j'ai mal formulé ma question, je parlais de l'efficacité du
fait de faire de la récursivité terminale avec python.



Non, en Python ça n'apporte rien.
(cliqué trop vite...)

Ce n'est pas en l'occurrence un problème d'"intelligence" du
compilateur, mais un choix délibéré.

--
bruno desthuilliers
python -c "print '@'.join(['.'.join([w[::-1] for w in p.split('.')]) for
p in ''.split('@')])"




Avatar
Emmanuel Delahaye
R12y wrote on 29/08/05 :
La récursivité ça m'a impressionné :-).


La plupart des langages savent faire ça, à commencer par le C. Mais si
il n'y a plus de pile, ça pète quelque soit le langage. La récursivité
n'est pas conseillée en production si la vie des gens est en jeu
(avionique, nucléaire, médecine...). Ca reste un concept très
universitaire...

--
Emmanuel
The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html
The C-library: http://www.dinkumware.com/refxc.html

"Mal nommer les choses c'est ajouter du malheur au
monde." -- Albert Camus.

Avatar
bruno modulix
Emmanuel Delahaye wrote:
R12y wrote on 29/08/05 :

La récursivité ça m'a impressionné :-).



La plupart des langages savent faire ça, à commencer par le C. Mais si
il n'y a plus de pile, ça pète quelque soit le langage. La récursivité
n'est pas conseillée en production si la vie des gens est en jeu
(avionique, nucléaire, médecine...). Ca reste un concept très
universitaire...


Sais-tu, Emmanuel, qu'il y a une très vaste gammes d'applications
non-universitaires *et* non-critiques ?-)

Pour ma part, j'utilise très courament la récursion pour des parcours
d'arborescence (ce qui est courant dans mon domaine). Et je n'ai pas
grand chose d'un universitaire...



--
bruno desthuilliers
ruby -e "print ''.split('@').collect{|p|
p.split('.').collect{|w| w.reverse}.join('.')}.join('@')"
python -c "print '@'.join(['.'.join([w[::-1] for w in p.split('.')]) for
p in ''.split('@')])"


Avatar
Jacti

Jacti wrote:



[ Attention: Xpost + follow-up ]

(snip)


D'après ce post
(http://mail.python.org/pipermail/python-dev/2004-July/046150.html)
il ne semble pas que Python dérécursive la récursion terminale.


Non, mais c'est un choix volontaire. Le patch pour ça existe (en tous
cas il eu existé).


Et pourquoi ce choix "volontaire" ?


De toute façon, je considère Python comme un très mauvais langage


Heu... Tu a bien lu le warning en haut du message, et regardé sur quel
ng tu postais ?-)


Oui, et alors ?

(je sais je vais à contre courant de l'avis de beaucoup de gens...)


Oui, particulièrement ici...

mais
j'ai travailler dans les compilateurs et je connais plus de 30 langages de
programmation et, donc,
je sais de quoi je parle...


Au lieu d'affirmer péremptoirement, tu pourrais peut-être argumenter ?


Un langage qui utilise l'indentation comme forme syntaxique de bloc
ne peut pas être un "bon" langage... (c'est inexprimable en BNF).

Pourquoi les informaticiens ont-ils toujours des attirances pour les plus
mauvais langages
(C, C++, Python, Visual Basic, par exemple) ?


Cherchez l'intrus... Si tu place Python et VB dans la même catégorie, je
crains que tu ne saches pas si bien que ça de quoi tu parles...


Bien sûr que VB n'est pas sur le même plan que Python (tout de même !), VB
étant le "Canada Dry" des LOO mais du point de vue qui nous occupe ici,
ils sont aussi "sales" (même si ce n'est pas le même type de saletés).

Sinon, pour répondre à ta question:
http://www.laputan.org/gabriel/worse-is-better.html

Seraient-ils tous d'infâmes
bidouilleurs ?


Oui, bien sûr. C'est évident.

Ou peut-être trouvent-ils juste que l'ambiance sur comp.lang.lisp est
trop saturée de prétention, de suffisance et d'arrogance ?-)

En ce qui me concerne, Python me permet de faire ce que j'ai à faire
simplement et rapidement. Effectivement avec d'infâmes bidouilles, comme
par exemple :
- les fonctions en tant qu'objets de première classe
- les fermetures
- les expressions de liste
- les générateurs
- les descripteurs
- les métaclasses


C'est vraiment la redécouverte de la poudre !

Bref, si l'on mets de côté les deux derniers points, d'infâmes
bidouilles très ouvertements inspirées des langages fonctionnels...

Ah, oui, c'est vrai, pas de macros, pas de joli modèle mathématique, une
préférence marquée pour la simplicité et la lisibilité... C'est vrai que
c'est minable, Python, quand on y pense.


Bonjour la simplicité syntaxique de Python !!
On ne peut pas faire un VRAI système d'exploitation sans un mécanisme
de macros (bien que je n'aime pas ça, mais c'est un mal nécessaire...).

Dernière remarque : loin de moi l'idée d'un troll. J'utilise Usenet depuis 1985
et je connais les règles.

Jacti



1 2 3 4 5