Hello everybody, j'aimerais savoir quel est la limite de la pile ( si c'est bien une pile ) lorsque l'on utilise une fonction récursive.
 
Merci, A+

La taille de la pile est un des paramètres du compilateur (enfin plus précisément du linker).
Et donc à priori tu peux mettre ce que tu veux.

Ok merci !

A noter que certains optimisers sont capable de dé-récursifier du code (si il y a une solution simple). Le watcom y arrive (un peu).

a la main ca marche aussi ... la derecu :=)

Globalement, la "dé-récursification" est facile si l'appel récursif est unique et terminal. Exemple (bateau), en Ada (pour se faire plaisir :

 
Ici, quel que soit le "chemin" pris par l'exécutant, il n'y a qu'un seul appel récursif, et c'est la dernière instruction exécutée. On peut alors transformer cela par une simple boucle.

 
Par contre, dès qu el'appel récursif n'est plus terminal, cela peut être plus compliqué. Pour dé-récursifier, il faut alors souvent passer par l'utilisation explicite d'une pile (au lieu de se reposer sur la pile du processeur). Et évidemment que il y a plusieurs appels récursifs (là un au moins des appels n'est pas terminal, forcément), ça devaient carrément obligatoire. Un des exemples les plus classiques c'est le tri rapide (quick-sort).

[edit]--Message édité par BifaceMcLeOD--[/edit]

Sauf que dans le code donné pour la factorielle, la récursivité n'est pas terminale car la valeur de retour n'est pas l'appel de la fonction mais un calcul appellant la fonction.

Heu.... oui, c'est vrai ça.    Verdoux, tu fais ch.... !    
 
     
 
Bon ben mon exemple n'était pas si bon que cela. Par contre, je peux vous trouver un exemple de fonction avec 2 appels récursifs. J'vous sers un p'tit coup de Fibo ? D
 
Verdoux> Si je réfléchis bien, le calcul de factoriel n'est jamais vraiment terminal, au sens algorithmique du terme. Je me trompe ?
De toute façon, ça ne contredit pas ce que je dis. Même inclus dans un calcul, l'appel récursif peut se dérécursifier par une simple boucle for, dès lors que c'est la dernière instruction du la fonction (c'est là que Verdoux me sort un contre-exemple, et là je me couvre de ridicule...   ).

On peut faire une factorielle en récursivité terminale:

 
Maintenant un compilo peut sans doute dérécursifier la factorielle donnée par Biface, mais j'ai pas vérifié. Faudrait jeter un coup d'oeil au code généré.

[edit]--Message édité par Verdoux--[/edit]

Ouais... Effectivement, il n'y a que de l'appel terminal, mais c'est un peu tordu à mon goût, le coup du wrapper pour un code aussi simple...
 
Quoique c'est vrai que ça doit être plus facile à dé-récursifier de manière automatique.  

En c++ on peut faire sans wrapper

Oui ben en Ada aussi alors...    

Vi... Très intéressant tout ca !!!!
Allez... Verdoux ou Mc Leod... Il ne peut en rester qu'un !!! D

Enfin tout ca pour dire que vous utilisez la recursivite la ou il faut justement pas l'utiliser... On se fout de garder sur le stack tout les valeurs de n...

Justement, avec le programme récursif classique de la factorielle, t'accumules sur la pile toutes les valeurs de n puisqu'à l'étape i, il y aura:
 n * ((n-1) * ((n-2) * ( ... ((n-i+1) * fact(n-i)) ... )))
Et cela ne sera évalué en totalité qu'à la fin.
 
Alors qu'en récurisvité terminale, la pile ne contient à chaque étape que les 2 entiers a et b.

Oui c'est une amelioration mais bon quand meme une boucle c bien aussi    

Pour la boucle, c'est pareil, non ? Tu gardes l'indice et le produit.

J'avais pas vu les choses comme ca ok c'est puissant la recu terminale alors

C'est pas que c'est puissant, c'est strictement équivalent à la méthode boucle et c'est pour ça que les compilos arrivent à dé-récursifier.
Maintenant tu codes comme tu veux. Dans certains cas, c'est plus lisible avec une boucle, et dans un autre c'est la forme récursive qui est plus éclairante.

[edit]--Message édité par Verdoux--[/edit]

Par puissant je voulais dire que c'est plus joli et plus mystique que la bete boucle...
Sauf avoir les defauts de la recursivite

Mystère> Bon, on va peut-être gommer le topique, là, parce que sinon, j'en connais qui risque de se mettre en boule...  

Euh... Attendez avant de le jeter à la poubelle ce topic ...
 
Jai une question.. Jai pas pigé le truc de la recu...
Car pour moi : f(a,b=1) ben....si tu l'appel avec f(1,2) le 2 devient 1, non ?

Ah ouai? il y a beaucoup de compilos qui arrivent a derecursifier? (a part celui de CAML?)  
(nb: c'est une vraie question..)
 
LEGREG

Dans f(a,b=1), a est un paramètre obligatoire, b est obtionnel avec une valeur par défaut de 1 s'il est omis.

Ah... oki oki
 
mci bcp mara'dad... Ca doit etre specifique au C++, non ?
Vous pouvez supprimer ce topic maintenant
Mais prenez votre temps...:D:D ...

En fait je suis pas certain pour le C++, j'ai vu çà en Java.
Mais surtout, je vois pas ce qu'une déclaration de fonction du genre
int fact(int a, int b = 1){ ...
pourrait vouloir dire d'autre !

C'est une valeur par defaut pour un parametre comme tu l'a dit...

En JAVA ??!!
Atend je teste de suite... Ca m'etonne... j'ai jamais vu ca moi... Serait-ce un moyen d'eviter la surcharge simple ??
Hmm... allez.. je teste D

Je croyais que c'était en Java, mais j'ai un doute là tout d'un coup ! (surcharge en effet).
Mais comme j'ai jamais fait de C...
Vérification faite, c'est en PHP que j'ai vu çà ;-)
Désolé...

J'ai regardé les 2 codes en assembleur générés par VC++ et GCC (avec optimisation activée).  
Je connais pas grand chose à l'assembleur, néanmoins le code pour la version non terminale de la factorielle contient un "call" vers la fonction alors que la version terminale, non.

[edit]--Message édité par Verdoux--[/edit]

"... Ca doit etre specifique au C++, non ? "
non :  
(VB) optional b as integer = 1
(ADA) b : integer := 1
 
je crois que c'est a peu pres ca ... par contre si qq'un pouvait me dire comment on fait en Pascal, j'avais pas trouvé

Sais pas si ca existe en pascal en tout cas moi j'ai jamais trouve non plus

A ma connaissance, donner une valeur par défaut à un paramètre de fonction n'est reconnu ni en Pascal, ni en Java. Ceci dit, peut-être que Borland a rajouté cette fonctionalité dans Delphi...
En Java, on peut le contourner en écrivant 2 fonctions avec le même nom, l'une des 2 appelant l'autre avec la valeur par défaut du paramètre en moins. Par contre, en Pascal, c'est impossible, car ce langage ne supporte pas la surcharge.
 
Par contre, comme l'a indiqué HelloWorld, la valeur par défaut de paramètre est possible en Ada, en Visual Basic et en C++.

[edit]--Message édité par BifaceMcLeOD--[/edit]

dites, j'ai implémenté un algo qui est basé sur une croissance de région. En gros, on passe à la fonction un pixel Pm (appelé graine), un seuil Tm (en niveau de gris, de 0 à 255), un pointeur sur l'image Tr sur laquelle je veux effectuer la croissance de région et un pointeur sur un tableau de pixels Set_G qui va récupérer tous les pixels voisins de Pm.NdG > Tm
Cette fonction est récursive, car si un voisin de Pm > Tm alors on cherche parmi les voisins du voisin des pixels > tm et ainsi de suite. L'ennui, c'est que rapidement, sur des images > 100*100, je me prend un stack overflow....
qq'un pourrait me dire si y'a un moyen d'éviter ça?
 
j'ai vu, on peut augmenter la pile, mais, y'a pas une autre solution, par ex, une fonction de croissance de région qui serait pas récurssive...

Tu peux toujours utiliser un stack et simuler la recursivite avec le stack et l'optimiser en ne mettant sur le stack que les valeurs dont tu as vraiment besoin (au retour de l'appel) et puis peut etre que tu peux trouver une fonction inverse que tu appellerais au retour de ta recu(sauf qu'il y en a plus) et cette fonction inverse te donnerait a partir dela valeur actuelle de tes variables les valeurs avant le pseudo appel.
Voila ce que je peux te dire... J'espere que je suis clair

 
non, pas très, en fait... mais le pb réside dans le fait que ma recherche est récursive. Je sais si c'est possible de l'éviter. Tu vois, je pars d'un pixel et la recherche va s'étendre tout autour de lui. La région va grossir de plus en plus.

Imaginons que tu as 100 variables ds ta fonction recursive en la rappellant tu vas tout savuer sur le stack systeme. Donc tu peux faire une fonction non recursive utilisant une boucle et un stack(interne a ta fonction) sur lequel tu ne sauves que tes varaibles dont tu auras besoin plus tard.
C'est plus clair maintenant?

Pas trop
En gros la boucle remplace la recursivite.
Ensuite il y a d'autres optimisations comme par exemple si a chaque fois que tu appelles ta fonction recursive tu appelle avec i+1... Peut etre que lors de l'equivalent du retour de ta recursivite (tu peux deviner la profondeur d'appel qui il y a eu et dire que i=i-6). Au lieu de stocker le i sur le stack voila ... si il faut je vais essayer de te montrer un exemple si tu veux

//RECURSIF
void exploiration(int i)
{
  if(i<16)
  {
    TARITEMENT
    exploration(i+1);
  }
}
 
main()
{
 exploration(1);
 return 1;
}
 
 
//NON RECURSIF AVEC STACK
void exploration(int i)
{
  while(stack.isEmpty())
  {
    while(i<16)
    {
      TRAITEMENT
      stack.push(i);
      i=i+1;
    }
    i=stack.pop();
  }
}
 
void exploration(int i)
{
  profondeur=0;
  do  
  {
    while(i<16)
    {
       TRAITEMENT
       profondeur++;
       i=i+1;
    }
    i--;
    profondeur--;
  }while(profondeur)
}
voila il y a surement des erreurs j'ai fait ca tres vite fait mais l'idee est la enfin je vais surement me faire descendre mais bon... j'ai l'habitude...

 
Ok, donc si j'ai bien compris, ton systeme d'extension est semblable a celui du démineurs quand on tombe sur une case a valeur 0. Dans ce cas, la dérécursification est très simple, j'ai du faire un tel truc en permière candi.
Si tu ne vois pas comment, tu peux aussi essayer de reconstruire completement un algo de manière non récursive dès le départ, c'est pas plus compliqué mais c'est une vue de l'iesprit qui convient mieux a cerains.