En Python, il existe une profondeur de récursivité maximale. On dirait que c'est parce que Python est un interpréteur, pas un compilateur. Est-ce que C++ a le même concept? Ou il est connecté uniquement avec la limite de RAM?Est-ce que C++ limite la profondeur de récursion?
La limite en C++ est due à la taille maximale de la pile. C'est généralement moins que la taille de la RAM de quelques ordres de grandeur, mais elle est encore assez grande. (Heureusement, les grandes choses comme la chaîne contenu sont typiquement maintenues pas sur la pile elle-même.)
La limite de pile est typiquement accordable au niveau d'OS. (Voir les documents pour le shell intégré ulimit si vous êtes sous Unix.) La valeur par défaut sur cette machine (OSX) est de 8 Mo.
[EDIT] Bien sûr, la taille de la pile ne suffit pas à elle seule pour déterminer la profondeur de recurcissement. Pour le savoir, vous devez calculer la taille de l'enregistrement d'activation (ou enregistrements) de la fonction récursive (également appelée une trame de pile). La façon la plus simple de le faire (que je connaisse) est d'utiliser un désassembleur (une caractéristique de la plupart des débogueurs) et de lire la taille des ajustements du pointeur de la pile au début et à la fin de chaque fonction. Ce qui est désordonné. (Vous pouvez le résoudre par d'autres moyens - par exemple, calculer la différence entre les pointeurs et les variables dans deux appels - mais ils sont encore plus méchants, surtout pour le code portable.) Lire les valeurs du démontage est plus facile.)
Je sais que j'aurais dû dire MiB pour les unités, mais cela signifie quelque chose d'entièrement à moi. Donc, je vais aller pour 67,1 mégabits à la place! –
Sur les machines Windows, vous pouvez A. gérer les conditions de débordement de la pile en toute sécurité et B. définir individuellement la profondeur de la pile par exécutable (option de l'éditeur de liens). Les machines Unix utilisent généralement des piles beaucoup plus profondes (8 Mo) que Windows (1 Mo) par défaut en raison de ces fonctionnalités. +1 –
Je pense qu'il existe des différences dans la manière dont les deux familles de systèmes d'exploitation gèrent la mémoire virtuelle dans ce domaine également. Les détails commencent à devenir plutôt triviaux. –
C++ a une profondeur de récurrence maximale limitée par la pile. Cependant, les systèmes d'exploitation modernes sont capables d'étendre dynamiquement une pile d'espace utilisateur à mesure qu'elle se remplit, limitant la profondeur de récursivité par l'espace mémoire et la fragmentation de la mémoire uniquement. Je crois que la limite est la taille de la pile disponible sur la plate-forme.
Hmm .. Je ne suis pas entièrement positif Unixen fournir cette fonctionnalité. Mais je pourrais avoir très très tort :) Il semble que 'boost :: regex' utiliserait ces fonctionnalités si elles étaient disponibles ... il les utilise sous Windows. –
L'expansion de pile dynamique semble intéressante. Avez-vous une référence? –
@Don Wakefield: http://support.microsoft.com/kb/315937 –
D'après ce que j'ai lu, c'est
8K
8Mo par défaut sur Linux, mais les noyaux modernes peuvent ajuster la taille de la pile dynamiquement.
8K est assez peu profond pour une pile. Je pensais que cela signifiait qu'il commence à 8K et se développe par pages. –
En fait, il est 8M par défaut :) –
En fait, pourrait être 8MB - l'article que j'ai lu n'était pas clair. –
Il n'y a pas de suivi de profondeur de récursivité ni de limite dans les normes C ou C++. Lors de l'exécution, la profondeur est limitée par la taille de la pile.
En fait, la limitation est une combinaison de la capacité d'adressage de la plate-forme, de la quantité de mémoire disponible pour le processus et des limitations définies par le compilateur. En général, les applications peuvent remplacer la pile et effectuer un comportement indéfini. –
En outre, toutes les limitations d'exécution de type «ulimit» ou, dans le cas de threads, les limites définies lors de la création du thread. Je ne suis pas sûr si, par "surcharger la pile", vous voulez dire "le définir à une taille que l'OS ne peut pas supporter (par exemple illimité) parce qu'une autre limite sera atteinte d'abord", ou "pousser trop sur la pile et dépasser la fin."Rien de tel que 256K de stockage automatique dans votre fonction récursive, dépassant un nombre insuffisant de pages de protection de pile" lecture seule "à la fin, et obtenant une erreur de segmentation ou une corruption de tas au lieu d'une erreur de lecture seule ... –
Non, C++ n'a pas de profondeur de récursivité explicite. Si la taille maximale de la pile est dépassée (1 Mo par défaut sous Windows), votre programme C++ débordera votre pile et l'exécution sera terminée.
Oui +1 De plus, il est important de noter que la terminaison est instantanée - semblable à l'appel de TerminateProcess.Nos fonctions d'arrêt de Nice de votre processus (par exemple DLL_PROCESS_DETACH, DLL_THREAD_DETACH, etc.) seront appelées –
Absolument - C'est l'une des façons les plus cruelles qu'un programme peut être terminé. –
Python a un tunable limit sur les appels récursifs, alors que C++ est limité par la taille de la pile. En outre, de nombreux langages ou compilateurs peuvent optimiser la récursion de queue en supprimant le cadre de pile de l'appelant afin qu'aucun espace de pile supplémentaire ne soit consommé. (En récursion queue, la seule chose que la fonction appelante fait est après avoir fait l'appel récursif est de retourner la valeur de retour appel récursif.)
int fact(int n, int accum=1){
if (n==0) return accum;
else return fact(n-1,n*accum); //tail recursion here.
}
Python n'optimise pas récursion de queue (mais stackless Python fait), et C++ ne pas besoin d'optimisation de la récursivité de la queue, mais je crois que gcc optimise la récursivité de la queue. La JVM n'optimise pas la récursion de queue, bien que le langage Scala le fasse dans certains cas documentés courants. Scheme et Lisp (et probablement d'autres langages fonctionnels aussi) nécessitent que la récursivité de la queue soit optimisée.
Je suppose que vous voulez dire une profondeur de récursivité * maximum *. (à quel point la récursivité est autorisée avant que vous ne rencontriez une erreur) – jalf
Je ne vois pas pourquoi être un interpréteur/compilateur aurait quelque chose à voir avec ça. Par exemple, Stackless Python est toujours un interpréteur, mais n'utilise pas la pile C pour ses cadres de pile et n'a donc pas le même problème, non? – Ken
notez qu'il existe des implémentations C++ et Python qui peuvent effectuer des éliminations d'appel de fin pour éviter d'atteindre les limites de la pile dans ces cas-là. –