(je suis débutant en c) je ne vois d'instruction pour boucler
bpasc...@googlemail.com
Voici une fonction très simple qui réagit comme s'il y avait une
boucle alors qu'en apparence il n'y en a pas :
#include <stdio.h>
void f2(int b);
void f1(int a);
int main(void)
{
f1(30);
return 0;
}
void f1(int a)
{
if( a )
f2( a - 1 );
printf("%d ", a);
}
void f2(int b)
{
printf(" . ");
if(b)
f1( b - 1 );
}
http://www.java2s.com/Code/C/Function/Functioncalleachother.htm
Merci,
Pascal
Kojak
"bpasc...@googlemail.com" <bpasc...@googlemail.com> a écrit :
> Bjr,sr,
> Voici une fonction très simple qui réagit comme s'il y avait une
> boucle alors qu'en apparence il n'y en a pas :
Bis. Même constat et réponse que précédemment.
--
Jacques.
zwim
>Bjr,sr,
>Voici une fonction tr�s simple qui r�agit comme s'il y avait une
>boucle alors qu'en apparence il n'y en a pas :
>
>#include <stdio.h>
>
>void f2(int b);
>void f1(int a);
>
>int main(void)
>{
> f1(30);
>
> return 0;
>}
>
>void f1(int a)
>{
> if( a )
> f2( a - 1 );
> printf("%d ", a);
>}
>
>void f2(int b)
>{
> printf(" . ");
> if(b)
> f1( b - 1 );
>}
>
>http://www.java2s.com/Code/C/Function/Functioncalleachother.htm
>
>Merci,
>Pascal
Tu viens de d�couvrir la *r�cursivit�*
En voil� un autre exemple plus imbriqu� encore, la courbe de Hilbert
en mode tortue style logo : fcap(0); d(n);
/* -------------------------------------------------------- */
void d(int n);
void h(int n);
void b(int n);
void g(int n);
void d(int n)
{
if(n==0) return;
if(n>0)
{
h(n-1); fcap(K_NORD); av(2);
d(n-1); fcap(K_EST); av(2);
d(n-1); fcap(K_SUD); av(2);
b(n-1);
}
if(n>=6) flush_videobuf();
}
/* -------------------------------------------------------- */
void h(int n)
{
if(n==0) return;
if(n>0)
{
d(n-1); fcap(K_EST); av(2);
h(n-1); fcap(K_NORD); av(2);
h(n-1); fcap(K_OUEST); av(2);
g(n-1);
}
}
/* -------------------------------------------------------- */
void b(int n)
{
if(n==0) return;
if(n>0)
{
g(n-1); fcap(K_OUEST); av(2);
b(n-1); fcap(K_SUD); av(2);
b(n-1); fcap(K_EST); av(2);
d(n-1);
}
}
/* -------------------------------------------------------- */
void g(int n)
{
if(n==0) return;
if(n>0)
{
b(n-1); fcap(K_SUD); av(2);
g(n-1); fcap(K_OUEST); av(2);
g(n-1); fcap(K_NORD); av(2);
h(n-1);
}
}
--
zwim.
Rien n'est impossible que la mesure de la volont� humaine...
bpasc...@googlemail.com
J'avais le sentiment de quelque chose de récursif dans le résultat
mais je n'ai pas encore abordé le chapitre des fonctions en tant
qu'autodidacte en programmation. En plus, le site d'où le code vient
n'abuse pas des commentaires. Je pense ils ont juste balancé du code
de différents langages pour ceux qui ont déjà de bonnes bases.
Pour ton code, la récursivité est plus apparente que le code que j'ai
posté dans le sens qu'à l'intérieur d'une fonction, tu appelles cette
fonction : void g(int n) { ... g(n-1); ...}
Je comprendrais certainement mieux quand j'aborderais le chapitre des
fonctions.
Merci,
Pascal
candide
> J'avais le sentiment de quelque chose de r�cursif dans le r�sultat
> mais je n'ai pas encore abord� le chapitre des fonctions en tant
> qu'autodidacte en programmation.
Tu n'as pas abord� la question des fonctions en C et tu as ouvert un fil
sur fgets() ? c'est pas vraiment logique, apprendre c'est comme une
recette de cuisine, il suffit pas d'avoir les bons ingr�dients faut
aussi les utiliser dans le bon ordre ;) Faut reconna�tre aussi que les
livres ne sont pas un mod�le de logique en la mati�re.
> Pour ton code, la r�cursivit� est plus apparente que le code que j'ai
> post� dans le sens qu'� l'int�rieur d'une fonction, tu appelles cette
> fonction : void g(int n) { ... g(n-1); ...}
>
C'est de la r�cursivit� crois�e. Franchement, le code donn� est tr�s
artificiel, c'est vraiment un exercice de style et qui ne sert quasiment
jamais dans la pratique, le genre de code qui n'a pour effet que de
d�courager le d�butant et lui faire prendre la proie pour l'ombre.
> Je comprendrais certainement mieux quand j'aborderais le chapitre des
> fonctions.
Il y a plein de programmeurs C (C ou autre) qui n'ont jamais rien
compris � la r�cursivit� donc te crois pas oblig� de passer par ce
pensum (qui est aussi une belle tarte � la cr�me).
-ed-
<bpascal...@googlemail.com> wrote:
> Bjr,sr,
> Voici une fonction très simple qui réagit comme s'il y avait une
> boucle alors qu'en apparence il n'y en a pas :
C'est un appel récursif. Ça se comporte comme une boucle, oui, c'est
fait pour ...
Ça n'a rien de 'très simple'...
Mickaël Wolff
> Il y a plein de programmeurs C (C ou autre) qui n'ont jamais rien
> compris � la r�cursivit� donc te crois pas oblig� de passer par ce
> pensum (qui est aussi une belle tarte � la cr�me).
J'ai du mal � comprendre qu'on puisse se pr�tendre programmeur et ne
rien entendre � la r�cursivit�. Les pointeurs, � la rigueur, je peux
comprendre, mais la r�cursivit� ?
--
Micka�l Wolff aka Lupus Michaelis
http://lupusmic.org
Samuel Devulder
> candide a �crit :
>
>> Il y a plein de programmeurs C (C ou autre) qui n'ont jamais rien
>> compris � la r�cursivit� donc te crois pas oblig� de passer par ce
>> pensum (qui est aussi une belle tarte � la cr�me).
>
> J'ai du mal � comprendre qu'on puisse se pr�tendre programmeur et ne
> rien entendre � la r�cursivit�. Les pointeurs, � la rigueur, je peux
> comprendre, mais la r�cursivit� ?
>
Moi aussi. Sans la r�cursivit�, fini les structures d'arbres et autres
structures de donn�es "sophistiqu�es".
Souvent la r�cursivit� permet de coder avec peu de ligne des algos qui
s'ils sont "d�r�cursivis�s" deviennent super lourds � �crire, g�rer,
maitenir et qui n�c�ssitent du support du Runtime ou de l'OS tel que
l'allocation de m�moire dynamique.
Dans mon domaine (l'embarqu�), les OS n'ont pas toujours d'allocation
m�moire dynamique mais ils supportent tous une pile (pour appeller des
fonctions il vaut mieux), et dans ce cas la version r�cursive des algos
est pr�f�rable � celle qui fait des "malloc()".
Cela dit, dans ce domaine il faut se m�fier de la taille de ce que l'on
envoi sur la pile car cette derni�re n'est pas non plus toujours tr�s
grande (256octets � 1k parfois), mais cela permet quand m�me de
travailler sur des structures de donn�es r�alistes avec une profondeur
raisonnable. En effet si on empile 8 octets � chaque appel (un pointeur
de data et l'adresse de retour par exemple), alors il faut a peu pr�s
une profondeur de 32 avant de saturer les 256 octets de pile. C'est pas
mal du tout finalement.
sam.
bpasc...@googlemail.com
> Tu n'as pas abordé la question des fonctions en C et tu as ouvert un fil
> sur fgets() ? c'est pas vraiment logique, apprendre c'est comme une
> aussi les utiliser dans le bon ordre ;) Faut reconnaître aussi que les
> livres ne sont pas un modèle de logique en la matière.
A mon niveau, je distingue les fonctions "toutes faites" qui vont avec
stdio.h, string.h ... des fonctions que l'on "fabrique" avec
prototype, déclaration, définition... Je ne suis pas entièrement sûre
de ce que je dis mais je pense que ça explique en tant que débutant,
j'ai commencé avec les fonctions des librairies standards.
-ed-
<bpascal...@googlemail.com> wrote:
> A mon niveau, je distingue les fonctions "toutes faites" qui vont avec
> stdio.h, string.h ... des fonctions que l'on "fabrique" avec
> prototype, déclaration, définition... Je ne suis pas entièrement sûre
> de ce que je dis mais je pense que ça explique en tant que débutant,
> j'ai commencé avec les fonctions des librairies standards.
Et tu as tout à fait raison... J'ai failli répondre directement à
Candide, mais j'ai préféré que ça vienne de toi !
candide
> On 26 nov, 13:26, "bpascal...@googlemail.com"
> <bpascal...@googlemail.com> wrote:
>> A mon niveau, je distingue les fonctions "toutes faites" qui vont avec
>> stdio.h, string.h ... des fonctions que l'on "fabrique" avec
>> de ce que je dis mais je pense que �a explique en tant que d�butant,
>> j'ai commenc� avec les fonctions des librairies standards.
>
> Et tu as tout � fait raison...
si son but est de ne pas arriver � apprendre le C, il est effectivement
sur la bonne voie.
bpasc...@googlemail.com
> > Et tu as tout à fait raison...
>
> si son but est de ne pas arriver à apprendre le C, il est effectivement
> sur la bonne voie.
?
candide
>>> Et tu as tout � fait raison...
>> si son but est de ne pas arriver � apprendre le C, il est effectivement
>> sur la bonne voie.
>
> ?
Tu postes ici occasionnellement mais quand m�me depuis plusieurs mois si
bien que je commence � entrevoir ton profil.
J'ai l'impression que tu patauges compl�tement, que tu ne progresses pas
et qu'en fait que tu as un probl�me de cadrage ou d'encadrement, assez
typique de l'apprentissage de certains "autodidactes" comme tu te
qualifies toi-m�me. Tu n'arrives pas � hi�rarchiser l'information ie
distinguer ce qui est fondamental par rapport � ce qui est de l'ordre du
d�tail. Ton apprentissage semble incoh�rent, dispers� et sans objectif
bien d�fini.
H�las, les r�ponses donn�es par certains intervenants de ce forum, en
particulier celle de -ed-, prouvent qu'ils n'ont pas compris le
recadrage n�cessaire et je d�plore qu'ils te "d�cadrent" encore plus.
bpasc...@googlemail.com
> bpascal...@googlemail.com a écrit :
>
> >>> Et tu as tout à fait raison...
> >> si son but est de ne pas arriver à apprendre le C, il est effectivement
> >> sur la bonne voie.
>
> > ?
>
> bien que je commence à entrevoir ton profil.
>
> J'ai l'impression que tu patauges complètement, que tu ne progresses pas
> et qu'en fait que tu as un problème de cadrage ou d'encadrement, assez
> typique de l'apprentissage de certains "autodidactes" comme tu te
> distinguer ce qui est fondamental par rapport à ce qui est de l'ordre du
> détail. Ton apprentissage semble incohérent, dispersé et sans objectif
> bien défini.
>
> Hélas, les réponses données par certains intervenants de ce forum, en
> particulier celle de -ed-, prouvent qu'ils n'ont pas compris le
En bon paternaliste, je te remercie de ton analyse de bon père de
famille mais je suis majeur et vacciné.
A cet instant, j'apprends, je n'ai que ça à faire de mes journées
(mais c'est un autre sujet) alors plutôt que de rester devant la télé
ou à glander sur internet...
Cependant c'est vrai; je n'ai aucun objectif ni projet définit. Peut-
être que ça viendra sans forcer si j'attends, je risque de ne rien
apprendre. C'est un autre sujet.
Je suis très reconnaissant à ceux qui de manière pragmatique partagent
leur savoir. Si on me demande où j'ai appris à programmer dans
l'hypothèse (très mince) que je reçoive un compliment, je serais fier
de dire que j'ai appris en grande partie dans ce forum. Mais comme
autodidacte, je reterais quand même dans quelques années très prudent
avant de dire que je sais programmer.
Merci
bpasc...@googlemail.com
> >> si son but est de ne pas arriver à apprendre le C, il est effectivement
> >> sur la bonne voie.
>
> > ?
Mais je veux quand même finir par dire que je lis attentivement vos
posts et que je suis respectueux de vos contributions. Je n'hésite pas
à dire qu'à mon niveau elles participent à la qualité de ce forum.
candide
>
> Cependant c'est vrai; je n'ai aucun objectif ni projet d�finit. Peut-
> �tre que �a viendra sans forcer si j'attends, je risque de ne rien
> apprendre. C'est un autre sujet.
As-tu envie d'apprendre le C ? As-tu besoin d'apprendre le C ? Veux-tu
apprendre le C ?
Il est tr�s frustrant de rester plusieurs mois sur l'apprentissage d'un
langage et d'avancer � pas de fourmis. Qu'apr�s plusieurs mois
d'apprentissage du C tu n'aies pas d�cid� de te lancer dans
l'apprentissage des fonctions dans leur plus simple appareil et que tu
aies consid�r� qu'il �tait pr�f�rable d'utiliser des fonctions "toutes
faites" de la librairie standard me laisse assez dubitatif sur ta
progression.
As-tu essay� d'autres langages plus accessibles et moins frustrants
comme Python ou Java ainsi que je te l'ai d�j� conseill� ?
-ed-
> Hélas, les réponses données par certains intervenants de ce forum, en
> particulier celle de -ed-, prouvent qu'ils n'ont pas compris le
> recadrage nécessaire et je déplore qu'ils te "décadrent" encore plus.
Et on attend toujours tes recommandations. En vain semble-t-il ...
-ed-
>
> As-tu essayé d'autres langages plus accessibles et moins frustrants
> comme Python ou Java ainsi que je te l'ai déjà conseillé ?
Ah. Enfin une réponse sensée...
bpasc...@googlemail.com
Bonjour,
Les personnes qui ont fait java veulent que tout le monde commence à
apprendre avec java. Je ne sais pas pourquoi. Java est un langage
orienté objet. En plus d'apprendre la syntaxe, il faut apprendre les
objets qui composent le langage.
J'interviens su r ce forum de manière irrégulière, pour l'instant je
concentre mes efforts vers les algorithmes. Je me concentre vers le
langage assembleur. Je ne veux pas approfondir. Avant d'aller plus
loin dans la programmation, je veux comprendre ce qui se passe dans la
machine tant que c'est à "porter de mains".
En fait, je ne viens pas sur ce forum pour savoir ce qui serait bien
pour les intestins ou le foi. J'ai quand même du mal à imaginer que le
langage C est inutile. Je peux admettre que c'est difficilement
exploitable avec des langages haut niveau qui fournissent déjà les
outils pour programmer efficacement.
Pascal
bpasc...@googlemail.com
l'algorithme car au fil de la discussion, je comprends à peu près que
c'est récursif mais je vois en apparence une boucle.
candide
> On 28 nov, 10:26, -ed- <emmanuel.delah...@gmail.com> wrote:
>> On 27 nov, 21:50, candide <cand...@free.invalid> wrote:
>
> J'interviens su r ce forum de mani�re irr�guli�re, pour l'instant je
> concentre mes efforts vers les algorithmes.
Ah bon, tu te concentres vers les algorithmes ? Ce n'est vraiment pas
l'impression que tu me donnes. Les algorithmes, �a n'a en principe rien
� voir avec l'_apprentissage_ d'un langage de programmation et il est
m�me totalement inefficace de faire les deux simultan�ment.
> Je me concentre vers le
> langage assembleur.
Ah. Ben laisse tomber le C et fais de l'assembleur.
> Je ne veux pas approfondir. Avant d'aller plus
> loin dans la programmation, je veux comprendre ce qui se passe dans la
> machine tant que c'est � "porter de mains".
Et bien ce n'est pas le C qui va te le dire puisqu'un des int�r�ts
fondamentaux d'un langage comme le C est de pouvoir abstraire la couche
mat�rielle sp�cifique sur laquelle tu lanceras ton ex�cutable.
>
> En fait, je ne viens pas sur ce forum pour savoir ce qui serait bien
> pour les intestins ou le foi. J'ai quand m�me du mal � imaginer que le
> langage C est inutile.
inutile � quoi ? � savoir ce que fait ta machine avec ses registres ?
oui, alors il est inutile.
> Je peux admettre que c'est difficilement
> exploitable avec des langages haut niveau qui fournissent d�j� les
> outils pour programmer efficacement.
>
Ben oui mais alors lance-toi dans l'assembleur.
Samuel Devulder
> Par ailleurs, j'ai du mal � comprendre le "cheminement" de
> l'algorithme car au fil de la discussion, je comprends � peu pr�s que
> c'est r�cursif mais je vois en apparence une boucle.
Prends un papier et un crayon, surtout pas un ordi, et d�roule toi m�me
le code. Tu devrais vite comprendre pourquoi le code r�cursif produit le
m�me r�sultat qu'une boucle.
Par ailleurs pour �tudier les algorithmes, pas besoin d'un langage
particulier. Tous les langages � peu pr�s d�cents sont utilisables, m�me
et surtout un pseudo-langage qui fait abstraction des conventions
syntaxique de tel ou tel langage. Ainsi tu te concentres sur le sens
profond de l'algo et pas aux d�tails techniques parfaitement inutiles
vis a vis de l'algorithme.
Enfin tu sembles consid�rer que la boucle est une construction du
langage (en gros un for(;;) ou un while()). Mais c'est faux. Il existe
des langages qui n'ont m�me pas de telles instructions. Je pense ici aux
langages type LISP et autres CAML. Dans ces langages l� si tu veux
it�rer tu dois programmer une fonction r�cursive.
En gros ce qu'il y a � retenir ce n'est pas que le langage poss�de ou
non des instructions de type for(;;) ou pas pour qu'on puisse r�aliser
des boucles. La notion de boucle est juste le fait de vouloir ex�cuter
*plusieurs* fois un bout de code. Cela peut se faire avec
* des for(...;CONDITION;...) {BLOCK;}
* des while(CONDITION) {BLOCK;}
* des appels r�cursifs:
foo(...) {if(CONDITION) {BLOCK; foo(...);}}
* et des trucs encore plus bizarres avec pointeurs sur
fonctions et autres joyeuset�s techniques.
D'une fa�on g�n�rale cela provient du fait qu'il n'y a pas qu'une seule
fa�on de r�aliser une chose voulue. C'est ca la seule chose � retenir:
�a n'est pas parce que ton code montre en apparence un boucle qu'il y a
n�cessairement un for(;;) dedans.
sam.
candide
> Par ailleurs, j'ai du mal � comprendre le "cheminement" de
> l'algorithme car au fil de la discussion, je comprends � peu pr�s que
> c'est r�cursif mais je vois en apparence une boucle.
Ta "question" est � peine compr�hensible. Avant de te poser ce genre de
question compl�tement anecdotique pour ne pas dire insignifiante au vu
du code auquel tu te r�f�res (r�cursivit� crois�e), commence par faire
des choses basiques :
-- cr�er tes propres fonctions (ce que tu dit ne pas avoir encore fait)
-- t'informer sur la r�cursivit� en g�n�ral
-- coder ta propre fonction r�cursive "jouet" (les exemples sont l�gion
: calcul de puissances, calcul d'un produit d'entiers, parcours de
tableau, recherche de maximum dans un tableau, conversions entre bases
de num�ration, etc) et analyser son comportement ligne par ligne, et
avec un d�bogueur pour bien comprendre l'empilement des appels, c'est
encore mieux.
Mais sache que la r�cursivit� est une notion difficile, ce n'est pas
pour rien qu'on dit que "l'it�ration est humaine et la r�cursion
divine". La r�cursivit� a des actions "magiques" qu'on peut mettre pas
mal de temps � comprendre et ensuite � savoir appliquer dans des
situations un peu riches. La r�cursit� ne s'arr�te pas au codage de la
fonction factorielle.
Marc Espie
Voici quatre facons d'afficher un tableau. Avec ca, j'espere que tu
arriveras a comprendre pourquoi boucle et recursion, au final, c'est
pratiquement la meme chose...
#define TAILLE 50
#include <stdio.h>
/* les fonctions affiche1, affiche2, affiche3, affiche4 font toute la
* meme chose, a savoir afficher les elements t[i] pour a <= i < b
*/
void
affiche1(int t[], int a, int b)
{
int i;
/* boucle classique. */
for (i = a; i < b; i++)
printf("%d ", t[i]);
}
void
affiche2(int t[], int a, int b)
{
/* recursion: on affiche tout, puis le dernier element */
if (a == b)
return;
else {
affiche2(t, a, b-1);
printf("%d ", t[b-1]);
}
}
void
affiche3(int t[], int a, int b)
{
/* recursion: on affiche le premier element, puis le reste */
if (a == b)
return;
else {
printf("%d ", t[a]);
affiche3(t, a+1, b);
}
}
/* la meme que la 3, sauf qu'on peut enlever la recursion (recursion dite
* terminale, puisque l'appel a la fonction se fait a la fin)
*/
void
affiche4(int t[], int a, int b)
{
debut:
if (a == b)
return;
else {
printf("%d ", t[a]);
a++;
goto debut;
}
}
int
main()
{
int t[TAILLE];
int i;
/* juste histoire de mettre quelque chose dedans */
for (i = 0; i < TAILLE; i++)
t[i] = i;
affiche1(t, 0, TAILLE);
printf("\n");
affiche2(t, 0, TAILLE);
printf("\n");
affiche3(t, 0, TAILLE);
printf("\n");
affiche4(t, 0, TAILLE);
printf("\n");
return 0;
}
candide
> Prends un papier et un crayon, surtout pas un ordi, et d�roule toi m�me
> le code. Tu devrais vite comprendre pourquoi le code r�cursif produit le
> m�me r�sultat qu'une boucle.
>
Faut dire que l'exemple qu'il a r�cup�r� n'est pas des plus simples. En
voici un plus adapt� et plus d�monstratif :
void boucle(int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", i * i);
}
/* simule une boucle */
void f(int n)
{
if (n > 0)
{
f(n - 1);
printf("%d ", (n - 1) * (n - 1));
}
}
int main(void)
{
boucle(10);
printf("\n");
f(10);
printf("\n");
return 0;
}
et qui affiche :
0 1 4 9 16 25 36 49 64 81
0 1 4 9 16 25 36 49 64 81
candide
>
> Faut dire que l'exemple qu'il a r�cup�r� n'est pas des plus simples. En
> voici un plus adapt� et plus d�monstratif :
>
grilled by Marc Espie ;)
bpasc...@googlemail.com
> Samuel Devulder a écrit :
>
> > Prends un papier et un crayon, surtout pas un ordi, et déroule toi même
> > le code. Tu devrais vite comprendre pourquoi le code récursif produit le
> > même résultat qu'une boucle.
>
> Faut dire que l'exemple qu'il a récupéré n'est pas des plus simples. En
> voici un plus adapté et plus démonstratif :
>
> void boucle(int n)
> {
> int i;
>
> for (i = 0; i < n; i++)
> printf("%d ", i * i);
>
> }
>
> /* simule une boucle */
> void f(int n)
> {
> if (n > 0)
> {
> f(n - 1);
> printf("%d ", (n - 1) * (n - 1));
> }
>
> }
>
> int main(void)
> {
> boucle(10);
> printf("\n");
> f(10);
> printf("\n");
> return 0;
>
> }
>
> et qui affiche :
>
> 0 1 4 9 16 25 36 49 64 81
> 0 1 4 9 16 25 36 49 64 81
Bjr/sr,
Je dois admettre que je suis loin du niveau du premier post et je ne
veux pas perdre de temps avec des acrobaties intellectuelles à ne plus
finir ! Si j'ai besoin, je reviendrais réfléchir...
Pour explication ce poste ci-dessus me paraît plus abordable enfin je
dois reconnaître que pour cette partie je suis dépassé :
> /* simule une boucle */
> void f(int n)
> {
> if (n > 0)
> {
> f(n - 1);
> printf("%d ", (n - 1) * (n - 1));
> }
>
> }
Qu'est-ce qui se produit après "f(n-1)" ?La séquence "rembobine"???
càd après void f(10) ; void f(9) au second appel )à cause de f
(n-1), ...void f(8) ... où printf est inclus avant que la séquence
rembobine dans ce cas, 81 64 42 ...devrait être affichés ? Mais ce
n'est pas le cas et je ne trouve pas d'explication.
Merci,
Pascal
candide
>> void f(int n)
>> {
>> if (n > 0)
>> {
>> f(n - 1);
>> printf("%d ", (n - 1) * (n - 1));
>> }
>>
>> }
>
> Qu'est-ce qui se produit apr�s "f(n-1)" ?La s�quence "rembobine"???
Oui
> c�d apr�s void f(10) ;
Euh non, void f(10) ne veut rien dire.
Bon pour simplifier les explications, supposons que le code soit
#include <stdio.h>
void f(int n)
{
if (n > 0)
{
f(n-1)
printf("%d ", (n - 1) * (n - 1));
}
}
int main(void)
{
f(3);
printf("\n");
return 0;
}
et qui affiche :
0 1 4
Au premier appel f(3), imm�diatement f est relanc�e par l'appel f(2) qui
lui m�me est relanc� par f(1) qui � nouveau appelle f(0). C'est
l'empilement des appels. Donc pour chacun de ces appels, l'ex�cution de
la fonction f s'est arr�t� � la ligne suivante :
f(n - 1);
Maintenant, � cause de la ligne
if (n > 0)
f(0) se termine dans rien faire et c'est l� que vient le point capital :
on revient � la fonction appelante (/return to the caller/) qui �tait f
bien s�r avec le param�tre n=1. Donc le programme continue apr�s la ligne
f(n - 1);
et donc avec l'instruction
printf("%d ", (n - 1) * (n - 1));
o� n=1 ce qui affiche 0. Vu le code de f, l'ex�cution de f(1) se termine
et comme f(1) avait �t� appel� par f(2), on continue le programme l� o�
il �tait rest�, le printf est ex�cut�. Bon, et ainsi de suite jusqu'au
premier appel (n=3) et qui va afficher 4 puis se terminer. La fonction
qui avait appel�e f(3) est main() donc on revient � main, ce qui clot le
programme.
Le fait que la fonction soit r�cursive ne change en fait
fondamentalement rien � la fa�on dont les appels sont effectu�s et achev�s.
> void f(9) au second appel )� cause de f
> (n-1), ...void f(8) ... o� printf est inclus avant que la s�quence
> rembobine dans ce cas, 81 64 42 ...devrait �tre affich�s ?
Non, justement. Modifie le code en pla�ant le f(n-1) apr�s le printf()
et tu verras ce qu'il se passe.
Marc Espie
bpasc...@googlemail.com <bpasc...@googlemail.com> wrote:
>Bjr/sr,
>
>Je dois admettre que je suis loin du niveau du premier post et je ne
>finir ! Si j'ai besoin, je reviendrais r�fl�chir...
>Pour explication ce poste ci-dessus me para�t plus abordable enfin je
>dois reconna�tre que pour cette partie je suis d�pass� :
>> /* simule une boucle */
>> void f(int n)
>> {
>> � if (n > 0)
>> � � {
>> � � � f(n - 1);
>> � � � printf("%d ", (n - 1) * (n - 1));
>> � � }
>>
>> }
>
>(n-1), ...void f(8) ... o� printf est inclus avant que la s�quence
>rembobine dans ce cas, 81 64 42 ...devrait �tre affich�s ? Mais ce
>n'est pas le cas et je ne trouve pas d'explication.
Pour comprendre un programme avec une fonction recursive, il faut que
tu comprennes la notion de pile d'appels, en particulier, le fait que
plusieurs "instances" de la meme fonction peuvent etre vivantes en meme
temps. E.g., tu vas avoir un premier appel a f avec sa version de i,
qui appelle f avec un autre parametre, donc un 2e f avec un 2e i, etc.
Il n'y pas d'inclusion de printf qui tienne, c'est juste le code qui est
execute dans l'ordre:
Si tu as un debugger sous la main, pose un point d'arret au debut de f, et
fais lui afficher la pile d'appel a chaque fois que tu t'arretes.
Sinon, tu peux instrumenter un peu ton code "a la mano": fais afficher a
f ce qui se passe quand tu y entres.
Par exemple
void f(int n)
{
� if (n > 0)
� � {
� � � f(n - 1);
� � � printf("%d ", (n - 1) * (n - 1));
� � }
}
static int niveau = 0;
void entete(int k)
{
int i;
for (i = 0; i < k; i++)
printf(" ");
}
void f(int n)
{
entete(niveau++);
printf("+f(%d)\n", n);
if (n > 0) {
f(n-1);
printf("%d\n", (n-1) * (n-1));
}
entete(--niveau);
printf("-f(%d)\n", n);
}
Si tu appelles f(3), tu verras quelque chose comme:
+f(3)
+f(2)
+f(1)
+f(0)
-f(0)
1
-f(1)
4
-f(2)
9
-f(3)
Sur lequel on voit bien les niveaux d'appel de f (et surtout, le fait que
lorsque tu appelles f(0), tu as bien f(3), f(2), f(1) en attente...)
Si ton but c'est effectivement de faire de l'assembleur, va bien falloir
un jour que tu comprennes ca. Impossible de faire de l'assembleur sans
comprendre la pile !
Wykaaa
>
> Il y a plein de programmeurs C (C ou autre) qui n'ont jamais rien
> compris � la r�cursivit� donc te crois pas oblig� de passer par ce
> pensum (qui est aussi une belle tarte � la cr�me).
La "tarte � la cr�me" c'est de faire croire qu'on peut se dispenser de
comprendre la r�cursivit� quand on est programmeur. Ceci est totalement
faux.
Tout algorithme qui requiert un automate � pile est souvent beaucoup
plus facile � coder de fa�on r�cursive (exemple : la reconnaissance
syntaxique des expressions arithm�tiques).
Et puis nombre d'algorithmes sur les arbres, voire les listes, sont bien
plus faciles � programmer de fa�on r�cursive.
La r�cursivit� est un concept cl� de la programmation (et de
l'informatique et des math�matiques en g�n�ral).
Erwan David
l'�tape suivante �tant d'apprendre � se passer de la r�cursivit� qand on peut...
--
Le travail n'est pas une bonne chose. Si �a l'�tait,
les riches l'auraient accapar�
-ed-
<bpascal...@googlemail.com> wrote:
> Les personnes qui ont fait java veulent que tout le monde commence à
> apprendre avec java. Je ne sais pas pourquoi. Java est un langage
Euh, moi, j'ai commencé par le BASIC (meutrier) et le Pascal (zen)...
> orienté objet. En plus d'apprendre la syntaxe, il faut apprendre les
> objets qui composent le langage.
On peut très bien apprendre les bases de la programmation en Java sans
utiliser le paradigme objet...
Ceci-dit, de nos jours, je recommanderais plutôt un langage interprété
simple (et puissant) comme Python ou Ruby pour apprendre la
programmation ... Une fois le terrain dégagé, c'est à dire ces
principes de base acquis
- valeur
- constante
- variable
- opérateurs
- sorties simples
- structures de code (décisions, boucles)
- tableaux
- structures de données
- procédures et fonctions
- récursion
- ... j'ai du en oublier ...
on peut attaquer un langage plus complexe et subtil comme le C.
Mais vouloir commencer de rien par le C, c'est absurde. Trop de choses
complexes et subtiles à avaler d'un coup. On se tue à le répéter ...
> J'interviens sur ce forum de manière irrégulière, pour l'instant je
> concentre mes efforts vers les algorithmes.
OK, pour ça, un langage de haut niveau suffit, comme Python, par
exemple.
> Je me concentre vers le
> langage assembleur. Je ne veux pas approfondir. Avant d'aller plus
Quel intérêt de se lancer dans l'assembleur ? C'est encore plus subtil
et complexe que le C et en plus, c'est pas portable...
> loin dans la programmation, je veux comprendre ce qui se passe dans la
> machine tant que c'est à "porter de mains".
Tu ne conduis une voiture que si tu es un expert en sciences
mécanique ? Il faut savoir faire confiance dans les comportements
décrits. Ceci dit, une connaissance limitée de l'assembleur (voir la
liste "principes de base" ci-dessus) permet d'interpréter le mode pas
à pas d'un débogeur en mode machine, mais est-ce vraiment nécessaire
pour toi ?
Ce qui se passe dans la machine, c'est plutôt simple. Il faut avoir
quelques notions basiques d'architecture logique (CPU, registres,
mémoire d'exécution, mémoire de données). Les instructions machines
sont des séquences d'octets rangées à la suite dans la mémoire
d'exécution, qui comportent une partie 'code opératoire' (opcode) et
éventuellement une partie 'données'. Ces données sont soit une valeur
immédiate (constante) soit un numéro de 'registre' (mémoire locale du
CPU) soit l'adresse d'une variable (pointeur). C'est l'opcode qui
permet de savoir exactement à quoi on a affaire...
Les codes opératoires permettent d'exécuter des opérations simples
comme :
- lire une donnée
- écrire une donnée
- faire un calcul simple (+ - * /)
- faire une comparaison (= > <)
- faire un saut direct ou conditionnel
avec ça, on fait quasiment tout ce qui est nécessaire pour exécuter
n'importe quelle application.
Le code est lu octet par octet, puis interprété par le CPU (le
processeur, quoi...).
Ce qui correspond à une instruction est exécuté avec les données
passées en paramètres
Il faut en plus connaitre le mécanisme des appels de fonctions (pile,
passage de paramètres, empilage de l'adresse de retour, instruction de
fin de fonction, mais c'est relativement simple).
Ça, c'est la théorie, et elle permet de suivre un débogueur pas à pas
en mode machine relativement facilement. Maintenant, si tu veux entrer
dans les détails propres à chaque architecture physique et à chaque
mode de fonctionnement, là, ça devient complexe et subtil. Tu y tiens
vraiment ?
> En fait, je ne viens pas sur ce forum pour savoir ce qui serait bien
> pour les intestins ou le foi.
Pas compris. La foi ? Le foie ? (oui, le français est aussi une langue
complexe et subtile !)
Et quel rapport avec la programmation ?
>J'ai quand même du mal à imaginer que le
> langage C est inutile.
Personne n'a dit qu'il était inutile. Par contre, ce n'est pas du tout
un langage d'initiation à la programmation. Encore une fois, trop de
détails spécifiques à ce langage parasitent le message (relire la
liste "principes de base" ci-dessus).
> Je peux admettre que c'est difficilement
"c'est" ? Que signifie ici, pour toi, le " c' " ?
> exploitable avec des langages haut niveau qui fournissent déjà les
> outils pour programmer efficacement.
Langue de bois détectée (rien compris en fait ...)
Marc Espie
candide <can...@free.invalid> wrote:
>Il y a plein de programmeurs C (C ou autre) qui n'ont jamais rien
>compris � la r�cursivit� donc te crois pas oblig� de passer par ce
>pensum (qui est aussi une belle tarte � la cr�me).
Si c'est pour donner des conseils aussi mauvais, tu peux aussi fermer
ta gueule.
Le cote "chercher la petite bete dans la norme", ca tu sais faire.
Le cote "expliquer la programmation aux gens", par contre c'est moins
au point...
Meme s'il y a des gens qui se pretendent programmeurs qui sont nuls, ca
n'est pas une raison pour inciter les nouveaux a faire pareil...
-ed-
Voici une bonne définition de ce qu'est la récursion :
Récursion : voir récursion.
Si tu as compris ça, tu as tout compris, notamment l'aspect répétitif
de la chose...
La question suivante devrait être "mais alors comment on sort de la
boucle ?"
Marc Espie
-ed- <emmanuel...@gmail.com> wrote:
>On 28 nov, 12:54, "bpascal...@googlemail.com"
><bpascal...@googlemail.com> wrote:
>> l'algorithme �car au fil de la discussion, je comprends � peu pr�s que
>> c'est r�cursif mais je vois en apparence une boucle.
>Voici une bonne d�finition de ce qu'est la r�cursion :
>R�cursion : voir r�cursion.
>Si tu as compris �a, tu as tout compris, notamment l'aspect r�p�titif
>de la chose...
>La question suivante devrait �tre "mais alors comment on sort de la
>boucle ?"
Personnellement, je pense toujours qu'on est deforme par des annees
d'apprentissages de la programmation structuree: il n'y a rien de
naturel dans une construction telle que
i = i + 1;
mais bon, des annees d'explications de comment ca marche, des petites
cases memoire, et tout ca, conduisent a une vision etriquee de l'informatique
et du fonctionnement des machines.
Le point de vue du MIT, de commencer par du scheme (avec _the structure and
interpretation of computer programs_) se tient parfaitement.
De toutes facons, si on veut faire des choses serieuses, tot ou tard, va
falloir s'assurer que ce qu'on fait fonctionne...
Et entre devoir ecrire explicitement mes invariants de boucle et mes
conditions d'arret, ou avoir du recursif qui se prouve "naturellement" avec
une belle equation, le recursif c'est souvent plus simple.
Juste un petit bout de point de vue.
Les variables du procedural, les boucles qui vont avec, c'est une vision
tres proche de la machine. Ca revient a prendre la route le nez dans le
guidon.
Oublier un peu tout ca, faire du fonctionnel propre, avec de la recursion,
c'est souvent une bonne facon de s'elargir les horizons.
Allez, une petite fonction recursive pour la route.
unsigned int
pgcd(unsigned int a, unsigned int b)
{
if (a < b)
return pgcd(b, a);
else if (b == 0)
return a;
else
return pgcd(b, a % b);
}
Wykaaa
La situation a chang� en 30 ans !
Les compilateurs actuels savent beaucoup mieux g�rer la r�cursion qu'au
Moyen-Age :-)
Beaucoup transforment la r�cursion terminale en it�ration (le "pattern"
d'optimisation n'est pas tr�s compliqu�).
Toute fonction r�cursive peut �tre d�r�cursiv�e (pour les fonctions
ih�remment r�cursives, en passant par une pile LIFO) mais � quel prix ?
J'ai pris l'exemple de l'analyseur syntaxique des expressions
arithm�tiques parce que c'est un langage "context-free" reconnaissable
par un automate � pile et donnant lieu � un algorithme LL(k) ou LR(k)
(look-ahead left ou right, k �tant la profondeur du look-ahead)
, voire LALR (Look-Ahead Left Recursive employ� dans Yacc et Gnu Bison)
Ecris donc cela "� la main" sans r�cursion (je veux dire la
reconnaissance des expressions arithm�tiques (pas le petit cas d'�cole
bateau mais, par exemple, la reconnaissance des expressions en C) et on
se revoit apr�s (je l'ai fait, il y a longtemps en analyse LR(k) et j'ai
calcul� la fermeture transitive � la main, c'est vraiment du sport alors
que c'est si simple en r�cursif...).
Marc Espie
>La situation a chang� en 30 ans !
>Les compilateurs actuels savent beaucoup mieux g�rer la r�cursion qu'au
>Moyen-Age :-)
>Beaucoup transforment la r�cursion terminale en it�ration (le "pattern"
>d'optimisation n'est pas tr�s compliqu�).
Heureusement, c'est quand meme une techno qui date des annees 60 !
La seule raison pour laquelle ca a mis du temps a etre utilise dans les
compilo C, c'est qu'il etait peu frequent pour les programmeurs C de
faire de la recursion, et qu'ils avaient tendance a optimiser manuellement
la recursion terminale en goto le debut de la fonction....
>Toute fonction r�cursive peut �tre d�r�cursiv�e (pour les fonctions
>ih�remment r�cursives, en passant par une pile LIFO) mais � quel prix ?
>J'ai pris l'exemple de l'analyseur syntaxique des expressions
>arithm�tiques parce que c'est un langage "context-free" reconnaissable
>par un automate � pile et donnant lieu � un algorithme LL(k) ou LR(k)
>(look-ahead left ou right, k �tant la profondeur du look-ahead)
>, voire LALR (Look-Ahead Left Recursive employ� dans Yacc et Gnu Bison)
Le seul cas d'ecole ou ca vaut le coup de faire gaffe, c'est quicksort,
ou il faut compter les elements de chaque "moitie", histoire de s'assurer
que la recursion terminale s'applique bien sur le bon morceau, sinon, ca
peut degenerer en pile de taille lineaire et pas logarithmique.
Mais je ne t'apprend rien...
Benoit Izac
le 29/11/2009 à 11:07, -ed- <emmanuel...@gmail.com> a écrit dans
le message
<d99cd762-ed06-4f79...@e27g2000yqd.googlegroups.com> :
>> loin dans la programmation, je veux comprendre ce qui se passe dans la
>> machine tant que c'est à "porter de mains".
>
> Tu ne conduis une voiture que si tu es un expert en sciences
> mécanique ?
L'analogie est mauvaise. La programmation, c'est plutôt la fabrication
de la voiture, l'utilisation du programme étant la conduite.
Je veux fabriquer une voiture. Dans tous les cas il me faut des plans
(algorithmes) et c'est indépendant du choix que je vais faire pour sa
fabrication (langage de programmation). Ensuite, j'ai le choix :
- je veux construire moi-même toutes les pièces (assembleurs)
- je veux acheter toutes les matières premières et réaliser tous les
usinages, par contre j'utilise des vis du commerce (C)
- je veux acheter des composants existants dans le commerce comme le
moteur, la carrosserie et ne réaliser que l'assemblage (Python,
Perl, etc.)
Ça reste une analogie, la réalité est un peu plus complexe quand au
choix du langage.
Ceci dit, pour quelqu'un qui n'est pas informaticien (comme moi) et
qui ne pratique pas la programmation de manière régulière, il ne faut
pas s'attendre à pouvoir programmer en C correctement avant plusieurs
années (pratiquement dix ans dans mon cas mais je suis une
feignasse ;-) ).
Je pense qu'on apprends un langage de programmation comme une langue
étrangère : au début, on comprends rien et c'est bien normal. Il ne faut
surtout pas s'attarder sur tous les petits détails sinon on n'apprend
rien. Avec le temps, on commence à comprendre le sens des phrases même
si on ne comprend pas chaque mot. Avec la pratique, on acquière des
automatismes qui permettent de ne plus réfléchir à certaines choses et
donc de pouvoir se concentrer sur d'autre dont on ignorait l'existence.
Pour une personne qui apprend seule, parler couramment, avoir l'accent
et pouvoir faire du littéraire, c'est beaucoup, beaucoup de travail (je
veux pas décourager mais je pense même que c'est quasiment impossible).
Si l'on veux vraiment avoir une maîtrise du langage, la seule solution
c'est d'aller dans un pays où les gens parlent cette langue (milieu
professionnel ou participer au développement d'une application réelle).
Mes deux cents.
--
Benoit Izac
Erwan David
> Erwan David a �crit :
>> Wykaaa <wyk...@yahoo.fr> �crivait :
>>
>>> candide a �crit :
>>>
>>>> Il y a plein de programmeurs C (C ou autre) qui n'ont jamais rien
>>>> compris � la r�cursivit� donc te crois pas oblig� de passer par ce
>>>> pensum (qui est aussi une belle tarte � la cr�me).
>>> La "tarte � la cr�me" c'est de faire croire qu'on peut se dispenser de
>>> comprendre la r�cursivit� quand on est programmeur. Ceci est
>>> totalement faux.
>>> Tout algorithme qui requiert un automate � pile est souvent beaucoup
>>> plus facile � coder de fa�on r�cursive (exemple : la reconnaissance
>>> syntaxique des expressions arithm�tiques).
>>> Et puis nombre d'algorithmes sur les arbres, voire les listes, sont
>>> bien plus faciles � programmer de fa�on r�cursive.
>>>
>>> La r�cursivit� est un concept cl� de la programmation (et de
>>> l'informatique et des math�matiques en g�n�ral).
>>
>> l'�tape suivante �tant d'apprendre � se passer de la r�cursivit� qand on peut...
>>
> Je ne vois pas pourquoi.
> La situation a chang� en 30 ans !
�a c'est mon historique de d�veloppeur embarqu� qui parle...
Marc Espie
Erwan David <er...@rail.eu.org> wrote:
>�a c'est mon historique de d�veloppeur embarqu� qui parle...
Ca veut juste dire que tu optimises la recursion terminale a la main
en presence de compilateurs deficients...
candide
> In article <4b0e4cc7$0$9187$426a...@news.free.fr>,
> candide <can...@free.invalid> wrote:
>> Il y a plein de programmeurs C (C ou autre) qui n'ont jamais rien
>> compris � la r�cursivit� donc te crois pas oblig� de passer par ce
>> pensum (qui est aussi une belle tarte � la cr�me).
>
> Si c'est pour donner des conseils aussi mauvais, tu peux aussi fermer
> ta gueule.
Visiblement, �a ne te fait pas plaisir que je te dise la r�alit� mais,
oui, un grand nombre de programmeurs n'ont pas compris la r�cursivit�.
Comprendre la r�cursivit�, ce n'est pas avoir compris la tarte � la
cr�me de la factorielle.
Une fois de plus, si on dit que l'it�ration est humaine et la r�cursion
divine, ce n'est pas pour rien : il y a vraiment une difficult� �
_vraiment_ comprendre la r�cursivit�.
>
> Le cote "chercher la petite bete dans la norme", ca tu sais faire.
>
> Le cote "expliquer la programmation aux gens", par contre c'est moins
> au point...
Je n'en suis pas si s�r justement. Question d'empathie.
>
> Meme s'il y a des gens qui se pretendent programmeurs qui sont nuls, ca
> n'est pas une raison pour inciter les nouveaux a faire pareil...
On n'est pas un programmeur nul si on ne maitrise pas la r�cursivit�.
Marc Espie
candide <can...@free.invalid> wrote:
>Marc Espie a �crit :
>> Meme s'il y a des gens qui se pretendent programmeurs qui sont nuls, ca
>> n'est pas une raison pour inciter les nouveaux a faire pareil...
>On n'est pas un programmeur nul si on ne maitrise pas la r�cursivit�.
Ben si.
Ou plus precisement, si on ne maitrise pas la recursivite, on est loin
d'avoir fini d'apprendre.
Ca fait partie des connaissances de base que tout programmeur raisonnablement
serieux doit connaitre. Je te l'accorde, il y a plein de guignols qui se
pretendent "programmeurs" et qui n'y ont rien compris. Ca ne change rien
au fait que c'est la honte du metier.
candide
> In article <d27e61cf-0ad2-410c...@j24g2000yqa.googlegroups.com>,
> d'apprentissages de la programmation structuree: il n'y a rien de
> naturel dans une construction telle que
> i = i + 1;
absolument mais ta "programmation structur�e" (je sais pas trop ce que
�a recouvre � vrai dire, c'est un truc que je lis de temps en temps) n'a
rien � voir l� dedans. Pose la question � un, deux, dix d�butants (mais
en vois-tu dans ton �cole ?) qui _d�couvre_ une expression comme i=i+1
et tu auras la r�ponse.
> mais bon, des annees d'explications de comment ca marche, des petites
> cases memoire, et tout ca, conduisent a une vision etriquee de l'informatique
> et du fonctionnement des machines.
Quand on programme, y compris en C, a-t-on n�cessairement besoin de
conna�tre le fonctionnement des machines. Les variables sont des
abstractions.
> Et entre devoir ecrire explicitement mes invariants de boucle et mes
> conditions d'arret, ou avoir du recursif qui se prouve "naturellement" avec
> une belle equation, le recursif c'est souvent plus simple.
Exemple ?
>
> Juste un petit bout de point de vue.
>
> Les variables du procedural, les boucles qui vont avec, c'est une vision
> tres proche de la machine.
Non, c'est juste chez toi de la d�formation professionnelle.
> Oublier un peu tout ca, faire du fonctionnel propre, avec de la recursion,
> c'est souvent une bonne facon de s'elargir les horizons.
Ah ben oui mais faut savoir ce qu'on veut : apprendre � programmer en C
ou se faire un culture G pour discuter devant la machine � caf� ;)
>
> Allez, une petite fonction recursive pour la route.
>
> unsigned int
> pgcd(unsigned int a, unsigned int b)
> {
> if (a < b)
> return pgcd(b, a);
> else if (b == 0)
> return a;
> else
> return pgcd(b, a % b);
> }
"Peut mieux faire", j'ai envie de dire car un d�tail dans l'algorithme
d'Euclide t'a �chapp� : ta premi�re ligne ne sert � rien car si a<b
alors, dans ton appel r�cursif pgcd(b, a%b), le deuxi�me argument sera
a. Et cette cascade de trois return, c'est pas tr�s C.
Le code plus ou moins standard du pgcd r�cursif est :
int pgcd(int a, int b)
{
return b ? pgcd(b, a % b) : a ;
}
Marc Espie
candide <can...@free.invalid> wrote:
>absolument mais ta "programmation structur�e" (je sais pas trop ce que
>�a recouvre � vrai dire, c'est un truc que je lis de temps en temps) n'a
>rien � voir l� dedans. Pose la question � un, deux, dix d�butants (mais
>en vois-tu dans ton �cole ?) qui _d�couvre_ une expression comme i=i+1
>et tu auras la r�ponse.
Je n'en ai pas vu depuis pas mal d'annees, tout betement parce qu'ils sont
trop ages. Mais j'ai des souvenirs de club d'info d'il y a pas mal d'annees,
avec des collegiens, ou c'etait pas du tout naturel pour eux au depart.
>> mais bon, des annees d'explications de comment ca marche, des petites
>> cases memoire, et tout ca, conduisent a une vision etriquee de l'informatique
>> et du fonctionnement des machines.
>
>Quand on programme, y compris en C, a-t-on n�cessairement besoin de
>conna�tre le fonctionnement des machines. Les variables sont des
>abstractions.
... mais i=i+1, c'est deja un biais important sur le fonctionnement des
machines. Et on peut programmer sans variables modifiables !
>> Et entre devoir ecrire explicitement mes invariants de boucle et mes
>> conditions d'arret, ou avoir du recursif qui se prouve "naturellement" avec
>> une belle equation, le recursif c'est souvent plus simple.
>Exemple ?
Tu m'emmerdes. Va chercher dans la biblio. J'emploie des termes precis. Tu
peux trouver autant d'exemples que tu veux dans toute la litterature qui
traite de semantique et de preuves de programmes.
>> Les variables du procedural, les boucles qui vont avec, c'est une vision
>> tres proche de la machine.
>Non, c'est juste chez toi de la d�formation professionnelle.
... Et des oeilleres persistantes chez toi. C'est pas parce que tu ne
connais QUE C ou assimile qu'il n'existe que ca. C'est pas parce que 90%
des gens programment en procedural pur qu'il n'y a pas autre chose dans
la nature.
>> Oublier un peu tout ca, faire du fonctionnel propre, avec de la recursion,
>> c'est souvent une bonne facon de s'elargir les horizons.
>Ah ben oui mais faut savoir ce qu'on veut : apprendre � programmer en C
>ou se faire un culture G pour discuter devant la machine � caf� ;)
"Apprendre a programmer en C", ca implique entre autres "d'apprendre a
programmer", ce qui veut dire connaitre toutes les techniques utiles, et ca
inclut la recursion !
>> unsigned int
>> pgcd(unsigned int a, unsigned int b)
>> {
>> if (a < b)
>> return pgcd(b, a);
>> else if (b == 0)
>> return a;
>> else
>> return pgcd(b, a % b);
>> }
>
>"Peut mieux faire", j'ai envie de dire car un d�tail dans l'algorithme
>d'Euclide t'a �chapp� : ta premi�re ligne ne sert � rien car si a<b
>alors, dans ton appel r�cursif pgcd(b, a%b), le deuxi�me argument sera
>a. Et cette cascade de trois return, c'est pas tr�s C.
M'a echappe ? mais va te faire foutre ! C'est pas parce que tu veux
ecrire les choses autrement en te focalisant sur un detail que ma version
est incorrecte.
Cascade de 3 return, pas tres C ? Euh, la-encore, enleve tes oeilleres.
C'est parfaitement valide, et extremement classique.
>Le code plus ou moins standard du pgcd r�cursif est :
"plus ou moins". c'est juste une autre facon d'ecrire la meme chose.
Tu l'as recopie de quelque part, pour dire que c'est standard ? ou tu arrives
encore a inventer trois lignes de code sans les repiquer ailleurs ?
>int pgcd(int a, int b)
>{
> return b ? pgcd(b, a % b) : a ;
>}
La j'avoue, la coupe est pleine. J'en ai plus que marre de tes frasques.
A force de jouer au "candide" qui reprend tout et tout le monde en jouant
ta mouche du coche, et en voulant imposer aux gens ta vision etriquee du
monde, tu as finalement reussi a m'enerver un peu.
M'en fous, a troll, troll-et-demi. J'ai la peau plus solide que toi. Si tu
cherches la bagarre...
Richard Delorme
> Une fois de plus, si on dit que l'it�ration est humaine et la r�cursion
> divine, ce n'est pas pour rien : il y a vraiment une difficult� �
> _vraiment_ comprendre la r�cursivit�.
On apprend plus les suites en Math�matiques � l'�cole ?
Suites arithm�tiques :
a_(0)
a_(n+1) = a_(n) + r
Suites g�om�triques :
q_(0)
q_(n+1) = q_(n) * r
etc.
Si l'on a compris �a, on a compris la r�cursivit�.
--
Richard
candide
> La "tarte � la cr�me" c'est de faire croire qu'on peut se dispenser de
> comprendre la r�cursivit� quand on est programmeur. Ceci est totalement
> faux.
Non, au contraire, le "informatiquement correct" c'est de parler tout le
temps de r�cursivit�, fonction r�cursive par-ci, fonction r�cursive par
l�. �a me fait penser � des discussions sur le forum du site du z�ro o�
des intervenants te sortent "et ben t'as le coder en r�cursif" comme si
la r�cursivit� �tait un algorithme ...
> Tout algorithme qui requiert un automate � pile est souvent beaucoup
> plus facile � coder de fa�on r�cursive (exemple : la reconnaissance
> syntaxique des expressions arithm�tiques).
ben je vais poser la question � un vrai programmeur C, Emmanuel Delahaye
: dis-nous, tu avais dit que tu avais programm� dans ta biblioth�que
perso un automate � piles si je ne m'abuse. L'as tu cod� en r�cursif ?
> Et puis nombre d'algorithmes sur les arbres, voire les listes, sont bien
> plus faciles � programmer de fa�on r�cursive.
�a d'abord, c'est une tarte � la cr�me. Quelques algorithmes sur les
graphes (dont les arbres) sont cod�s r�cursivement. La cas typique est
le parcours en profondeur (DFS). Mais il est courant qu'il n'y ait
aucune impl�mentation r�cursive adapt�e (le BFS est typique). Encore
r�cemment, j'ai cod� le codage de Prufer d'un arbre ; rien de r�cursif
pourtant c'est un arbre. Et m�me pour le parcours en profondeur, il
n'est pas dit que l'algo r�cursif soit adapt�. J'avais r�cemment � coder
en Python un probl�me de parcours de labyrinthe, j'ai donc opt� pour un
DFS : et bien j'ai eu une "maximum recursion depth error". Chose qui
pourrait arriver aussi en C, parce que si ton graphe est tr�s profond,
tu vas empiler les appels et si la r�cursion n'est pas terminale ce qui
est courant, t'exploseras ta pile.
>
> La r�cursivit� est un concept cl� de la programmation (et de
> l'informatique et des math�matiques en g�n�ral).
Pour le concept-clef, je veux bien mais souvent �a reste au stade du
concept, quand il s'agit d'impl�menter, il y a plus grand monde (sauf
pour une r�cursivit� de type factorielle qui est compl�tement factice).
On n'a pas toujours besoin de tout verbaliser ni de tout
intellectualiser, tu crois que le singe a pris des cours de r�cursivit�
pour monter dans son arbre ? ;)
Erwan David
oui, parceque des compilateurs efficaces en dehors des cas simples sont
rares dans ce domaine.
Wykaaa
Bin si, justement. Tiens, �crit un �diteur de lien sans utiliser la
r�cursion, juste pour voir...
Wykaaa
Wykaaa a �crit (en plus tu cotes comme un goret) :
>> La r�cursivit� est un concept cl� de la programmation (et de
>> l'informatique et des math�matiques en g�n�ral).
>
>
> Pour le concept-clef, je veux bien mais souvent �a reste au stade du
> concept, quand il s'agit d'impl�menter, il y a plus grand monde (sauf
> pour une r�cursivit� de type factorielle qui est compl�tement factice).
> On n'a pas toujours besoin de tout verbaliser ni de tout
> intellectualiser, tu crois que le singe a pris des cours de r�cursivit�
> pour monter dans son arbre ? ;)
>
>
Je te donne un autre exemple encore :
Ecris un �valuateur de lambda-expressions de fa�on non r�cursive...
Il y a quantit� d'algorithme qu'il est EXTREMEMENT plus simple d'�crire
en r�cursif, m�me et surtout si on �limine les algos sur les arbres, les
listes, etc. qui pourtant, ne sont pas que des exercices de style
puisqu'ils sont utilis�s dans les optimiseurs des compilateurs, les
syst�mes d'exploitation, etc.
En disant aux d�butants qu'ils n'ont pas besoin de conna�tre la
r�cursivit� pour programmer, tu les trompes en faisant d'eux des singes
"pousseurs de caract�res".
candide
> Tu m'emmerdes. Va chercher dans la biblio. J'emploie des termes precis. Tu
> peux trouver autant d'exemples que tu veux dans toute la litterature qui
> traite de semantique et de preuves de programmes.
>
"trait� de s�mantique", "preuves de programmes" connais rien � �a, je
suis pas du s�rail mais je sais que mes �tudiants de L3 font �a (et m�me
avec du Coq je crois).
>
> ... Et des oeilleres persistantes chez toi. C'est pas parce que tu ne
> connais QUE C ou assimile qu'il n'existe que ca. C'est pas parce que 90%
> des gens programment en procedural pur qu'il n'y a pas autre chose dans
> la nature.
>
On est d'accord sur ce point.
>> Ah ben oui mais faut savoir ce qu'on veut : apprendre � programmer en C
>> ou se faire un culture G pour discuter devant la machine � caf� ;)
>
> "Apprendre a programmer en C", ca implique entre autres "d'apprendre a
> programmer", ce qui veut dire connaitre toutes les techniques utiles, et ca
> inclut la recursion !
Je dis pas le contraire, je fais des TP de C en premi�re ann�e et le
dernier TP est sur la r�cursivit�.
>
> M'a echappe ? mais va te faire foutre ! C'est pas parce que tu veux
> ecrire les choses autrement en te focalisant sur un detail que ma version
> est incorrecte.
>
> Cascade de 3 return, pas tres C ? Euh, la-encore, enleve tes oeilleres.
> C'est parfaitement valide, et extremement classique.
J'ai pas dit que c'�tait pas valide mais il est par exemple plus courant
pour un pratiquant du C d'�crire
int max(int a, int b)
{
return a > b ? a : b;
}
plutot que
int max(int a, int b)
{
if (a > b)
return a;
else
return b;
}
>
>
>> Le code plus ou moins standard du pgcd r�cursif est :
> "plus ou moins". c'est juste une autre facon d'ecrire la meme chose.
> Tu l'as recopie de quelque part, pour dire que c'est standard ? ou tu arrives
> encore a inventer trois lignes de code sans les repiquer ailleurs ?
Je ne l'ai pas invent� car c'est classique (cf. le code de Wikipedia �
"Algorithme d'Euclide"). C'est pas vous les informaticiens qui �tes tout
le temps en train de dire qu'il faut pas r�inventer la roue ? Et puis le
coup de ne pas distinguer le cas o� a et b ne sont pas dans l'ordre
naturel, je dois reconnaitre que je n'y avais pas pens� la premi�re fois
(et donc j'avais �crit comme toi).
>
> La j'avoue, la coupe est pleine.
>
Et bien ta coupe n'est pas tr�s profonde ...
candide
>
> Bin si, justement. Tiens, �crit un �diteur de lien sans utiliser la
> r�cursion, juste pour voir...
Et tu crois que tout programmeur C a le background pour �crire un
�diteur de liens ? Le programmeur qui �crit un compilateur ou des outils
de ce genre n'est pas le programmeur lambda.
Mais je veux bien examiner un code-source d'�diteur de liens, histoire
de voir si justement la r�cursivit� est aussi utilis�e que tu le dis.
T'as un lien vers les sources de ld ou un truc du genre ?
candide
> Je te donne un autre exemple encore :
> Ecris un �valuateur de lambda-expressions de fa�on non r�cursive...
>
> Il y a quantit� d'algorithme qu'il est EXTREMEMENT plus simple d'�crire
> en r�cursif, m�me et surtout si on �limine les algos sur les arbres, les
> listes, etc. qui pourtant, ne sont pas que des exercices de style
> puisqu'ils sont utilis�s dans les optimiseurs des compilateurs, les
> syst�mes d'exploitation, etc.
Mais je ne dis pas que la r�cursivit� soit un concept inutile. Remettons
le fil dans son contexte. pascal (le PO) essaye de d�chiffrer un code
r�cursif tordu alors qu'il a bien d'autres choses plus �l�mentaires �
r�gler. Le PO, tu sais il est tr�s tr�s loin des lambda-expression, d�j�
s'il savait �crire de lui-m�me une fonction de son cr�, il aurait avanc�.
Benoit Izac
le 29/11/2009 à 15:42, candide <can...@free.invalid> a écrit dans le
message <4b128857$0$11205$426a...@news.free.fr> :
> Et tu crois que tout programmeur C a le background pour écrire un
> éditeur de liens ? Le programmeur qui écrit un compilateur ou des outils
> de ce genre n'est pas le programmeur lambda.
>
> Mais je veux bien examiner un code-source d'éditeur de liens, histoire
> de voir si justement la récursivité est aussi utilisée que tu le dis.
> T'as un lien vers les sources de ld ou un truc du genre ?
<http://sourceware.org/cgi-bin/cvsweb.cgi/src/ld/?cvsroot=src>
<http://www.openbsd.org/cgi-bin/cvsweb/src/gnu/usr.bin/ld/>
Bon courage. ;-)
--
Benoit Izac
candide
> Suites arithm�tiques :
> a_(0)
> a_(n+1) = a_(n) + r
>
> Suites g�om�triques :
> q_(0)
> q_(n+1) = q_(n) * r
>
> etc.
>
> Si l'on a compris �a, on a compris la r�cursivit�.
>
Ce que tu nous donnes l�, c'est une variation sur la sempiternelle
version de la factorielle : ta premi�re fonction revient � calculer un
produit r�cursivement et la seconde une puissance r�cursivement, ce qui
au demeurant ne me parait pas naturel. Il me semble de plus naturel de
dire � un coll�gien que 12**42 c'est le produit de 12 quarante deux
fois par lui-m�me que de lui dire qu'une formule comme 12**truc c'est
12**(truc-1)*12 si truc !=0 et que 12**0 vaut 1.
Par ailleurs, je crois que les lyc�ens voient �a mais c'est surtout
l'occasion de leur parler de raisonnement par r�currence.
Maintenant, je pense que tu as plein de gens qui ont compris la version
r�cursive de la factorielle et qui seront incapables de te coder (en C)
r�cursivement toutes les fa�ons de combiner par exemple trois objets,
par exemple si les objets sont
entree, plat, dessert
�a doit g�n�rer
entre
plat
dessert
entree plat
entree dessert
plat dessert
entree plat dessert
Ce que je peux te dire, c'est qu'une majorit� d'�tudiants va savoir
coder assez facilemnt une puissance en r�cursif mais tr�s tr�s peu
sauront �crire le code r�cursif de g�n�ration des combinaisons ou
quelque chose du genre.
Je peux m�me te donner un exemple concret : l'ann�e derni�re en contr�le
de TP, on a demand� de coder en r�cursif le calcul de la longueur d'une
cha�ne. Pas compliqu� Et pourtant, voici un exemple de code qu'une
�tudiante (en maths) s�rieuse a donn� :
#include <stdio.h>
int f(char *phrase)
{
int i;
int cpt;
if(phrase[i]='\0')cpt=0;
/*on decale de une lettre a chaque appel c'est � dire que
par exemple on compte la premi�re lettre puis le nombre de lettre
de la phrase sans compter la premi�re. dans notre cas
on compte 1 (pour le j) + le nombre de lettre de
"e hais le C"(sans le j) et ainsi de suite jusqu'a ce
qu'on tombe sur le caract�re nul.donc on doit prendre en compte
la phrase qui commence par le caract�re de la case d'indice 1,puis 2 ...*/
else cpt=1+f(?);
return cpt;
}
int main(void)
{
char phrase[]="je hais le C";
int compteur=f(phrase);
printf("le nombre de caract�re est de :%d",compteur);
return 0;
}
Voici un autre exemple d'un �tudiant pourtant s�rieux et assidu :
#include <stdio.h>
int f(char *chaine)
{
int res;
while (chaine != '\0')
{
res=1+f(chaine-1);
}
return res;
}
int main(void)
{
char s[]="je hais la C!";
printf ("il y a %d caract�res.\n",f(s));
return 0;
}
Donc, le concept de r�cursivit� il est assez facile � comprendre mais il
faut aller au-del� du concept, "In code we trust!" comme on dit. Et on
se rend compte que cela peut poser certaines difficult�s
d'impl�mentation (en C par exemple mais je suppose que �a doit �tre vrai
dans d'autres langages) si on veut �tre un minimum efficace, il n'est
pas toujours facile de voir comment faire pour que chaque appel n'alloue
pas les donn�es et qu'au contraire, ils utilisent une sorte de pool
commun. Si en g�n�ral, on suit l'algorithme math�matique de trop pr�s,
en g�n�ral, on obtient des impl�mentations non efficaces.
Samuel Devulder
Un truc a savoir, c'est que si l'optimiseur vire une r�cursivit�, ton
prog devient nettement moins d�buggable par perte du contexte courant
("stack frame"). En th�orie on s'en fiche, mais � l'usage c'est chiant
et il vaut mieux que le compilo garde la structure asm assez proche du
code d'origine.
Je te raconte pas les surprise qu'on trouve en d�buggant un code
optimis� par un compilo qui en fait trop. Par exemple au niveau
couverture du code on se retrouve � passer par les deux branches d'un
if() simultan�ment et crois moi c'est pas bon du tout pour certains
crit�res de couverture du code (mc/dc etc). En plus quand le code ASM ne
trace plus les lignes du code C dans le m�me ordre o� elle sont �crite
rend le truc in-tra�able. En th�orie on s'en fiche d'avoir un code non
tracable s'il est bon.. mais voila le moindre code, meme hyper simple,
est souvent bugg� (cf les pbs d'overflow en arithmetique) et on est
content d'avoir un code ASM assez proche du code C.
Dernier point: en embarque la vitesse n'est pas le probl�me. Les mhz
sont souvent l� plus que n�c�ssaire (80Mhz pour traiter des trucs qui
arrivent � une freq de 5khz ca le fait les doigts dans le nez), mais ce
qui coince c'est la ROM et la RAM. Elles sont toutes petites en
embarqu�, et on pr�f�re de loin, mais vraiment de loin, optimiser en
taille (rom/ram) qu'en vitesse.
sam.
Wykaaa
[snip]
>
> Donc, le concept de r�cursivit� il est assez facile � comprendre mais il
> faut aller au-del� du concept, "In code we trust!" comme on dit. Et on
> se rend compte que cela peut poser certaines difficult�s
> d'impl�mentation (en C par exemple mais je suppose que �a doit �tre vrai
> dans d'autres langages) si on veut �tre un minimum efficace, il n'est
> pas toujours facile de voir comment faire pour que chaque appel n'alloue
> pas les donn�es et qu'au contraire, ils utilisent une sorte de pool
> commun. Si en g�n�ral, on suit l'algorithme math�matique de trop pr�s,
> en g�n�ral, on obtient des impl�mentations non efficaces.
C'est quoi un "pool commun" ?
Des variables globales ? statiques ?
Quand on utilise la r�cursivit�, on va �viter les variables justement
(on n'utilisera que des param�tres). On ne va faire que des appels de
fonctions (r�cursivement). C'est �videmment possible en C.
La programmation fonctionnelle, tu connais ?
Les langages sans affectation, tu connais ?
Les langages � assignation unique, tu connais ?
L'�valuation paresseuse, tu connais ?
Fonction d'Ackermann en Haskell :
ackermann 0 n = (n + 1)
ackermann m 0 = ackermann (m-1) 1
ackermann m n = ackermann (m-1) (ackermann m (n-1))
Justement, le mieux c'est de suivre, au plus pr�s, la d�finition
math�matique.
candide
> C'est quoi un "pool commun" ?
> Des variables globales ? statiques ?
En pratique c'est souvent le cas mais on peut aussi passer en param�tre
un pointeur vers ce qui va �tre le pool.
>
> Quand on utilise la r�cursivit�, on va �viter les variables justement
> (on n'utilisera que des param�tres).
Regarde un impl�mentation correcte de qsort() par un quicksort et tu
verras qu'il n'y a pas que des param�tres. J'ai celle de Plauger sous
les yeux (c'est pas vraiment un mauvais programmeur!) et il d�finit un
paquet de variables. Au final, c'est pas tr�s g�nant vu que la
complexit� est en n*ln(n) donc on limite la casse.
On peut bien s�r �viter les variables mais alors on introduit des
param�tres factices, qui ne servent qu'au fonctionnement interne de la
fonction, bref on m�lange interface et impl�mentation, le truc que je
d�teste.
> On ne va faire que des appels de
> fonctions (r�cursivement). C'est �videmment possible en C.
Oui, tu enfonces des portes ouvertes.
>
> La programmation fonctionnelle, tu connais ?
Plusieurs de mes coll�gues ont tent� de m'y convertir (enfin � Caml)
mais en vain.
> Les langages sans affectation, tu connais ?
Non
> Les langages � assignation unique, tu connais ?
Non
> L'�valuation paresseuse, tu connais ?
Lazy evaluation ? j'ai vu le nom dans des docs Python mais je ne sais
pas ce que c'est.
>
> Fonction d'Ackermann en Haskell :
> ackermann 0 n = (n + 1)
> ackermann m 0 = ackermann (m-1) 1
> ackermann m n = ackermann (m-1) (ackermann m (n-1))
>
> Justement, le mieux c'est de suivre, au plus pr�s, la d�finition
> math�matique.
Certainement pas. Exemple classique :
int f(int n)
{
return n <= 1 ? 1 : f(n - 1) + f(n - 2);
}
ce qui une fois de plus montre qu'il y a une distance entre le concept
souvent simple voire trivial, et l'impl�mentation. Bref, ne confondons
pas r�cursivit� de salon et r�cursivit� de codeur.
Au demeurant, peut-�tre que certains certains langages sont plus aptes
que d'autres � suivre au plus pr�s la d�finition math�matique.
Marc Espie
Samuel Devulder <samuel-do...@geensys.com> wrote:
>Marc Espie a �crit :
>> In article <m2d431t...@minuetto.depot.rail.eu.org>,
>> Erwan David <er...@rail.eu.org> wrote:
>>
>>> �a c'est mon historique de d�veloppeur embarqu� qui parle...
>>
>> Ca veut juste dire que tu optimises la recursion terminale a la main
>> en presence de compilateurs deficients...
>Un truc a savoir, c'est que si l'optimiseur vire une r�cursivit�, ton
>prog devient nettement moins d�buggable par perte du contexte courant
>("stack frame"). En th�orie on s'en fiche, mais � l'usage c'est chiant
>et il vaut mieux que le compilo garde la structure asm assez proche du
>code d'origine.
En general, t'as un ou deux drapeaux dans ton compilo pour choisir quel
comportement adopter... et sauf code produit tres vite et rempli de bugs,
je prend toujours le cote "plus optimise".
>Je te raconte pas les surprise qu'on trouve en d�buggant un code
>optimis� par un compilo qui en fait trop.
T'as pas besoin, je pense que je connais aussi bien que toi... tant que
le compilo lui-meme n'est pas buggue, c'est pas un souci.
Apres tout, on est dans fr.comp.lang.c, donc la notion de comportement
observable, c'est dans le sujet. Et si on ne maitrise pas ce genre
de choses, ben il faut rester loin d'un compilo optimisant (tu veux
qu'on lance une flamewar sur restrict et sur les regles d'aliasing en C ?...)
>Par exemple au niveau
>couverture du code on se retrouve � passer par les deux branches d'un
>if() simultan�ment et crois moi c'est pas bon du tout pour certains
>crit�res de couverture du code (mc/dc etc). En plus quand le code ASM ne
>trace plus les lignes du code C dans le m�me ordre o� elle sont �crite
>rend le truc in-tra�able. En th�orie on s'en fiche d'avoir un code non
>tracable s'il est bon.. mais voila le moindre code, meme hyper simple,
>est souvent bugg� (cf les pbs d'overflow en arithmetique) et on est
>content d'avoir un code ASM assez proche du code C.
Ca, par contre, les soucis d'overflow en arithmetique, ca empeche souvent
un gros ensemble d'optimisations naturelles, surtout si tu es dans un
environnement ou les overflow signalent. Mais bon, la-aussi tu sais ca
aussi bien que moi.
Perso, si je voulais faire de l'asm, je ferais de l'asm. J'attend de mon
compilo qu'il fasse un boulot decent cote optimisation. Je suis conscient
que ca n'est pas toujours le cas sur certaines archis peu repandues, helas...
Samuel Devulder
> En general, t'as un ou deux drapeaux dans ton compilo pour choisir quel
> comportement adopter... et sauf code produit tres vite et rempli de bugs,
> je prend toujours le cote "plus optimise".
Oui. Mais je suis tomb� un jour sur une ex�cution pas a pas d'un code
bien trop optimis� au point de se demander si c'�tait effectivement le
bon fichier C qu'on ex�cutait tellement le flot du programme observ�
�tait diff�rent de celui cod�. Je serais tent� comme toi de dire qu'on
s'en fiche, qu'il faut faire confiance au compilo, certes, mais le pb
ici �tait dans les #define pr�sent dans le code, donc de d�terminer la
configuration du programme �tait la bonne ou pas. En 1ere approche je
pr�f�re que le compilo ne joue pas trop avec la structure du code. On
s'y retrouve mieux dans la maintenance.
C'est un probl�me uniquement pratique, je te l'accorde, mais important.
Si le programme a une r�cursivit� terminale, qu'il la laisse.. car en
cas de pb, on sera bien contant d'utiliser la stack pour voir ce qu'il
se passe. Si on veut optimiser, alors on �crit une boucle � la place
soit m�me. C'�tait le propos de Erwan je pense. Il faut bien voir que
dans certains contextes on ne peut uploader du code aussi souvent qu'on
veut et qu'il faut faire avec ce qui est en rom.
> Perso, si je voulais faire de l'asm, je ferais de l'asm. J'attend de mon
> compilo qu'il fasse un boulot decent cote optimisation. Je suis conscient
> que ca n'est pas toujours le cas sur certaines archis peu repandues, helas...
Oui. mais peu r�pandues... faut voire.. il y a quand meme quelques
dizaines d'ECU par voiture, ca en fait quelques millions de cpu �
l'archi peu r�pandue en circulation ;-) Tout est relatif au domaine en fait.
Non, comme je voulais le souligner, ce que chacun attends d'un compilo C
n'est pas identique suivant les professions.
Dans le domaine de l'embarqu�, on ne peut faire de l'ASM � la main pour
des raisons de taille (les projets petits � moyens font quelques
dizaines de millions de lignes de codes � traiter par le compilo) et de
co�t de maintenance. Du coup il y a quelques fonctions ASM tr�s bas
niveau et beaucoup, mais alors beaucoup de C autour. L'important est ici
de faire tenir des millions de lignes de C dans quelques centaines de Ko.
On demande au compilo d'optimiser en vitesse, mais pas forc�ment au
d�triment de la taille (enfin bon, on fait des compromis en pratique).
Quelque part on veut que le compilo compile comme on aurait �crit � la
main avec quelques astuces mais pas beaucoup plus car �a devient
infernal � tracer. Le fait que les compilos ne changent pas les flots
(donn�es/contr�le) dans le programme n'est pas une preuve de leur
faiblesse, bien au contraire, mais un choix dict� par la pratique.
Du coup les optims qu'on trouve dans ces compilos sp�cialis�s ne sont
pas les trucs type r�cursivit� terminale, mais plutot des trucs propres
au cpu comme l'utilisation d'instruction compactes ou pr�-cabl�es
(calculs min/max, ou interpolation lin�aire).
Bref chaque domaine a des besoins differents d'un compilo C et il est
assez "injuste" de qualifier les uns ou les autre de mauvais parce
qu'ils supportent ou pas l'optimisation de recursivit� terminale.
sam (c'est juste mon avis).
Wykaaa
> Wykaaa a �crit :
>
>> C'est quoi un "pool commun" ?
>> Des variables globales ? statiques ?
>
> En pratique c'est souvent le cas mais on peut aussi passer en param�tre
> un pointeur vers ce qui va �tre le pool.
>
>> Quand on utilise la r�cursivit�, on va �viter les variables justement
>> (on n'utilisera que des param�tres).
>
>
> Regarde un impl�mentation correcte de qsort() par un quicksort et tu
> verras qu'il n'y a pas que des param�tres. J'ai celle de Plauger sous
> les yeux (c'est pas vraiment un mauvais programmeur!) et il d�finit un
> paquet de variables. Au final, c'est pas tr�s g�nant vu que la
> complexit� est en n*ln(n) donc on limite la casse.
>
>
> On peut bien s�r �viter les variables mais alors on introduit des
> param�tres factices, qui ne servent qu'au fonctionnement interne de la
> fonction, bref on m�lange interface et impl�mentation, le truc que je
> d�teste.
C'est une question de modularit� dans les fonctions. Je suis d'accord
que l'environnement doit �tre global.
>
>> On ne va faire que des appels de
>> fonctions (r�cursivement). C'est �videmment possible en C.
>
> Oui, tu enfonces des portes ouvertes.
Non. Je voulais dire vraiment programmer en fonctionnel sans variable.
>
>
>> La programmation fonctionnelle, tu connais ?
>
> Plusieurs de mes coll�gues ont tent� de m'y convertir (enfin � Caml)
> mais en vain.
Quelle tristesse :-(
>
>
>> Les langages sans affectation, tu connais ?
>
> Non
>
>> Les langages � assignation unique, tu connais ?
>
> Non
>
>> L'�valuation paresseuse, tu connais ?
>
>
> Lazy evaluation ? j'ai vu le nom dans des docs Python mais je ne sais
> pas ce que c'est.
Alors je comprends que tu n'aime pas la r�cursivit�.
>
>
>> Fonction d'Ackermann en Haskell :
>> ackermann 0 n = (n + 1)
>> ackermann m 0 = ackermann (m-1) 1
>> ackermann m n = ackermann (m-1) (ackermann m (n-1))
>>
>> Justement, le mieux c'est de suivre, au plus pr�s, la d�finition
>> math�matique.
>
> Certainement pas. Exemple classique :
>
> int f(int n)
> {
> return n <= 1 ? 1 : f(n - 1) + f(n - 2);
> }
>
Oui la suite de Fibonacci �crite de cette mani�re n'est pas optimis�e
car les m�mes �valuations se font � plusieurs endroits.
>
> ce qui une fois de plus montre qu'il y a une distance entre le concept
> souvent simple voire trivial, et l'impl�mentation. Bref, ne confondons
> pas r�cursivit� de salon et r�cursivit� de codeur.
Ce n'est pas � moi que tu vas tenir ce discours. J'ai tremp� pendant 10
ans dans les compilateurs et il y avait de la r�cursion � tous les
�tages... M�me pour le calcul d'adresse dans les g�n�rateurs de code.
L'optimiseur global faisait des transformations sur les arbres,
repr�sentant le code du programme � compiler, que par des "patterns"
d'appels de fonctions r�cursives imbriqu�es !
Et crois-moi, ce n'�tait pas du code pour montrer la r�cursion aux
�tudiants. C'�tait g�nial � maintenir et � faire �voluer (ajouter des
optimisations, par exemple). Il suffisait "d'ajouter au bon endroit un
"pattern" d'appel. Le nouveau pattern de transformation pouvait �tre
long � trouver (conception) mais il fallait 2 minutes pour l'ajouter
dans le code.
> Au demeurant, peut-�tre que certains certains langages sont plus aptes
> que d'autres � suivre au plus pr�s la d�finition math�matique.
C'est pour cette raison que j'ai montr� du code en Haskell qui est
r�put� pour bien g�rer la r�cursivit�.
candide
> Alors je comprends que tu n'aime pas la r�cursivit�.
Au contraire, j'adore pratiquer la r�cursivit� et je peux passer des
heures � �purer un code r�cursif.
Je ne vois pas ce qui te laisse dire �a. Tout ce dont tu as parl�
pr�c�demment n'a rien � voir avec le C me semble-t-il et je ne vois pas
en quoi �a m'aiderait � mieux coder en C.
> Oui la suite de Fibonacci �crite de cette mani�re n'est pas optimis�e
> car les m�mes �valuations se font � plusieurs endroits.
>>
>> ce qui une fois de plus montre qu'il y a une distance entre le concept
>> souvent simple voire trivial, et l'impl�mentation. Bref, ne confondons
>> pas r�cursivit� de salon et r�cursivit� de codeur.
>
> Ce n'est pas � moi que tu vas tenir ce discours. J'ai tremp� pendant 10
> ans dans les compilateurs et il y avait de la r�cursion � tous les
> �tages...
La question n'�tait pas l�, tu m'as dit qu'un algorithme r�cursif devait
suivre "au plus pr�s" la d�finition math�matique. Mon exemple ci-dessus
prouve le contraire et d'autres exemples pourraient montrer que la
r�cursivit� est plus compliqu�e � comprendre que ce que dit Richard
Delorme.
bpasc...@googlemail.com
> Bonjour,
>
> le message
> <d99cd762-ed06-4f79-af6a-f6ecd5136...@e27g2000yqd.googlegroups.com> :
>
> >> loin dans la programmation, je veux comprendre ce qui se passe dans la
> >> machine tant que c'est à "porter de mains".
>
> > Tu ne conduis une voiture que si tu es un expert en sciences
> > mécanique ?
>
> L'analogie est mauvaise. La programmation, c'est plutôt la fabrication
> de la voiture, l'utilisation du programme étant la conduite.
Je suis d'accord.
> Je veux fabriquer une voiture. Dans tous les cas il me faut des plans
> (algorithmes) et c'est indépendant du choix que je vais faire pour sa
> fabrication (langage de programmation). Ensuite, j'ai le choix :
>
> - je veux construire moi-même toutes les pièces (assembleurs)
> - je veux acheter toutes les matières premières et réaliser tous les
> usinages, par contre j'utilise des vis du commerce (C)
> - je veux acheter des composants existants dans le commerce comme le
> moteur, la carrosserie et ne réaliser que l'assemblage (Python,
> Perl, etc.)
Je viens d'un pays très pauvre (dans les dix derniers selon le
classement...). Les 2 roues moto petites cylindrées avec et sans
embrayage importées sont fréquentes. Si je suis jeune dans ce pays qui
à ce jour offre peu d'avenir, je vais apprendre à réparer ces moteurs
et apprendre comment ça fonctionne. Maintenant dans certains cas, je
dois apprendre à forger pour fabriquer les pièces difficiles à trouver
ou récupérer des pièces endommagés...déformées...
> Ça reste une analogie, la réalité est un peu plus complexe quand au
> choix du langage.
>
> Ceci dit, pour quelqu'un qui n'est pas informaticien (comme moi) et
> qui ne pratique pas la programmation de manière régulière, il ne faut
> pas s'attendre à pouvoir programmer en C correctement avant plusieurs
> années (pratiquement dix ans dans mon cas mais je suis une
> feignasse ;-) ).
peut-être j'aurais besoin de 20 ans...sérieusement
> Je pense qu'on apprends un langage de programmation comme une langue
> étrangère : au début, on comprends rien et c'est bien normal. Il ne faut
> surtout pas s'attarder sur tous les petits détails sinon on n'apprend
> rien. Avec le temps, on commence à comprendre le sens des phrases même
> si on ne comprend pas chaque mot. Avec la pratique, on acquière des
> automatismes qui permettent de ne plus réfléchir à certaines choses et
> donc de pouvoir se concentrer sur d'autre dont on ignorait l'existence.
Progress is a small process*
> Pour une personne qui apprend seule, parler couramment, avoir l'accent
> et pouvoir faire du littéraire, c'est beaucoup, beaucoup de travail (je
> veux pas décourager mais je pense même que c'est quasiment impossible).
> Si l'on veux vraiment avoir une maîtrise du langage, la seule solution
> c'est d'aller dans un pays où les gens parlent cette langue (milieu
> professionnel ou participer au développement d'une application réelle).
Un ordinateur est déjà un outil formidable pour apprendre
l'informatique et c'est accessible.
Mais tu as raison, pour parler avec l'accent et les expressions
locales, il n'y a pas d'autres solutions que d'aller pendant une
longue période dans le pays et . Pour faire du littéraire, c'est une
autre question.
> Mes deux cents.
*50 cents
> Benoit Izac
Merci
bpasc...@googlemail.com
> bpascal...@googlemail.com a écrit :
>
> >> void f(int n)
> >> {
> >> if (n > 0)
> >> {
> >> f(n - 1);
> >> printf("%d ", (n - 1) * (n - 1));
> >> }
>
> >> }
>
> > Qu'est-ce qui se produit après "f(n-1)" ?La séquence "rembobine"???
>
> Oui
>
> > càd après void f(10) ;
>
> Euh non, void f(10) ne veut rien dire.
>
> Bon pour simplifier les explications, supposons que le code soit
>
> #include <stdio.h>
>
> void f(int n)
> {
> if (n > 0)
> {
> f(n-1)
> printf("%d ", (n - 1) * (n - 1));
> }
>
> }
>
> int main(void)
> {
> f(3);
> printf("\n");
> return 0;
>
> }
>
> et qui affiche :
>
> 0 1 4
>
> Au premier appel f(3), immédiatement f est relancée par l'appel f(2) qui
> lui même est relancé par f(1) qui à nouveau appelle f(0). C'est
> l'empilement des appels. Donc pour chacun de ces appels, l'exécution de
> la fonction f s'est arrêté à la ligne suivante :
>
> f(n - 1);
>
> Maintenant, à cause de la ligne
>
> if (n > 0)
>
> f(0) se termine dans rien faire et c'est là que vient le point capital :
> on revient à la fonction appelante (/return to the caller/) qui était f
> bien sûr avec le paramètre n=1. Donc le programme continue après la ligne
>
> f(n - 1);
>
> et donc avec l'instruction
>
> printf("%d ", (n - 1) * (n - 1));
>
> où n=1 ce qui affiche 0. Vu le code de f, l'exécution de f(1) se termine
> et comme f(1) avait été appelé par f(2), on continue le programme là où
> il était resté, le printf est exécuté. Bon, et ainsi de suite jusqu'au
> premier appel (n=3) et qui va afficher 4 puis se terminer. La fonction
> qui avait appelée f(3) est main() donc on revient à main, ce qui clot le
> programme.
>
> Le fait que la fonction soit récursive ne change en fait
> fondamentalement rien à la façon dont les appels sont effectués et achevés.
>
> > void f(9) au second appel )à cause de f
> > (n-1), ...void f(8) ... où printf est inclus avant que la séquence
> > rembobine dans ce cas, 81 64 42 ...devrait être affichés ?
>
> Non, justement. Modifie le code en plaçant le f(n-1) après le printf()
> et tu verras ce qu'il se passe.
merci
Wykaaa
> Wykaaa a �crit :
>
>> Alors je comprends que tu n'aime pas la r�cursivit�.
>
> Au contraire, j'adore pratiquer la r�cursivit� et je peux passer des
> heures � �purer un code r�cursif.
>
> Je ne vois pas ce qui te laisse dire �a. Tout ce dont tu as parl�
> pr�c�demment n'a rien � voir avec le C me semble-t-il et je ne vois pas
> en quoi �a m'aiderait � mieux coder en C.
Non, tout ce que j'ai dis a � voir avec la r�cursivit� et �a s'applique
� tous les langages o� la r�cursivit� peut �tre mise en oeuvre.
>
>
>> Oui la suite de Fibonacci �crite de cette mani�re n'est pas optimis�e
>> car les m�mes �valuations se font � plusieurs endroits.
>>> ce qui une fois de plus montre qu'il y a une distance entre le concept
>>> souvent simple voire trivial, et l'impl�mentation. Bref, ne confondons
>>> pas r�cursivit� de salon et r�cursivit� de codeur.
>> Ce n'est pas � moi que tu vas tenir ce discours. J'ai tremp� pendant 10
>> ans dans les compilateurs et il y avait de la r�cursion � tous les
>> �tages...
>
> La question n'�tait pas l�, tu m'as dit qu'un algorithme r�cursif devait
> suivre "au plus pr�s" la d�finition math�matique. Mon exemple ci-dessus
> prouve le contraire et d'autres exemples pourraient montrer que la
> r�cursivit� est plus compliqu�e � comprendre que ce que dit Richard
> Delorme.
>
Je suis d'accord avec Richard Delorme. La r�cursivit� n'est pas dure �
comprendre, du moins pour la r�cursion directe (une fonction qui
s'appelle elle-m�me) car, dans ce cas, il suffit de dire que l'appel
r�cursif doit �tre tel que l'on est certain, qu'� un moment donn�, la
condition d'arr�t sera rencontr�e.
bpasc...@googlemail.com
> Au premier appel f(3), immédiatement f est relancée par l'appel f(2) qui
> lui même est relancé par f(1) qui à nouveau appelle f(0). C'est
> l'empilement des appels. Donc pour chacun de ces appels, l'exécution de
> la fonction f s'est arrêté à la ligne suivante :
Bonjour,
J'ai pu comprendre le concept de récursivité avec votre explication.
Je comprends également que pour comprendre des récursions plus
"sophistiquées", une compréhension de ce qui se passe en compilation/
assembleur est nécessaire. Je pense à l'accès des données en mémoire.
Je ne suis pas encore là, je souhaiterais sortir de ce livre sur
l'architecture des ordinateurs pour passer à la pratique mais si je
vais trop vite, je pense que je devrais retourner à ce livre (et
puisl'inconvénient d'etre autodidacte; il y a aussi le manque de
motivation). Mais selon ce qui est dit dans cette discussion,
comprendre la récursivité permet de comprendre for et while ...
Ce livre n'est pas à coté maintenant mais j'ai en mémoire d'un
pointeur IP ou quelque chose comme ca qui "empile" le résultat des
fonctions dans le stack ou heap je crois et retourne à l'adresse d'une
données dans un buffer selon les instructions du séquenceur ou de
l'unité de commande...
Je pensais que IP n'était employé que pour les fonctions vers les
pointeurs. Et c'est pourquoi je n'ai pas fait le lien en
premier'depuis le début de cette discussion et votre réponse) avec les
fonctions de récursivité qui ne sont pas des fonctions vers les
pointeurs.
Peut-être c'est un autre sujet, mais une fonction vers un pointeur
pourrait rendre l'appel d'une fonction récursive plus rapide?
Merci,
Pascal
Senhon
<bpasc...@googlemail.com> a �crit dans le message de groupe de discussion
: 458d9849-cb8d-447f...@e23g2000yqd.googlegroups.com...
>
>> Au premier appel f(3), imm�diatement f est relanc�e par l'appel f(2) qui
>> lui m�me est relanc� par f(1) qui � nouveau appelle f(0). C'est
>> l'empilement des appels. Donc pour chacun de ces appels, l'ex�cution de
>> la fonction f s'est arr�t� � la ligne suivante :
>
> Bonjour,
> J'ai pu comprendre le concept de r�cursivit� avec votre explication.
> Je comprends �galement que pour comprendre des r�cursions plus
> "sophistiqu�es", une compr�hension de ce qui se passe en compilation/
> assembleur est n�cessaire. Je pense � l'acc�s des donn�es en m�moire.
> Je ne suis pas encore l�, je souhaiterais sortir de ce livre sur
> l'architecture des ordinateurs pour passer � la pratique mais si je
> vais trop vite, je pense que je devrais retourner � ce livre (et
> puisl'inconv�nient d'etre autodidacte; il y a aussi le manque de
> motivation). Mais selon ce qui est dit dans cette discussion,
> Ce livre n'est pas � cot� maintenant mais j'ai en m�moire d'un
> pointeur IP ou quelque chose comme ca qui "empile" le r�sultat des
> fonctions dans le stack ou heap je crois et retourne � l'adresse d'une
> donn�es dans un buffer selon les instructions du s�quenceur ou de
> l'unit� de commande...
> Je pensais que IP n'�tait employ� que pour les fonctions vers les
> pointeurs. Et c'est pourquoi je n'ai pas fait le lien en
> fonctions de r�cursivit� qui ne sont pas des fonctions vers les
> pointeurs.
> Peut-�tre c'est un autre sujet, mais une fonction vers un pointeur
> pourrait rendre l'appel d'une fonction r�cursive plus rapide?
> Merci,
> Pascal
Houlala, tu embrouilles tout.
Senhon
<bpasc...@googlemail.com> a �crit dans le message de groupe de discussion
: 458d9849-cb8d-447f...@e23g2000yqd.googlegroups.com...
>
>> Au premier appel f(3), imm�diatement f est relanc�e par l'appel f(2) qui
>> l'empilement des appels. Donc pour chacun de ces appels, l'ex�cution de
>> la fonction f s'est arr�t� � la ligne suivante :
>
> Bonjour,
> J'ai pu comprendre le concept de r�cursivit� avec votre explication.
> Je comprends �galement que pour comprendre des r�cursions plus
> "sophistiqu�es", une compr�hension de ce qui se passe en compilation/
> assembleur est n�cessaire. Je pense � l'acc�s des donn�es en m�moire.
> Je ne suis pas encore l�, je souhaiterais sortir de ce livre sur
> l'architecture des ordinateurs pour passer � la pratique mais si je
> vais trop vite, je pense que je devrais retourner � ce livre (et
> motivation). Mais selon ce qui est dit dans cette discussion,
> Ce livre n'est pas � cot� maintenant mais j'ai en m�moire d'un
> pointeur IP ou quelque chose comme ca qui "empile" le r�sultat des
> fonctions dans le stack ou heap je crois et retourne � l'adresse d'une
> donn�es dans un buffer selon les instructions du s�quenceur ou de
> Je pensais que IP n'�tait employ� que pour les fonctions vers les
> pointeurs. Et c'est pourquoi je n'ai pas fait le lien en
> pointeurs.
> Peut-�tre c'est un autre sujet, mais une fonction vers un pointeur
> pourrait rendre l'appel d'une fonction r�cursive plus rapide?
> Merci,
> Pascal
Houlala, tu embrouilles tout, le hard, l'asm, le C.
Suis les recommandations de Candide parce que l� tu semble tr�s mal
embringu�.
Senhon
"Marc Espie" <es...@lain.home> a �crit dans le message de groupe de
discussion : hettah$25et$1...@saria.nerim.net...
> Tu m'emmerdes. Va chercher dans la biblio. J'emploie des termes precis. Tu
...
> M'a echappe ? mais va te faire foutre ! C'est pas parce que tu veux
...
>>Le code plus ou moins standard du pgcd r�cursif est :
> "plus ou moins". c'est juste une autre facon d'ecrire la meme chose.
> Tu l'as recopie de quelque part, pour dire que c'est standard ? ou tu
> arrives
> encore a inventer trois lignes de code sans les repiquer ailleurs ?
...
> La j'avoue, la coupe est pleine. J'en ai plus que marre de tes frasques.
...
> A force de jouer au "candide" qui reprend tout et tout le monde en jouant
> ta mouche du coche, et en voulant imposer aux gens ta vision etriquee du
> monde, tu as finalement reussi a m'enerver un peu.
...
> M'en fous, a troll, troll-et-demi. J'ai la peau plus solide que toi. Si tu
> cherches la bagarre...
Candide explique au moins. Toi, noy� dans l'agressivit�, il y a aussi des
explications, mais au final on n'en retient que la vulgarit� ( au sens
p�joratif ) de tes propos.
Marc Boyer
Bon, mon passé d'enseignant me fait bondir quand je lit tout ça.
Le 28-11-2009, bpasc...@googlemail.com <bpasc...@googlemail.com> a écrit :
>
> J'interviens su r ce forum de manière irrégulière, pour l'instant je
> concentre mes efforts vers les algorithmes. Je me concentre vers le
> langage assembleur. Je ne veux pas approfondir. Avant d'aller plus
> loin dans la programmation, je veux comprendre ce qui se passe dans la
> machine tant que c'est à "porter de mains".
1) Pour apprendre l'algorithmique, le C est un bien mauvais outil.
Les analogies ont toutes leurs limites, alors disons pour simplifier
que C a ses raisons d'être pour les pros, mais que débuter avec ça
en 2009, c'est chercher les complications.
2) L'assembleur, ce n'est justement pas "à portée de main"
A moins que les ASM ne se soient simplifiés depuis 10 ans,
pleins de pb von se poser au débutant.
Ca va commencer avec les opérations signées, non signées,
8,16,32,64 bits, extensions de signes qui feraient presque
aimer celles du C.
On va ajouter les jolis pb d'instructions après le branchement
qui sont quand même exécutés à cause du pipe-line.
Les E/S à base d'interuptions, ça va être une jolie affaire,
surtout que les OS modernes vont surement pas laisser n'importe
quel code accéder comme ça aux périphériques.
On doit pouvoir s'en passer en liant l'ASM à des biblios
d'E/S en C, mais pour le débutant, ça risque d'être pas mal.
Je ne suis pas sur que la gestion des segments mémoire soit
très facile elle aussi....
> En fait, je ne viens pas sur ce forum pour savoir ce qui serait bien
> pour les intestins ou le foi. J'ai quand même du mal à imaginer que le
> langage C est inutile.
Le C n'est pas inutile. Mais apprendre à programmer en autodidacte
en C, c'est un peut comme apprendre à nager dans la rade de Brest
un jour de grand vent... On passe son temps à se noyer (sauf que
dans la natation on se noie qu'une fois).
Marc Boyer
--
En prenant aux 10% des francais les plus riches 12% de leurs revenus,
on pourrait doubler les revenus des 10% les plus pauvres.
http://www.inegalites.fr/spip.php?article1&id_mot=130
Marc Boyer
> Bonjour,
> Ceci dit, pour quelqu'un qui n'est pas informaticien (comme moi) et
> qui ne pratique pas la programmation de manière régulière, il ne faut
> pas s'attendre à pouvoir programmer en C correctement avant plusieurs
> années (pratiquement dix ans dans mon cas mais je suis une
> feignasse ;-) ).
Il faut savoir mettre les choses en balance. En gros, en IUT, il
faut 2 ans pour faire un programeur pro débutant.
En 100-200 heures, on peut apprendre des bases correctes de
programmation pour des petits projets (<10.000 lignes).
Antoine Leca
> le 29/11/2009 à 11:07, -ed- <emmanuel.delahaye@> a écrit dans le message
> <d99cd762-ed06-4f79...@e27g2000yqd.googlegroups.com> :
>
>>> loin dans la programmation, je veux comprendre ce qui se passe dans la
>>> machine tant que c'est à "porter de mains".
>> mécanique ?
>
> L'analogie est mauvaise. La programmation, c'est plutôt la fabrication
> de la voiture, l'utilisation du programme étant la conduite.
>
> (algorithmes) et c'est indépendant du choix que je vais faire pour sa
> fabrication (langage de programmation).
C'est une bonne description de la _fabrication_ des voitures, mais ce
n'est pas une analogie correcte pour la programmation ÀMHA. Ce que tu
décris est limité à la partie codage. Pour moi, la programmation intègre
aussi la partie conception (faire les plans).
Et ce, même si les SSII ont décidé que cette activité de conception
devait s'appeler « analyse » et être différenciée de l'activité
« programamtion » (supposée moins noble et facturée moins chère ; je ne
sais pas si cette distinction est toujours d'actualité, d'ailleurs.)
Antoine
Marc Boyer
> candide a écrit :
>> Il y a plein de programmeurs C (C ou autre) qui n'ont jamais rien
>> pensum (qui est aussi une belle tarte à la crème).
>
> La "tarte à la crème" c'est de faire croire qu'on peut se dispenser de
> comprendre la récursivité quand on est programmeur. Ceci est totalement
> faux.
Ca dépend de la définition de "programmeur".
> Tout algorithme qui requiert un automate à pile est souvent beaucoup
> plus facile à coder de façon récursive (exemple : la reconnaissance
> syntaxique des expressions arithmétiques).
> Et puis nombre d'algorithmes sur les arbres, voire les listes, sont bien
> plus faciles à programmer de façon récursive.
Mais dans la vraie vie, ils ont été empaquetté dans un truc qui va
s'appeller std::map, java.util.TreeSet, lex/yak ou un truc du genre.
> La récursivité est un concept clé de la programmation (et de
> l'informatique et des mathématiques en général).
Oui, la notion de calculabilité aussi, et le typage aussi,
et Turing aussi... Est-ce bien nécessaire pour faire un site
de e-commerce ?
Marc Boyer
> Dernier point: en embarque la vitesse n'est pas le problème. Les mhz
> sont souvent là plus que nécéssaire (80Mhz pour traiter des trucs qui
> arrivent à une freq de 5khz ca le fait les doigts dans le nez), mais ce
Je pense qu'il y a différents mondes "embarqués". Chez les avioneurs,
on réduit aussi le nombre de CPU (pour diminuer l'alim), et on a
tendance à charger la CPU le plus qu'on puisse (en restant déterministe).
Il existe des calculateurs qui sont vraiment très chargés.
Antoine Leca
>> T'as un lien vers les sources de ld ou un truc du genre ?
>
Tiens, OpenBSD maintient toujours l'éditeur de liens dynamiques de Paul
Kranembourg ? Je croyais que toutes les cibles étaient passées à ELF ?
En tous cas, je ne vois pas en quoi les variations exposées dans cette
version de ld ont un quelconque intérêt en matière de récursivité.
Antoine
Antoine Leca
> On apprend plus les suites en Math�matiques � l'�cole ?
<snip>
> Si l'on a compris �a, on a compris la r�cursivit�.
Comprendre comment cela marche ne signifie pas que l'on soit capable
d'utiliser, c'es-�-dire de r�soudre un probl�me d'arithm�tique (o� a
priori il n'y a pas de suite ou s�rie visibles) en *introduisant* des
suites ou des s�ries.
Et l�, je n'ai pas l'impression que les �l�ves qui sortent du lyc�e
soient tous capables de le faire (� commencer par moi � l'�poque.)
Antoine
Antoine Leca
> Wykaaa a �crit :
[ contexte utile rajout� ]
::: On n'est pas un programmeur nul si on ne maitrise pas la r�cursivit�.
>> Bin si, justement. Tiens, �crit un �diteur de lien sans utiliser la
>> r�cursion, juste pour voir...
>
> Et tu crois que tout programmeur C a le background pour �crire un
> �diteur de liens ? Le programmeur qui �crit un compilateur ou des outils
> de ce genre n'est pas le programmeur lambda.
Je crois que tu as loup� l'argument de Fran�ois.
Au d�but (disons jusque vers 1980, �15 ans pour me couvrir), les
�diteurs de liens n'utilisaient pas de r�cursivit� dans la recherche des
symboles ind�finis dans les biblioth�ques, et pour palier ce /l�ger/
probl�me, les utilisateurs de ces �diteurs devaient jongler avec des
outils comme ranlib, lorder/tsort, pour ranger les modules objet
� dans le bon ordre � dans les biblioth�ques, afin que l'�diteur des
liens puisse en une seule passe trouver tous les modules � lier. Et s'il
y avait des cycles, la seule solution �tait de faire manuellement
plusieurs passes de ld -r. Hideuse solution, que Fran�ois attribue � des
programmeurs nuls.
> T'as un lien vers les sources de ld ou un truc du genre ?
http://minnie.tuhs.org/UnixTree/V7/usr/src/cmd/ld.c.html
Antoine
Richard Delorme
>
> Bon, mon passé d'enseignant me fait bondir quand je lit tout ça.
>
> Le 28-11-2009, bpasc...@googlemail.com<bpasc...@googlemail.com> a écrit :
>>
>> J'interviens su r ce forum de manière irrégulière, pour l'instant je
>> concentre mes efforts vers les algorithmes. Je me concentre vers le
>> langage assembleur. Je ne veux pas approfondir. Avant d'aller plus
>> loin dans la programmation, je veux comprendre ce qui se passe dans la
>> machine tant que c'est à "porter de mains".
>
> 1) Pour apprendre l'algorithmique, le C est un bien mauvais outil.
> Les analogies ont toutes leurs limites, alors disons pour simplifier
> que C a ses raisons d'être pour les pros, mais que débuter avec ça
> en 2009, c'est chercher les complications.
>
> 2) L'assembleur, ce n'est justement pas "à portée de main"
> A moins que les ASM ne se soient simplifiés depuis 10 ans,
> pleins de pb von se poser au débutant.
Je suis d'accord avec ce que tu dis et pour explorer des algorithmes ou
apprendre à programmer, un langage comme Python est plus approprié que
le langage C ou l'assembleur. Une nuance néanmoins, c'est qu'il existe
d'excellent livres sur les algorithmes, en C (Algorithms in C de R.
Sedgevick) ou en Assembleur (The Art of Programming de D. Knuth) et très
peu à l'aide de langage plus abordables.
--
Richard
Marc Boyer
> Le 30/11/2009 11:27, Marc Boyer a écrit :
>>
>> Bon, mon passé d'enseignant me fait bondir quand je lit tout ça.
>>
>>>
>>> J'interviens su r ce forum de manière irrégulière, pour l'instant je
>>> concentre mes efforts vers les algorithmes. Je me concentre vers le
>>> langage assembleur. Je ne veux pas approfondir. Avant d'aller plus
>>> loin dans la programmation, je veux comprendre ce qui se passe dans la
>>> machine tant que c'est à "porter de mains".
>>
>> 1) Pour apprendre l'algorithmique, le C est un bien mauvais outil.
>> Les analogies ont toutes leurs limites, alors disons pour simplifier
>> que C a ses raisons d'être pour les pros, mais que débuter avec ça
>> en 2009, c'est chercher les complications.
>>
>> 2) L'assembleur, ce n'est justement pas "à portée de main"
>> A moins que les ASM ne se soient simplifiés depuis 10 ans,
>> pleins de pb von se poser au débutant.
>
> Je suis d'accord avec ce que tu dis et pour explorer des algorithmes ou
> apprendre à programmer, un langage comme Python est plus approprié que
> le langage C ou l'assembleur. Une nuance néanmoins, c'est qu'il existe
> d'excellent livres sur les algorithmes, en C (Algorithms in C de R.
> Sedgevick) ou en Assembleur (The Art of Programming de D. Knuth) et très
> peu à l'aide de langage plus abordables.
Là encore, qu'appelle-t-on "apprendre l'algorithmique" ?
Je n'ai pas d'idée sur celui de Sedgevick que je ne connais
pas. Mais celui de Knuth me semble hors de portée d'un débutant.
L'algorithmique du débutant, c'est arriver dans une seule boucle
a trouver le minimum, le maximum et calculer la moyenne d'une
suite de nombres. C'est arriver à contruire un entier en lisant
les chiffres pas la gauche ou par la droite. C'est arriver à afficher
un nombre en affichant les chiffres un par un.
Wykaaa
> Le 29-11-2009, Wykaaa <wyk...@yahoo.fr> a écrit :
>> candide a écrit :
>>> Il y a plein de programmeurs C (C ou autre) qui n'ont jamais rien
>>> compris à la récursivité donc te crois pas obligé de passer par ce
>>> pensum (qui est aussi une belle tarte à la crème).
>> La "tarte à la crème" c'est de faire croire qu'on peut se dispenser de
>> comprendre la récursivité quand on est programmeur. Ceci est totalement
>> faux.
>
> Ca dépend de la définition de "programmeur".
Qu'est-ce à dire ?
>
>> Tout algorithme qui requiert un automate à pile est souvent beaucoup
>> plus facile à coder de façon récursive (exemple : la reconnaissance
>> syntaxique des expressions arithmétiques).
>> Et puis nombre d'algorithmes sur les arbres, voire les listes, sont bien
>> plus faciles à programmer de façon récursive.
>
> Mais dans la vraie vie, ils ont été empaquetté dans un truc qui va
> s'appeller std::map, java.util.TreeSet, lex/yak ou un truc du genre.
C'est vrai mais il y en a encore beaucoup qui sont victimes du syndrome
NIH (Not Invented Here).
>
>> La récursivité est un concept clé de la programmation (et de
>> l'informatique et des mathématiques en général).
>
> Oui, la notion de calculabilité aussi, et le typage aussi,
> et Turing aussi... Est-ce bien nécessaire pour faire un site
> de e-commerce ?
On ne se plaindra pas du fait que les sites de e-commerce soient bogués :-)
Marc Boyer
> Marc Boyer a écrit :
>> Le 29-11-2009, Wykaaa <wyk...@yahoo.fr> a écrit :
>>> candide a écrit :
>>>> Il y a plein de programmeurs C (C ou autre) qui n'ont jamais rien
>>>> compris à la récursivité donc te crois pas obligé de passer par ce
>>>> pensum (qui est aussi une belle tarte à la crème).
>>> La "tarte à la crème" c'est de faire croire qu'on peut se dispenser de
>>> comprendre la récursivité quand on est programmeur. Ceci est totalement
>>> faux.
>>
>> Ca dépend de la définition de "programmeur".
>
> Qu'est-ce à dire ?
Que cette définition varie suivant celui qui la prononce.
Je préfère parler de chemin de progression, et la récursivité
n'est pas sur le tout début du chemin. Et l'OP a pas mal
de choses à voir avant AMHA.
>>> Tout algorithme qui requiert un automate à pile est souvent beaucoup
>>> plus facile à coder de façon récursive (exemple : la reconnaissance
>>> syntaxique des expressions arithmétiques).
>>> Et puis nombre d'algorithmes sur les arbres, voire les listes, sont bien
>>> plus faciles à programmer de façon récursive.
>>
>> Mais dans la vraie vie, ils ont été empaquetté dans un truc qui va
>> s'appeller std::map, java.util.TreeSet, lex/yak ou un truc du genre.
>
> C'est vrai mais il y en a encore beaucoup qui sont victimes du syndrome
> NIH (Not Invented Here).
Ben si j'ai à choisir entre passer 4h sur la récurcivité et passer
4h sur les bienfaits de la réutilisation de code éprouvé, mon choix
est vite fait (cf notion de chemin vue avant).
>>> La récursivité est un concept clé de la programmation (et de
>>> l'informatique et des mathématiques en général).
>>
>> Oui, la notion de calculabilité aussi, et le typage aussi,
>> et Turing aussi... Est-ce bien nécessaire pour faire un site
>> de e-commerce ?
>
> On ne se plaindra pas du fait que les sites de e-commerce soient bogués :-)
Je ne suis pas expert en bug de WEB 2.0, mais j'aurais tendance à croire
que c'est plus à cause de glue mal faites entre composants (ie mauvais
emplois de la ré-utilisation, paquetage, encapsulation) que de notions
de récursivité mal comprises.
Erwan David
> Le 29-11-2009, Samuel Devulder <samuel-do...@geensys.com> a �crit�:
>> Dernier point: en embarque la vitesse n'est pas le probl�me. Les mhz
>> sont souvent l� plus que n�c�ssaire (80Mhz pour traiter des trucs qui
>> arrivent � une freq de 5khz ca le fait les doigts dans le nez), mais ce
>> qui coince c'est la ROM et la RAM. Elles sont toutes petites en
>> embarqu�, et on pr�f�re de loin, mais vraiment de loin, optimiser en
>> taille (rom/ram) qu'en vitesse.
>
> Je pense qu'il y a diff�rents mondes "embarqu�s". Chez les avioneurs,
> on r�duit aussi le nombre de CPU (pour diminuer l'alim), et on a
> tendance � charger la CPU le plus qu'on puisse (en restant d�terministe).
>
> Il existe des calculateurs qui sont vraiment tr�s charg�s.
>
mon embarqu� �tait celui des terminaux de paiement bancaire. L� on
chercheiat � minimiser l'empreinte m�moire (code, donn�e et pile) au
d�triment peut-�tre des performances.
--
Le travail n'est pas une bonne chose. Si �a l'�tait,
les riches l'auraient accapar�
Marc Espie
Antoine Leca <ro...@localhost.invalid> wrote:
>Benoit Izac a écrit :
>>> T'as un lien vers les sources de ld ou un truc du genre ?
>>
>> <http://www.openbsd.org/cgi-bin/cvsweb/src/gnu/usr.bin/ld/>
>
>Tiens, OpenBSD maintient toujours l'éditeur de liens dynamiques de Paul
>Kranembourg ? Je croyais que toutes les cibles étaient passées à ELF ?
Non, vax n'est pas passe a elf. C'est pas si simple que ca. Si ces outils
n'etaient pas buggues, ca se saurait...
Marc Espie
bpasc...@googlemail.com <bpasc...@googlemail.com> wrote:
>
>> Au premier appel f(3), imm�diatement f est relanc�e par l'appel f(2) qui
>> l'empilement des appels. Donc pour chacun de ces appels, l'ex�cution de
>> la fonction f s'est arr�t� � la ligne suivante :
>
>Bonjour,
>J'ai pu comprendre le concept de r�cursivit� avec votre explication.
>Je comprends �galement que pour comprendre des r�cursions plus
>assembleur est n�cessaire.
Non. C'est necessaire pour comprendre comment ca fonctionne en pratique
et comment c'est implemente dans la machine. Ca n'est pas necessaire
pour *utiliser* de la recursion sophistiquee.
>Je pense � l'acc�s des donn�es en m�moire.
T'as juste besoin du concept de variable locale. Une fois que tu as saisi
que dans une fonction recursive f(int i), ben tu as une variable i *differente*
par niveau de recursion, ben tu sais tout. T'as pas besoin de savoir comment
la machine gere ca pour t'en servir...
Richard Delorme
> Là encore, qu'appelle-t-on "apprendre l'algorithmique" ?
> Je n'ai pas d'idée sur celui de Sedgevick que je ne connais
> pas. Mais celui de Knuth me semble hors de portée d'un débutant.
>
> L'algorithmique du débutant, c'est arriver dans une seule boucle
> a trouver le minimum, le maximum et calculer la moyenne d'une
> suite de nombres. C'est arriver à contruire un entier en lisant
> les chiffres pas la gauche ou par la droite. C'est arriver à afficher
> un nombre en affichant les chiffres un par un.
Je pensait au stade suivant, quand on est plus débutant, mais pas encore
un expert.
--
Richard
Antoine Leca
Marc Espie �crivit dans <news:hf0nj7$pd$2...@saria.nerim.net> :
> In article <hf0bkn$6oh$1...@shakotay.alphanet.ch>,
> Antoine Leca <ro...@localhost.invalid> wrote:
>> Tiens, OpenBSD maintient toujours l'éditeur de liens dynamiques de Paul
>> Kranembourg ? Je croyais que toutes les cibles étaient passées � ELF ?
>
Bzz... d�sol� pour le param�trage UTF-8 de mon client. Je plonge dans la
config et je vais essayer de corriger le tir � l'avenir...
<interlude>
Bigre, cela n'a pas l'air simple. Question pour les sp�cialistes :
Comment param�trer Tbird (ou quelle extension) pour avoir un retour
visuel qui permette de savoir si le message lu (ou mieux, celui auquel
on r�pond) est en UTF-8 plut�t qu'en iso-8859-machin ?
Question subsidiaire : quelle extension (ou quel param�trage) pour que
Tbird r�agisse correctement aux URLs <news:a@b>, � la RFC1738 �3.6 ?
Antoine
Olivier Miakinen
> [ Copie et suivi sur fr.comp.mail ]
Ok pour la copie, mais tu as oubliￜ le suivi. Je le positionne.
> Bigre, cela n'a pas l'air simple. Question pour les spï¿œcialistes :
> Comment paramï¿œtrer Tbird (ou quelle extension) pour avoir un retour
> visuel qui permette de savoir si le message lu (ou mieux, celui auquel
> on rï¿œpond) est en UTF-8 plutï¿œt qu'en iso-8859-machin ?
Pour celui que tu lis :
Affichage > Encodage des caractï¿œres
Pour celui que tu composes :
Options > Encodage des caractï¿œres
Dans un cas comme dans l'autre, tu peux en profiter pour le changer s'il
ne te convient pas (temporairement pour la lecture, dï¿œfinitivement pour
la composition).
Cordialement,
--
Olivier Miakinen
-ed-
> ben je vais poser la question à un vrai programmeur C, Emmanuel Delahaye
> : dis-nous, tu avais dit que tu avais programmé dans ta bibliothèque
> perso un automate à piles si je ne m'abuse. L'as tu codé en récursif ?
J'ai programmé un moteur d'automate à tableau dynamique (FSM), mais
pas du tout à pile ni récursif (interdit en embarqué sensible).
-ed-
wrote:
> Un truc a savoir, c'est que si l'optimiseur vire une récursivité, ton
> prog devient nettement moins débuggable par perte du contexte courant
> ("stack frame"). En théorie on s'en fiche, mais à l'usage c'est chiant
> et il vaut mieux que le compilo garde la structure asm assez proche du
> code d'origine.
Non. Le "truc à savoir", c'est qu'on ne débogue pas en mode
optimisé...
candide
> Je pensait au stade suivant, quand on est plus d�butant, mais pas encore
> un expert.
>
Sont en progression g�om�trique les marches avec toi ;) Sinon AMHA
Knuth, c'est peu comme Proust, souvent cit� mais peu lu.
(attention ce n'est pas une attaque personnelle ;) )
Samuel Devulder
>> prog devient nettement moins d�buggable par perte du contexte courant
>> ("stack frame"). En th�orie on s'en fiche, mais � l'usage c'est chiant
>> et il vaut mieux que le compilo garde la structure asm assez proche du
>> code d'origine.
>
> optimis�...
Va dire ca quand tu dois d�boguer un truc qui se passe en rom. Parfois
(souvent m�me suivant les m�tiers), le code ne tourne pas sur un PC et
on ne peut recompiler le projet � loisir. Il faut d�bugger le truc "en
place", avec des sondes JTAG et tout et tout. Sans compter que bien
souvent, le code non optimis� ne tient m�me plus dans la rom/ram/flash.
sam.
Richard Delorme
J'ai aussi cit� Sedgevick qui est tout-�-fait abordable d�s ce niveau.
M�me le C qu'il utilise est simplifi� � l'extr�me, et les explications
qu'il fournit sont tr�s didactiques (et peu math�matiques) mais
n�anmoins d�taill�es. Les ouvrages de Knuth sont certes plus
math�matiques. Mais, � la rigueur, ils sont tr�s abordables � un
math�maticien non informaticien.
--
Richard
Francois
Richard Delorme a �crit :
> Les ouvrages de Knuth sont certes plus
> math�matiques. Mais, � la rigueur, ils sont tr�s abordables � un
> math�maticien non informaticien.
Ont ils �t� un jour �t� traduits en fran�ais ?
--
Fran�ois Lafont
Wykaaa
> [ Copie et suivis sur fr.comp.mail ]
> Question subsidiaire : quelle extension (ou quel param�trage) pour que
> Tbird r�agisse correctement aux URLs <news:a@b>, � la RFC1738 �3.6 ?
Ah oui, moi aussi je veux savoir.
Marc Espie
Pas vraiment. Il y a eu des projets non aboutis par ITP, defunte maison
d'edition.
Marc Espie
Il y a des bouts de Knuth qui se lisent tres bien, et d'autres qui sont plus
a considerer comme ouvrage de reference. Lire tout Knuth prend une vie,
particulierement si on regarde les exercices...
(et puis il y a des bouts de Knuth, comme MIX, qui l'amusent beaucoup, mais
qui sont un peu superflus... pas assez pour pouvoir s'en passer, mais
suffisamment pour qu'on ait envie de zapper quelques paragraphes).
Il y aussi des bouts qui ont ete rattrapes depuis, quand meme. Il y a
d'excellentes publis sur les limites d'IEEE 754 qui completent tres
agreablement le "semi-numerical algorithms".
Dans les petits Knuth a recommander sans discernement, il y a
"mathematical writing", qui ne traite pas de programmatino, mais qui est
un excellent bouquin de style pour ouvrages techniques.
Francois
>>> Les ouvrages de Knuth sont certes plus
>>> math�matiques. Mais, � la rigueur, ils sont tr�s abordables � un
>>> math�maticien non informaticien.
>> Ont ils �t� un jour �t� traduits en fran�ais ?
>
> Pas vraiment. Il y a eu des projets non aboutis par ITP, defunte maison
> d'edition.
Ah, dommage. Merci pour la r�ponse.
--
Fran�ois Lafont
Marc Espie
-ed- <emmanuel...@gmail.com> wrote:
>On 29 nov, 17:42, Samuel Devulder <samuel-dot-devul...@geensys.com>
>wrote:
>> prog devient nettement moins d�buggable par perte du contexte courant
>> ("stack frame"). En th�orie on s'en fiche, mais � l'usage c'est chiant
>> et il vaut mieux que le compilo garde la structure asm assez proche du
>> code d'origine.
>
>optimis�...
Et tu fais comment quand tu tombes sur un bug qui ne se produit pas en
mode non-optimise.
J'en profite pour vouer les programmeurs de gcc aux gemonies. Quelle idee
foncierement debile d'initialiser les variables locales a 0 quand on n'est
pas en mode optimise !
Pierre Maurette
[...]
> Il y a des bouts de Knuth qui se lisent tres bien, et d'autres qui sont plus
> a considerer comme ouvrage de reference. Lire tout Knuth prend une vie,
Ah, oui.
C'est un peu comme Proust, non ?
--
Pierre Maurette
Marc Espie
Pierre Maurette <maurett...@wanadoo.fr> wrote:
>Marc Espie, le 30/11/2009 a �crit :
>
>[...]
>
>> Il y a des bouts de Knuth qui se lisent tres bien, et d'autres qui sont plus
>> a considerer comme ouvrage de reference. Lire tout Knuth prend une vie,
>
>Ah, oui.
>
>C'est un peu comme Proust, non ?
Je sais pas, j'ai jamais lu de Proust, et de ce qu'on m'en a dit, ca fait
pas envie ;-)