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

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : [C] quelle est la profondeur de recursion maximale ??

olib

keep smiling !

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

Publicité

LeGreg

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

Ace17

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?

pascal_

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 :

void affTab( int tab[], int i){
if( i < TAILLE_MAX ){
printf( "%d\n", tab[i] );
affTab( tab, i+1 ); // <= terminal
}
}
int facto( int n ){
if( n == 0 ){
return 1;
}else{
return n * facto( n-1 ); // <= pas terminal. La dernière opération
// à réaliser est la multiplication
}
}

Ace17

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?

Taz

bisounours-codeur

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.

Taz

bisounours-codeur

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

christophe_d13

L'efficacité à tout prix.

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

Taz

bisounours-codeur

christophe_d13 a écrit :

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

c'est quoi alors la solution pour ackerman ?

christophe_d13

L'efficacité à tout prix.

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

Code :

ack(m, n)
| reponse <- 0
| soit p une pile
| push(p, (m, n))
| Tant-que p n'est pas vide
| | (m, n) <- pop(p)
| | Si m=0
| | | reponse <- n+1
| | | Si p n'est pas vide
| | | | (m, n) <- pop(p)
| | | | push(p, (m, reponse))
| | | | reponse <- n
| | | Fin-si
| | Sinon si n=0
| | | push(p, (m-1, 1))
| | Sinon
| | | push(p, (m-1, reponse))
| | | push(p, (m, n-1))
| | Fin-Si
| FinTant-que
| Renvoie reponse
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

Publicité

Taz

bisounours-codeur

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

christophe_d13

L'efficacité à tout prix.

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.

Taz

bisounours-codeur

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

christophe_d13

L'efficacité à tout prix.

Taz> Tout à fait d'accord.

FORUM HardWare.fr

Programmation

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

Sujets relatifs
Arbre binaire, trouver la profondeur d une node.	recursion, je ne comprend pas cet algo
[défi de la semaine] objectif réutilisation maximale	Largeur maximale
iteration --> recursion aide algo simple	[C++ OPENGL] Affichage de cubes superposés et tampon de profondeur
[YACC] Problème de récursion à droite	[HTML] tableau de taille maximale pour un forum
[JAVA] comment donner une taille maximale a un textfield?	[XML] Récuperer la valeur maximale contenue dans une balise
Plus de sujets relatifs à : [C] quelle est la profondeur de recursion maximale ??

Page générée en 0.060 secondes