[C] quelle est la profondeur de recursion maximale ??

quelle est la profondeur de recursion maximale ?? [C] - C - Programmation

Marsh Posté le 19-04-2004 à 03:39:23    


mon programme plante apres environ 70 000 appels recursifs.
 
je me demandais si il y avait une limite sur la profondeur de récursion et si oui, laquelle...
 
merciiiiiii
 

Reply

Marsh Posté le 19-04-2004 à 03:39:23   

Reply

Marsh Posté le 19-04-2004 à 03:42:22    

La taille de la pile, la quantité de mémoire disponible.
 
Quelle limite tu atteinds en premier dépends de ton systeme.
 
Sinon si tu programmais en Caml avec de la recursion terminale tu n'aurais pas ce probleme.
 
En regle general en C on essaie de limiter le nombre d'appels récursifs: La programmation itérative a exactement les memes "capacités" que la programmation récursive.
 
LeGreg

Reply

Marsh Posté le 19-04-2004 à 09:20:15    

LeGreg a écrit :

Sinon si tu programmais en Caml avec de la recursion terminale tu n'aurais pas ce probleme.


 
Qu'est-ce que c'est, la récursion terminale?

Reply

Marsh Posté le 19-04-2004 à 10:10:46    

Ace17 a écrit :


 
Qu'est-ce que c'est, la récursion terminale?


 
C'est quand l'appel de la récursion est la dernière instruction de la fonction.
 

Code :
  1. void affTab( int tab[], int i){
  2.   if( i < TAILLE_MAX ){
  3.     printf( "%d\n", tab[i] );
  4.     affTab( tab, i+1 ); // <= terminal
  5.   }
  6. }
  8. int facto( int n ){
  9.   if( n == 0 ){
  10.     return 1;
  11.   }else{
  12.     return n * facto( n-1 ); // <= pas terminal. La dernière opération
  13.                              // à réaliser est la multiplication
  14. }
  15. }


 

Reply

Marsh Posté le 20-04-2004 à 08:06:14    

Ok merci; Et pour mettre en relation avec ce qu'a dis LeGreg, ca veut donc dire qu'on peut libérer la pile au fur et a mesure?

Reply

Marsh Posté le 20-04-2004 à 08:10:55    

c'est pas possible. la récursion c'est bien dans une certaine mesure. mais pas ici. (surtout qu'avec 32bits, tu va pas plus loin que 17!)
 
dérécursifie, si tu n'arrives pas à passer ton algorithme en itératif, tu peux toujours ruser en utilisant toi même une pile d'arguments dans le tas.

Reply

Marsh Posté le 20-04-2004 à 08:13:48    

sinon pour avoir une telle profondeur, tu fais quoi ? t'es sur d'avoir rien foiré ou tu réinventes ackerman ?

Reply

Marsh Posté le 24-04-2004 à 12:00:19    

J'ai déjà fait de la dérécursivité pour parcourir l'arborescence d'un réseau local, de disque physique et de la paletisation. Tout ça car il y avait des problèmes avec VC++ et Windows.
Tous les algos sont dérécursivables...


Message édité par christophe_d13 le 24-04-2004 à 12:00:37
Reply

Marsh Posté le 24-04-2004 à 12:26:45    

christophe_d13 a écrit :

Tous les algos sont dérécursivables...

c'est quoi alors la solution pour ackerman ?

Reply

Marsh Posté le 24-04-2004 à 12:34:07    

Posté par JHelp sur un autre forum (developpez.com)

Code :
  1. ack(m, n)
  2. | reponse <- 0
  3. | soit p une pile
  4. | push(p, (m, n))
  5. | Tant-que p n'est pas vide
  6. |  | (m, n) <- pop(p)
  7. |  | Si m=0
  8. |  |  | reponse <- n+1
  9. |  |  | Si p n'est pas vide
  10. |  |  |  | (m, n) <- pop(p)
  11. |  |  |  | push(p, (m, reponse))
  12. |  |  |  | reponse <- n
  13. |  |  | Fin-si
  14. |  | Sinon si n=0
  15. |  |  | push(p, (m-1, 1))
  16. |  | Sinon
  17. |  |  | push(p, (m-1, reponse))
  18. |  |  | push(p, (m, n-1))
  19. |  | Fin-Si
  20. | FinTant-que
  21. | Renvoie reponse
  22. Fin


Ok, le code ne marche pas correctement.
Mais c'est la seule solution quand on ne pas faire de récursivité : Utiliser un stockage de type pile.


Message édité par christophe_d13 le 24-04-2004 à 12:36:42
Reply

Marsh Posté le 24-04-2004 à 12:34:07   

Reply

Marsh Posté le 24-04-2004 à 12:39:50    

oui ben voilà, avec une pile on fait tout, mais c'est la complètement équivalent avec la pile d'appel ...

Reply

Marsh Posté le 24-04-2004 à 12:43:54    

Taz> Tout à fait, mais dans ce cas, on maîtrise complètement la pile, donc sa taille. C'est pas l'os qui la gêre à notre place. C'était le problème de olib.
70000 appels récursifs... sachant qu'à chaque appel il a un stockage d'un grand nombre de données pas directement liées à l'algo.

Reply

Marsh Posté le 24-04-2004 à 12:45:00    

oui, et ça risque quand même de sérieusement poutrer niveau efficacité

Reply

Marsh Posté le 24-04-2004 à 12:48:15    

Taz> Tout à fait d'accord.

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed