[C++] La fonction récursive maximale appelle en C / C ++ avant que la pile ne soit pleine et donne un défaut de segmentation?


Answers

Il n'y a (AFAIK) aucune limite bien établie. (Je réponds du point de vue d'un bureau Linux).

Sur les ordinateurs de bureau, la taille de la pile par défaut est de quelques mégaoctets en 2015. Sur Linux, vous pouvez utiliser setrlimit (2) pour le changer (à un chiffre raisonnable, ne vous attendez pas à le mettre à un gigaoctet ces jours-ci) et vous pouvez utiliser getrlimit (2) ou parse /proc/self/limits (voir proc (5) ) pour l'interroger. Sur les microcontrôleurs intégrés - ou à l'intérieur du noyau Linux -, la pile entière peut être beaucoup plus limitée (jusqu'à quelques kilo-octets au total).

Lorsque vous créez un thread à l'aide de pthread_create (3), vous pouvez utiliser un pthread_attr_t explicite et utiliser pthread_attr_setstack (3) pour définir l'espace de la pile.

BTW, avec GCC récent, vous pouvez compiler tous vos logiciels ( y compris la bibliothèque C standard) avec des piles divisées (donc passer -fsplit-stack à gcc ou g++ )

Enfin, votre exemple est un appel de queue , et GCC pourrait optimiser cela (dans un saut avec des arguments). J'ai vérifié que si vous compilez avec g++ -O2 (en utilisant GCC 4.9.2 sous Linux / x86-64 / Debian) la récursion serait transformée en une véritable boucle et aucune allocation de pile ne croîtrait indéfiniment (votre programme s'exécute pour près de 40 millions d'appels dans de meilleures langues comme Scheme ou Ocaml, il y a une garantie que les appels de queue sont en effet compilés de manière itérative (alors l'appel récursif de queue devient le plus souvent -ou même le seul-bouclage).

CyberSpok est excessif dans son commentaire (suggérant d'éviter les récursions). Les récursions sont très utiles, mais vous devriez les limiter à une profondeur raisonnable (par exemple, quelques milliers), et vous devez veiller à ce que les trames d'appel sur la pile d'appels soient petites (moins d'un kilo-octet chacune). les données dans le tas C Les options GCC -fstack-usage sont vraiment utiles pour signaler l'utilisation de la pile de chaque fonction compilée. Voir ceci et cela réponses.

Notez que le style de passage continu est un moyen canonique de transformer des récursions en itérations (vous échangez ensuite des trames de pile avec des fermetures allouées dynamiquement).

Certains algorithmes intelligents remplacent une récursion par des itérations de modification de fantaisie, par exemple l' algorithme de marquage de graphes de Deutche-Shorr-Waite .

Question

Je faisais une question où j'ai utilisé une fonction récursive pour créer un arbre de segment. Pour les plus grandes valeurs, il a commencé à donner une erreur de segmentation. Donc j'ai pensé avant que ce soit à cause de la valeur de l'index de tableau hors limite mais plus tard j'ai pensé que c'était peut-être parce que la pile du programme devenait trop grande. J'ai écrit ce code pour compter quel est le nombre maximum d'appels récursifs autorisés avant que le système donne une erreur de segmentation.

#include<iostream>
using namespace std; 
void recur(long long int);
int main()
{
  recur(0);
  return 0;
}
void recur(long long int v)
{
  v++;
  cout<<v<<endl;
  recur(v);

}

Après avoir exécuté le code ci-dessus j'ai eu la valeur de v à 261926 et 261893 et ​​261816 avant d'obtenir la faute de segmentation et toutes les valeurs étaient proches de celles-ci.

Maintenant, je sais que cela dépend de la machine à la machine, et la taille de la pile de la fonction étant appelée, mais quelqu'un peut-il expliquer les bases de la façon de rester à l'abri des erreurs de segmentation et qu'est-ce qu'une limite douce? .