miracle de la récursion

Loïc Joly

13/12/2003 à 11:57

Christophe wrote:

Bonjour

1 int queSuisJe( int* Tablo, const int TailleTablo )
2 {
3 if ( TailleTablo == 1 )
4 return Tablo[0];
5 else
6 return Tablo[TailleTablo - 1] + queSuisJe( Tablo, TailleTablo - 1 );
7 }

Je ne comprends pas comment le Tablo[0] de la ligne 4 peut stocker le
résultat ?
Il ne stocke pas le résultat. Le résultat est transmit de fonctions en

fonction par le return.

Quelqu'un pourrait il m'éclairer ?

Peut être en prenant le problème à l'envers ?

Si TailleTablo == 1
On retourne Tablo[0]

Si TailleTablo == 2
On retourne Tablo[1] + queSuisJe(Tablo, 1), c'est à dire Tablo[0] +
Tablo[1]

Si TailleTablo == 3
On retourne Tablo[2] + queSuisJe(Tablo, 2), c'est à dire
Tablo[0]+Tablo[1]+Tablo[2]

Si TailleTablo == 4
On retourne Tablo[3] + queSuisJe(Tablo, 2), c'est à dire
Tablo[0]+Tablo[1]+Tablo[2]+Tablo[3]

....

Si TailleTablo == n
On retourne Tablo[n-1] + queSuisJe(Tablo, n-1), c'est à dire la somme
des n premiers éléments (numéroté de 0 à [n-1]) de Tablo.

--
Loïc

Christophe

13/12/2003 à 13:22

"Loïc Joly" a écrit dans le message de
news:brer3p$ard$

Christophe wrote:
Bonjour

1 int queSuisJe( int* Tablo, const int TailleTablo )
2 {
3 if ( TailleTablo == 1 )
4 return Tablo[0];
5 else
6 return Tablo[TailleTablo - 1] + queSuisJe( Tablo, TailleTablo -
1 );

7 }

Je ne comprends pas comment le Tablo[0] de la ligne 4 peut stocker le
résultat ?
Il ne stocke pas le résultat. Le résultat est transmit de fonctions en

fonction par le return.

Quelqu'un pourrait il m'éclairer ?

Peut être en prenant le problème à l'envers ?

Si TailleTablo == 1
On retourne Tablo[0]

Si TailleTablo == 2
On retourne Tablo[1] + queSuisJe(Tablo, 1), c'est à dire Tablo[0] +
Tablo[1]

Si TailleTablo == 3
On retourne Tablo[2] + queSuisJe(Tablo, 2), c'est à dire
Tablo[0]+Tablo[1]+Tablo[2]

Si TailleTablo == 4
On retourne Tablo[3] + queSuisJe(Tablo, 2), c'est à dire
Tablo[0]+Tablo[1]+Tablo[2]+Tablo[3]

....

Si TailleTablo == n
On retourne Tablo[n-1] + queSuisJe(Tablo, n-1), c'est à dire la somme
des n premiers éléments (numéroté de 0 à [n-1]) de Tablo.

--
Loïc

J'imagine que c'est le compilateur qui, voyant que la fonction est

récursive, va totalement modifier le code de manière à renvoyer non pas un
nombre, mais une somme de nombre. En fait c'est le compilateur qui va faire
un gros travail dès qu'il reconnait une fonction récursive.
Je me trompe ?

Christophe Cro-magon à la recherche de l'eau tiède.

Benoit Rousseau

13/12/2003 à 14:11

Christophe wrote:

"Loïc Joly" a écrit dans le message de
Bonjour

1 int queSuisJe( int* Tablo, const int TailleTablo )
2 {
3 if ( TailleTablo == 1 )
4 return Tablo[0];
5 else
6 return Tablo[TailleTablo - 1] + queSuisJe( Tablo, TailleTablo - 1 );
7 }

Peut être en prenant le problème à l'envers ?

Si TailleTablo == 1
On retourne Tablo[0]

Si TailleTablo == n
On retourne Tablo[n-1] + queSuisJe(Tablo, n-1), c'est à dire la somme
des n premiers éléments (numéroté de 0 à [n-1]) de Tablo.

--
Loïc

J'imagine que c'est le compilateur qui, voyant que la fonction est
récursive, va totalement modifier le code de manière à renvoyer non pas un
nombre, mais une somme de nombre. En fait c'est le compilateur qui va faire
un gros travail dès qu'il reconnait une fonction récursive.
Je me trompe ?
Oui :-)

Le compilateur n'a pas grand chose à faire... Il va se contenter
d'appeler successivement la fonction queSuisJe avec les paramètres donnés.
C'est par contre la pile mémoire peut prendre un sacré coup si tu ne
fais pas attention... Si tu utilise une grande valeur pour Taille, il
faudra ajouter à la pile tous les appels de la fonction (Voir un peu le
comportement des appels de fonctions en assembleur sur internet pour
bien comprendre).

La fonction sera surement traduite comme ça :

comparer (t != 0)
si non egal, aller à l'etiquette etiq_if
x = Tablo[t-1]
appel queJeSuis( Tablo, t-1 )
x += valeur de retour
retourner x

etiq_if :
retourner Tablo[ 0 ]

Je n'aime toujours pas ton code parcequ'il ne prend pas en compte un
tableau de taille 0...

--------------------------------------------
Benoît Rousseau : roussebe at spray dot se
Jouez en programmant : http://realtimebattle.sourceforge.net/

Pierre Maurette

13/12/2003 à 17:53

"Christophe" a écrit
[...]

J'imagine que c'est le compilateur qui, voyant que la fonction est
récursive, va totalement modifier le code de manière à renvoyer non pas un
nombre, mais une somme de nombre. En fait c'est le compilateur qui va
faire

un gros travail dès qu'il reconnait une fonction récursive.
Je me trompe ?
Oui, je le crains. Mais c'est presque normal dans un premier temps.

J'ai modifié votre programme (voir en fin de message). Si vous en
interprétez la sortie, vous aurez fait un pas en avant.
La récursivité n'existe pas dans le langage. Une fonction est dite récursive
si elle s'appelle elle-même. C'est tout.
Le notion connue du langage est plutôt la réentrance : une fonction qui
n'est pas terminée, c'est à dire qui n'a pas atteint son return, doit
pouvoir être appelée à nouveau. Ceci se produira par exemple si elle
s'appelle elle-même, si elle appelle une autre fonction qui elle même
l'appelle, si elle est appelée par une routine de traitement d'interruption,
etc.
La difficulté, c'est que pour que ça fonctionne, il faut qu'au retour, elle
retrouve en l'état ses variables locales. Chaque "instance" (le mot est mal
choisi !) en possède donc un jeu propre.
Un point très important pour la compréhension : les paramètres passés à une
fonction ne sont rien d'autre que des variables locales initialisées par
l'appelant (on oublie ici les paramètres référence).
A chaque appel d'une fonction pour lequel le return n'a pas été atteint
correspond donc "quelque part" un groupe de variables locales toujours
"vivantes".

Le reste est question d'implémentation. Comprendre physiquement comment ça
se passe en aider certains (c'est mon cas) et en confuser d'autres. Sur x86
(et sans doute beaucoup d'autres hards), c'est une gestion particulière de
la pile qui est mise en oeuvre. Pour plus de renseignements, vous pouvez
Googliser sur la base de "cadre de pile", "stack frame"

Christophe Cro-magon à la recherche de l'eau tiède.
Très bonne démarche.

Homo sapiens sapiens en vue.
Tout en gardant j'espère un je ne sais quoi du cousin erectus, pour la plus
grande joie de madame ;-)
Pierre

Pour tester :

int queSuisJe( int Tablo[], const int TailleTablo )
{
static int NbreAppels = 0;
++NbreAppels;
std::cout << "Débutt" << NbreAppels << "t" << TailleTablo <<std::endl;
if ( TailleTablo == 1 )
{
std::cout << " ift" << NbreAppels << "t" << TailleTablo << "t" <<
Tablo[0] <<std::endl;
return Tablo[0];
}
else
{
int dummy = Tablo[TailleTablo - 1] + queSuisJe( Tablo, TailleTablo -
1 );
std::cout << "elset" << NbreAppels << "t" << TailleTablo << "t" <<
dummy <<std::endl;
return dummy;
}
}

"Christophe" <chrschneider@free.fr> a écrit
[...]

J'imagine que c'est le compilateur qui, voyant que la fonction est
récursive, va totalement modifier le code de manière à renvoyer non pas un
nombre, mais une somme de nombre. En fait c'est le compilateur qui va
faire

un gros travail dès qu'il reconnait une fonction récursive.
Je me trompe ?
Oui, je le crains. Mais c'est presque normal dans un premier temps.

J'ai modifié votre programme (voir en fin de message). Si vous en
interprétez la sortie, vous aurez fait un pas en avant.
La récursivité n'existe pas dans le langage. Une fonction est dite récursive
si elle s'appelle elle-même. C'est tout.
Le notion connue du langage est plutôt la réentrance : une fonction qui
n'est pas terminée, c'est à dire qui n'a pas atteint son return, doit
pouvoir être appelée à nouveau. Ceci se produira par exemple si elle
s'appelle elle-même, si elle appelle une autre fonction qui elle même
l'appelle, si elle est appelée par une routine de traitement d'interruption,
etc.
La difficulté, c'est que pour que ça fonctionne, il faut qu'au retour, elle
retrouve en l'état ses variables locales. Chaque "instance" (le mot est mal
choisi !) en possède donc un jeu propre.
Un point très important pour la compréhension : les paramètres passés à une
fonction ne sont rien d'autre que des variables locales initialisées par
l'appelant (on oublie ici les paramètres référence).
A chaque appel d'une fonction pour lequel le return n'a pas été atteint
correspond donc "quelque part" un groupe de variables locales toujours
"vivantes".

Le reste est question d'implémentation. Comprendre physiquement comment ça
se passe en aider certains (c'est mon cas) et en confuser d'autres. Sur x86
(et sans doute beaucoup d'autres hards), c'est une gestion particulière de
la pile qui est mise en oeuvre. Pour plus de renseignements, vous pouvez
Googliser sur la base de "cadre de pile", "stack frame"

Christophe Cro-magon à la recherche de l'eau tiède.
Très bonne démarche.

Homo sapiens sapiens en vue.
Tout en gardant j'espère un je ne sais quoi du cousin erectus, pour la plus
grande joie de madame ;-)
Pierre

Pour tester :

int queSuisJe( int Tablo[], const int TailleTablo )
{
static int NbreAppels = 0;
++NbreAppels;
std::cout << "Débutt" << NbreAppels << "t" << TailleTablo <<std::endl;
if ( TailleTablo == 1 )
{
std::cout << " ift" << NbreAppels << "t" << TailleTablo << "t" <<
Tablo[0] <<std::endl;
return Tablo[0];
}
else
{
int dummy = Tablo[TailleTablo - 1] + queSuisJe( Tablo, TailleTablo -
1 );
std::cout << "elset" << NbreAppels << "t" << TailleTablo << "t" <<
dummy <<std::endl;
return dummy;
}
}

Vous avez filtré cet utilisateur ! Consultez son message

"Christophe" a écrit
[...]

J'imagine que c'est le compilateur qui, voyant que la fonction est
récursive, va totalement modifier le code de manière à renvoyer non pas un
nombre, mais une somme de nombre. En fait c'est le compilateur qui va
faire

un gros travail dès qu'il reconnait une fonction récursive.
Je me trompe ?
Oui, je le crains. Mais c'est presque normal dans un premier temps.

J'ai modifié votre programme (voir en fin de message). Si vous en
interprétez la sortie, vous aurez fait un pas en avant.
La récursivité n'existe pas dans le langage. Une fonction est dite récursive
si elle s'appelle elle-même. C'est tout.
Le notion connue du langage est plutôt la réentrance : une fonction qui
n'est pas terminée, c'est à dire qui n'a pas atteint son return, doit
pouvoir être appelée à nouveau. Ceci se produira par exemple si elle
s'appelle elle-même, si elle appelle une autre fonction qui elle même
l'appelle, si elle est appelée par une routine de traitement d'interruption,
etc.
La difficulté, c'est que pour que ça fonctionne, il faut qu'au retour, elle
retrouve en l'état ses variables locales. Chaque "instance" (le mot est mal
choisi !) en possède donc un jeu propre.
Un point très important pour la compréhension : les paramètres passés à une
fonction ne sont rien d'autre que des variables locales initialisées par
l'appelant (on oublie ici les paramètres référence).
A chaque appel d'une fonction pour lequel le return n'a pas été atteint
correspond donc "quelque part" un groupe de variables locales toujours
"vivantes".

Le reste est question d'implémentation. Comprendre physiquement comment ça
se passe en aider certains (c'est mon cas) et en confuser d'autres. Sur x86
(et sans doute beaucoup d'autres hards), c'est une gestion particulière de
la pile qui est mise en oeuvre. Pour plus de renseignements, vous pouvez
Googliser sur la base de "cadre de pile", "stack frame"

Christophe Cro-magon à la recherche de l'eau tiède.
Très bonne démarche.

Homo sapiens sapiens en vue.
Tout en gardant j'espère un je ne sais quoi du cousin erectus, pour la plus
grande joie de madame ;-)
Pierre

Pour tester :

int queSuisJe( int Tablo[], const int TailleTablo )
{
static int NbreAppels = 0;
++NbreAppels;
std::cout << "Débutt" << NbreAppels << "t" << TailleTablo <<std::endl;
if ( TailleTablo == 1 )
{
std::cout << " ift" << NbreAppels << "t" << TailleTablo << "t" <<
Tablo[0] <<std::endl;
return Tablo[0];
}
else
{
int dummy = Tablo[TailleTablo - 1] + queSuisJe( Tablo, TailleTablo -
1 );
std::cout << "elset" << NbreAppels << "t" << TailleTablo << "t" <<
dummy <<std::endl;
return dummy;
}
}

M. B.

13/12/2003 à 18:42

"Pierre Maurette" <mmaauurreettttttee.ppiieerrrree@@ffrreeee.ffrr> a écrit
dans le message de news: 3fdb441e$0$24047$

Le reste est question d'implémentation. Comprendre physiquement comment ça
se passe en aider certains (c'est mon cas) et en confuser d'autres. Sur
x86

(et sans doute beaucoup d'autres hards), c'est une gestion particulière de
la pile qui est mise en oeuvre. Pour plus de renseignements, vous pouvez
Googliser sur la base de "cadre de pile", "stack frame"

Pourquoi une gestion "particuliere" ?

Qu'a-t-elle de particuliere ?

Que font les architectures qui n'utilisent pas de pile dans
ce cas ?

MB

Pierre Maurette

13/12/2003 à 18:50

"M. B." a écrit ...

"Pierre Maurette" <mmaauurreettttttee.ppiieerrrree@@ffrreeee.ffrr> a écrit
dans le message de news: 3fdb441e$0$24047$

Le reste est question d'implémentation. Comprendre physiquement comment
ça

se passe en aider certains (c'est mon cas) et en confuser d'autres. Sur
x86

(et sans doute beaucoup d'autres hards), c'est une gestion particulière
de

la pile qui est mise en oeuvre. Pour plus de renseignements, vous pouvez
Googliser sur la base de "cadre de pile", "stack frame"

Pourquoi une gestion "particuliere" ?
Qu'a-t-elle de particuliere ?
Je faisais allusion à la notion de stack frame, au transfert ESP dans EBP,

aux instructions spécifiques ENTER et LEAVE, toutes choses spécifique à
IA32, mais dont un équivalent existe chez Motorola et autres.

Que font les architectures qui n'utilisent pas de pile dans
ce cas ?
Je l'ignore, j'imagine que de toute façons, une pile de données est gérée

par le programme.
Connaissant surtout l'architecture IA32, je suis en général prudent sur ce
groupe, précisant quand quelque chose est spécifique, non portable, et
laissant la porte ouverte à toute implémentation.
Cordialement,
Pierre

Christophe

14/12/2003 à 10:14

"Pierre Maurette" a écrit > [...]

Un point très important pour la compréhension : les paramètres passés à
une

fonction ne sont rien d'autre que des variables locales initialisées par
l'appelant (on oublie ici les paramètres référence).
A chaque appel d'une fonction pour lequel le return n'a pas été atteint
correspond donc "quelque part" un groupe de variables locales toujours
"vivantes".

Donc pour 10 appels récursifs successifs d'une fonction le prog empilera les
10 adresses de
retour et stockera 10 'variables' représentant le résultat de chaque appel.

Bon, je vais faire quelques exercices, ça clairifiera peut être.
Et puis, je reverrais plus tard, prochain chapître : les pointeurs.
Merci à tous
Christophe

James Kanze

14/12/2003 à 13:41

"Pierre Maurette" <mmaauurreettttttee.ppiieerrrree@@ffrreeee.ffrr> writes:

|> "Christophe" a écrit
|> [...]
|> > J'imagine que c'est le compilateur qui, voyant que la fonction est
|> > récursive, va totalement modifier le code de manière à
|> > renvoyer non pas un nombre, mais une somme de nombre. En fait
|> > c'est le compilateur qui va faire un gros travail dès qu'il
|> > reconnait une fonction récursive. Je me trompe ?

|> Oui, je le crains.

Je ne crois pas. La plupart des compilateurs C++ que je connais traitent
un appel récursif exactement comme n'importe autre appel de fonction.

|> Mais c'est presque normal dans un premier temps. J'ai modifié
|> votre programme (voir en fin de message). Si vous en interprétez
|> la sortie, vous aurez fait un pas en avant.

|> La récursivité n'existe pas dans le langage.

Je ne suis pas sûr ce que tu essaies à dire. Le C et le C++
garantissent que les appels récursifs (directs ou indirects)
fonctionnent, dans la mesure qu'on n'épuise pas les ressources
système (pile). Je ne sais pas ce que tu veux de plus -- Lisp (un
langage récursif par excellence) n'en dit pas plus.

En revanche, l'utilisation de la récursion grauitement n'est pas un
idiome classique de C++, et le langage offre de nombreux autres
constructions comme les boucles. Une solution comme celle proposée ne
serait pas considérée une bonne solution C++, tandis que c'est la
solution classique en Lisp (bien que des Lisp modernes offrent des
boucles aussi, je crois). Du coup, les compilateurs C++ n'optimisent pas
trop pour la récursion, tandis que c'est à peu près la
première optimisation que fait un compilateur Lisp.

--
James Kanze mailto:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France +33 1 41 89 80 93

Jean-Marc Bourguet

14/12/2003 à 19:52

"M. B." writes:

[récursivité]

Que font les architectures qui n'utilisent pas de pile dans ce cas ?

Dès qu'on veut gérer la récursivité, il faut utiliser une pile. Soit
avec l'aide du processeur, soit sans. Celle pile peut être soit
contigüe soit non-contigüe mais ça ne m'étonnerait pas que les 4 cas
aient existé.

Ca ne m'étonnerait d'ailleurs pas non plus qu'il y ait toujours des
processeurs qui n'ait pas de pointeur de pile forcé par le processeur
mais simplement par des conventions. Ce qui m'étonnerait c'est qu'il
y ait des processeurs d'architecture récente posant des difficultés à
l'utilisation de la récursivité (dans celle dont je me souviens,
l'instruction d'appel à une routine sauvait la valeur de retour dans
le premier mot de la routine -- avec une telle architecture, une
routine récursive commence par sauver sa valeur de retour dans la pile
qu'elle gère très explicitement).

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Pierre Maurette

14/12/2003 à 21:53

"James Kanze" a écrit

"Pierre Maurette" <mmaauurreettttttee.ppiieerrrree@@ffrreeee.ffrr> writes:

|> "Christophe" a écrit
|> [...]
|> > J'imagine que c'est le compilateur qui, voyant que la fonction est
|> > récursive, va totalement modifier le code de manière à
|> > renvoyer non pas un nombre, mais une somme de nombre. En fait
|> > c'est le compilateur qui va faire un gros travail dès qu'il
|> > reconnait une fonction récursive. Je me trompe ?

|> Oui, je le crains.

Je ne crois pas. La plupart des compilateurs C++ que je connais traitent
un appel récursif exactement comme n'importe autre appel de fonction.
C'est exactement ce que j'ai écrit : Christophe demande s'il se trompe en

pensant que le compilateur "voyant que la fonction est récursive...etc.". Je
lui réponds que oui, je pense qu'il se trompe ("crains" est un euphémisme).
S'il se trompe, c'est donc que le compilateur ne fait pas ce qu'il pense.
Et je précise que :
"La récursivité n'existe pas dans le langage. Une fonction est dite
récursive si elle s'appelle elle-même. C'est tout."

Je ne suis pas sûr ce que tu essaies à dire. Le C et le C++
garantissent que les appels récursifs (directs ou indirects)
fonctionnent, dans la mesure qu'on n'épuise pas les ressources
système (pile). Je ne sais pas ce que tu veux de plus -- Lisp (un
langage récursif par excellence) n'en dit pas plus.
Pas vu cette garantie dans les normes C99 et C++98, en tous cas aucune

allusion à la pile sur ce sujet.
Je vais essayer d'expliquer, mais je n'ai jamais fait d'études
d'informatique, donc le vocabulaire est peut-être approximatif.
Une fonction F() est dite récursive si elle contient un appel récursif
direct ou indirect. Un appel récursif est un appel de fonction F1() qui
conduit la fonction F() à être appelée avant que F1() ne retourne. F1() peut
être F(), c'est alors de la récursivité directe.
En cherchant sur le mot lui-même, il est simplement dit que l'appel récursif
est autorisé pour l'ensemble des fonctions, sauf main() pour laquelle il est
justement refusé à la compilation.
[norme C++]
5.2.2 Function call
...
9 Recursive calls are permitted, except to the function named main ...:

[norme C]
6.5.2.2 Function calls
Constraints
...
11 Recursive function calls shall be permitted, both directly and indirectly
through any chain of other functions.

Les normes considèrent que le lecteur sait ce qu'est un appel récursif et
quelles sont les conditions minimales pour qu'il puisse être fonctionnel
(les autres conditions sont dans l'algo et le codage). Ces conditions sont
la réentrance des fonctions. Qu'est-ce ?
Chaque appel d'une fonction provoque la création d'un jeu tout neuf de
variables locales (ou automatiques, etc.). Parmi ces variables locales, les
paramètres passés à la fonction, ou des variables locales initialisées par
ces paramètres, question de vocabulaire. Imaginons que le déroulement de la
fonction soit interrompu par une interruption (signal) ou un appel de
fonction (pouvant être la fonction elle-même). Le programme est réentrant si
au retour de cet évènement, les variables locales sont inchangées et la
fonction peut donc continuer son travail, et ceci même si la fonction a été
appelée "pendant ce temps". Ceci couvre le cas où la fonction s'est
simplement appelée elle-même (et ainsi de suite parfois). La même fonction
appelée par plusieurs threads doit également être réentrante. Les normes
garantissent effectivement cette réentrance, mais sans faire de référence
très explicite à la récursivité. Les fonctions des bibliothèques standard ne
sont pas (ou ne sont pas toutes, ou ne sont pas garanties) réentrantes.
[norme C++]
1.9 Program execution
(voir paragraphes 9 & 10)

[norme C]
5.2.3 Signals and interrupts
1 Functions shall be implemented such that they may be interrupted at any
time by a signal, or may be called by a signal handler, or both, with no
alteration to earlier, but still active, invocations' control flow (after
the interruption), function return values, or objects with automatic storage
duration. All such objects shall be maintained outside the function image
(the instructions that compose the executable representation of a function)
on a per-invocation basis.

Les variables statiques ne sont bien entendu pas concernées par cette
réentrance, mais elles peuvent être utilisées pour ce qu'elles sont. Une
variable de ce type est par essence volatile. Enfin, j'en sais trop rien,
faudrait revoir la définition exacte de la volatilité ...
La présence d'une variable statique dans le code d'une fonction récursive
est parfois le signe d'une mauvaise compréhension, d'un refus du concept de
récursivité de la part du programmeur.
Quid de la pile ? Pour moi, il y a deux types de pile. Tout d'abord, le
concept d'appels emboités, la pile d'appel (la commande stack du debugger
SoftIce donne un exemple) :
main()
f1()
f2()
f3()
quand le code est dans f4().
Pour ce qui est de l'éventuelle pile physique du microprocesseur, la
représentation POURRAIT être :
bloc main()
bloc f1()
bloc f2()
bloc f3()
bloc f4()
Un bloc regroupe variables locales (dont paramètres), adresse de retour,
sauvegarde de certains registres comme EBP par exemple.

En revanche, l'utilisation de la récursion grauitement n'est pas un
idiome classique de C++, et le langage offre de nombreux autres
constructions comme les boucles.
Certainement. le calcul d'une factorielle par récursion est calamiteux en

termes de performances. Et pourtant ...
J'ai une solution récursive que je trouve indispensable qui me vient à
l'esprit, c'est le parcours de l'ensemble des fichiers d'un disque. Ça vient
certaineement du fait que sous Windows, quand on parcourt un répertoire, on
ne sait pas si on va ramener un fichier ou un répertoire. Idem pour beaucoup
de structures arborescentes.

Une solution comme celle proposée ne
serait pas considérée une bonne solution C++,
Certes, mais ce que fait Christophe est certainement une façon de faire un

grand pas dans la compréhension du fonctionnement des .. fonctions.

Cordialement,
Pierre

"James Kanze" <kanze@alex.gabi-soft.fr> a écrit

"Pierre Maurette" <mmaauurreettttttee.ppiieerrrree@@ffrreeee.ffrr> writes:

|> "Christophe" <chrschneider@free.fr> a écrit
|> [...]
|> > J'imagine que c'est le compilateur qui, voyant que la fonction est
|> > récursive, va totalement modifier le code de manière à
|> > renvoyer non pas un nombre, mais une somme de nombre. En fait
|> > c'est le compilateur qui va faire un gros travail dès qu'il
|> > reconnait une fonction récursive. Je me trompe ?

|> Oui, je le crains.

Je ne crois pas. La plupart des compilateurs C++ que je connais traitent
un appel récursif exactement comme n'importe autre appel de fonction.
C'est exactement ce que j'ai écrit : Christophe demande s'il se trompe en

pensant que le compilateur "voyant que la fonction est récursive...etc.". Je
lui réponds que oui, je pense qu'il se trompe ("crains" est un euphémisme).
S'il se trompe, c'est donc que le compilateur ne fait pas ce qu'il pense.
Et je précise que :
"La récursivité n'existe pas dans le langage. Une fonction est dite
récursive si elle s'appelle elle-même. C'est tout."

Je ne suis pas sûr ce que tu essaies à dire. Le C et le C++
garantissent que les appels récursifs (directs ou indirects)
fonctionnent, dans la mesure qu'on n'épuise pas les ressources
système (pile). Je ne sais pas ce que tu veux de plus -- Lisp (un
langage récursif par excellence) n'en dit pas plus.
Pas vu cette garantie dans les normes C99 et C++98, en tous cas aucune

allusion à la pile sur ce sujet.
Je vais essayer d'expliquer, mais je n'ai jamais fait d'études
d'informatique, donc le vocabulaire est peut-être approximatif.
Une fonction F() est dite récursive si elle contient un appel récursif
direct ou indirect. Un appel récursif est un appel de fonction F1() qui
conduit la fonction F() à être appelée avant que F1() ne retourne. F1() peut
être F(), c'est alors de la récursivité directe.
En cherchant sur le mot lui-même, il est simplement dit que l'appel récursif
est autorisé pour l'ensemble des fonctions, sauf main() pour laquelle il est
justement refusé à la compilation.
[norme C++]
5.2.2 Function call
...
9 Recursive calls are permitted, except to the function named main ...:

[norme C]
6.5.2.2 Function calls
Constraints
...
11 Recursive function calls shall be permitted, both directly and indirectly
through any chain of other functions.

Les normes considèrent que le lecteur sait ce qu'est un appel récursif et
quelles sont les conditions minimales pour qu'il puisse être fonctionnel
(les autres conditions sont dans l'algo et le codage). Ces conditions sont
la réentrance des fonctions. Qu'est-ce ?
Chaque appel d'une fonction provoque la création d'un jeu tout neuf de
variables locales (ou automatiques, etc.). Parmi ces variables locales, les
paramètres passés à la fonction, ou des variables locales initialisées par
ces paramètres, question de vocabulaire. Imaginons que le déroulement de la
fonction soit interrompu par une interruption (signal) ou un appel de
fonction (pouvant être la fonction elle-même). Le programme est réentrant si
au retour de cet évènement, les variables locales sont inchangées et la
fonction peut donc continuer son travail, et ceci même si la fonction a été
appelée "pendant ce temps". Ceci couvre le cas où la fonction s'est
simplement appelée elle-même (et ainsi de suite parfois). La même fonction
appelée par plusieurs threads doit également être réentrante. Les normes
garantissent effectivement cette réentrance, mais sans faire de référence
très explicite à la récursivité. Les fonctions des bibliothèques standard ne
sont pas (ou ne sont pas toutes, ou ne sont pas garanties) réentrantes.
[norme C++]
1.9 Program execution
(voir paragraphes 9 & 10)

[norme C]
5.2.3 Signals and interrupts
1 Functions shall be implemented such that they may be interrupted at any
time by a signal, or may be called by a signal handler, or both, with no
alteration to earlier, but still active, invocations' control flow (after
the interruption), function return values, or objects with automatic storage
duration. All such objects shall be maintained outside the function image
(the instructions that compose the executable representation of a function)
on a per-invocation basis.

Les variables statiques ne sont bien entendu pas concernées par cette
réentrance, mais elles peuvent être utilisées pour ce qu'elles sont. Une
variable de ce type est par essence volatile. Enfin, j'en sais trop rien,
faudrait revoir la définition exacte de la volatilité ...
La présence d'une variable statique dans le code d'une fonction récursive
est parfois le signe d'une mauvaise compréhension, d'un refus du concept de
récursivité de la part du programmeur.
Quid de la pile ? Pour moi, il y a deux types de pile. Tout d'abord, le
concept d'appels emboités, la pile d'appel (la commande stack du debugger
SoftIce donne un exemple) :
main()
f1()
f2()
f3()
quand le code est dans f4().
Pour ce qui est de l'éventuelle pile physique du microprocesseur, la
représentation POURRAIT être :
bloc main()
bloc f1()
bloc f2()
bloc f3()
bloc f4()
Un bloc regroupe variables locales (dont paramètres), adresse de retour,
sauvegarde de certains registres comme EBP par exemple.

En revanche, l'utilisation de la récursion grauitement n'est pas un
idiome classique de C++, et le langage offre de nombreux autres
constructions comme les boucles.
Certainement. le calcul d'une factorielle par récursion est calamiteux en

termes de performances. Et pourtant ...
J'ai une solution récursive que je trouve indispensable qui me vient à
l'esprit, c'est le parcours de l'ensemble des fichiers d'un disque. Ça vient
certaineement du fait que sous Windows, quand on parcourt un répertoire, on
ne sait pas si on va ramener un fichier ou un répertoire. Idem pour beaucoup
de structures arborescentes.

Une solution comme celle proposée ne
serait pas considérée une bonne solution C++,
Certes, mais ce que fait Christophe est certainement une façon de faire un

grand pas dans la compréhension du fonctionnement des .. fonctions.

Cordialement,
Pierre

Vous avez filtré cet utilisateur ! Consultez son message

"James Kanze" a écrit

"Pierre Maurette" <mmaauurreettttttee.ppiieerrrree@@ffrreeee.ffrr> writes:

|> "Christophe" a écrit
|> [...]
|> > J'imagine que c'est le compilateur qui, voyant que la fonction est
|> > récursive, va totalement modifier le code de manière à
|> > renvoyer non pas un nombre, mais une somme de nombre. En fait
|> > c'est le compilateur qui va faire un gros travail dès qu'il
|> > reconnait une fonction récursive. Je me trompe ?

|> Oui, je le crains.

Je ne crois pas. La plupart des compilateurs C++ que je connais traitent
un appel récursif exactement comme n'importe autre appel de fonction.
C'est exactement ce que j'ai écrit : Christophe demande s'il se trompe en

pensant que le compilateur "voyant que la fonction est récursive...etc.". Je
lui réponds que oui, je pense qu'il se trompe ("crains" est un euphémisme).
S'il se trompe, c'est donc que le compilateur ne fait pas ce qu'il pense.
Et je précise que :
"La récursivité n'existe pas dans le langage. Une fonction est dite
récursive si elle s'appelle elle-même. C'est tout."

Je ne suis pas sûr ce que tu essaies à dire. Le C et le C++
garantissent que les appels récursifs (directs ou indirects)
fonctionnent, dans la mesure qu'on n'épuise pas les ressources
système (pile). Je ne sais pas ce que tu veux de plus -- Lisp (un
langage récursif par excellence) n'en dit pas plus.
Pas vu cette garantie dans les normes C99 et C++98, en tous cas aucune

allusion à la pile sur ce sujet.
Je vais essayer d'expliquer, mais je n'ai jamais fait d'études
d'informatique, donc le vocabulaire est peut-être approximatif.
Une fonction F() est dite récursive si elle contient un appel récursif
direct ou indirect. Un appel récursif est un appel de fonction F1() qui
conduit la fonction F() à être appelée avant que F1() ne retourne. F1() peut
être F(), c'est alors de la récursivité directe.
En cherchant sur le mot lui-même, il est simplement dit que l'appel récursif
est autorisé pour l'ensemble des fonctions, sauf main() pour laquelle il est
justement refusé à la compilation.
[norme C++]
5.2.2 Function call
...
9 Recursive calls are permitted, except to the function named main ...:

[norme C]
6.5.2.2 Function calls
Constraints
...
11 Recursive function calls shall be permitted, both directly and indirectly
through any chain of other functions.

Les normes considèrent que le lecteur sait ce qu'est un appel récursif et
quelles sont les conditions minimales pour qu'il puisse être fonctionnel
(les autres conditions sont dans l'algo et le codage). Ces conditions sont
la réentrance des fonctions. Qu'est-ce ?
Chaque appel d'une fonction provoque la création d'un jeu tout neuf de
variables locales (ou automatiques, etc.). Parmi ces variables locales, les
paramètres passés à la fonction, ou des variables locales initialisées par
ces paramètres, question de vocabulaire. Imaginons que le déroulement de la
fonction soit interrompu par une interruption (signal) ou un appel de
fonction (pouvant être la fonction elle-même). Le programme est réentrant si
au retour de cet évènement, les variables locales sont inchangées et la
fonction peut donc continuer son travail, et ceci même si la fonction a été
appelée "pendant ce temps". Ceci couvre le cas où la fonction s'est
simplement appelée elle-même (et ainsi de suite parfois). La même fonction
appelée par plusieurs threads doit également être réentrante. Les normes
garantissent effectivement cette réentrance, mais sans faire de référence
très explicite à la récursivité. Les fonctions des bibliothèques standard ne
sont pas (ou ne sont pas toutes, ou ne sont pas garanties) réentrantes.
[norme C++]
1.9 Program execution
(voir paragraphes 9 & 10)

[norme C]
5.2.3 Signals and interrupts
1 Functions shall be implemented such that they may be interrupted at any
time by a signal, or may be called by a signal handler, or both, with no
alteration to earlier, but still active, invocations' control flow (after
the interruption), function return values, or objects with automatic storage
duration. All such objects shall be maintained outside the function image
(the instructions that compose the executable representation of a function)
on a per-invocation basis.

Les variables statiques ne sont bien entendu pas concernées par cette
réentrance, mais elles peuvent être utilisées pour ce qu'elles sont. Une
variable de ce type est par essence volatile. Enfin, j'en sais trop rien,
faudrait revoir la définition exacte de la volatilité ...
La présence d'une variable statique dans le code d'une fonction récursive
est parfois le signe d'une mauvaise compréhension, d'un refus du concept de
récursivité de la part du programmeur.
Quid de la pile ? Pour moi, il y a deux types de pile. Tout d'abord, le
concept d'appels emboités, la pile d'appel (la commande stack du debugger
SoftIce donne un exemple) :
main()
f1()
f2()
f3()
quand le code est dans f4().
Pour ce qui est de l'éventuelle pile physique du microprocesseur, la
représentation POURRAIT être :
bloc main()
bloc f1()
bloc f2()
bloc f3()
bloc f4()
Un bloc regroupe variables locales (dont paramètres), adresse de retour,
sauvegarde de certains registres comme EBP par exemple.

En revanche, l'utilisation de la récursion grauitement n'est pas un
idiome classique de C++, et le langage offre de nombreux autres
constructions comme les boucles.
Certainement. le calcul d'une factorielle par récursion est calamiteux en

termes de performances. Et pourtant ...
J'ai une solution récursive que je trouve indispensable qui me vient à
l'esprit, c'est le parcours de l'ensemble des fichiers d'un disque. Ça vient
certaineement du fait que sous Windows, quand on parcourt un répertoire, on
ne sait pas si on va ramener un fichier ou un répertoire. Idem pour beaucoup
de structures arborescentes.

Une solution comme celle proposée ne
serait pas considérée une bonne solution C++,
Certes, mais ce que fait Christophe est certainement une façon de faire un

grand pas dans la compréhension du fonctionnement des .. fonctions.

Cordialement,
Pierre

miracle de la récursion

10 réponses

Veuillez sélectionner un problème