(je suis débutant en c) je ne vois d'instruction pour boucler

bpascal123@googlemail.com a écrit :

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.

bpascal123@googlemail.com a écrit :

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.

Plutot que de faire plus complique, on va faire plus simple.

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;
}

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

candide a écrit :

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

On 28 nov, 13:55, candide <cand...@free.invalid> wrote:

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

bpascal123@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.

In article <5e66131a-fa08-4ef4-ad52-7f86e8ca0db1@d10g2000yqh.googlegroups.com>,
bpascal123@googlemail.com <bpascal123@googlemail.com> wrote:

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.

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("%dn", (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 !

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

Wykaaa <wykaaa@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...

--
Le travail n'est pas une bonne chose. Si ça l'était,
les riches l'auraient accaparé