Existe-t-il une limite câblée à la profondeur de récursivité en C

Le programme en discussion tente de calculer la sum-of-first-n-natural-numbers aide de la recursion . Je sais que cela peut être fait en utilisant une formule simple n*(n+1)/2 mais l’idée ici est d’utiliser la recursion .

Le programme est le suivant:

 #include  unsigned long int add(unsigned long int n) { return (n == 0) ? 0 : n + add(n-1); } int main() { printf("result : %lu \n", add(1000000)); return 0; } 

Le programme a bien fonctionné pour n = 100,000 mais lorsque la valeur de n été scope à 1,000,000 il en a résulté une Segmentation fault (core dumped)

Ce qui suit a été tiré du message gdb .

 Program received signal SIGSEGV, Segmentation fault. 0x00000000004004cc in add (n=Cannot access memory at address 0x7fffff7feff8 ) at kc:4 

Mes questions):

  1. Existe-t-il une limite câblée à recursion depth en C ? ou la recursion depth dépend-elle de la mémoire de stack disponible?

  2. Quelles sont les raisons possibles pour lesquelles un programme recevrait un signal reSIGSEGV?

Généralement, la limite sera la taille de la stack. Chaque fois que vous appelez une fonction, une certaine quantité de stack est consommée (généralement en fonction de la fonction). La quantité consommée est le cadre de la stack et elle est récupérée au retour de la fonction. La taille de la stack est presque presque fixe au démarrage du programme, qu’elle soit spécifiée par le système d’exploitation (et souvent ajustable à cet emplacement) ou même codée en dur dans le programme.

  • Certaines implémentations peuvent avoir une technique leur permettant d’allouer de nouveaux segments de stack au moment de l’exécution. Mais en général, ils ne le font pas.

  • Certaines fonctions consumnt la stack de manière légèrement plus imprévisible, par exemple lorsqu’elles y allouent un tableau de longueur variable.

  • Certaines fonctions peuvent être compilées pour utiliser les appels intercellulaires de manière à préserver l’espace de stack. Parfois, vous pouvez réécrire votre fonction pour que tous les appels (tels que lui-même) se déroulent comme la dernière chose à faire et que votre compilateur l’optimise.

Il n’est pas facile de voir exactement combien d’espace de stack est nécessaire pour chaque appel d’une fonction, et cela dépendra du niveau d’optimisation du compilateur. Un moyen peu coûteux de le faire dans votre cas serait d’imprimer chaque fois qu’on l’appelle; n sera probablement sur la stack (d’autant plus que le programme doit prendre son adresse – sinon il pourrait être dans un registre), et la distance entre ses emplacements successifs indiquera la taille du cadre de la stack.

Il n’y a pas de limite théorique à la profondeur de récursivité en C. Les seules limites sont celles de votre implémentation, généralement un espace de stack limité.
(Notez que la norme C ne nécessite pas réellement d’implémentation basée sur la stack. Je ne connais aucune implémentation dans le monde réel qui ne soit pas basée sur la stack, mais gardez cela à l’esprit.)

Un SIGSEGV peut avoir plusieurs causes, mais le dépassement de votre limite de stack est relativement courant. Déréférencer un mauvais pointeur en est un autre.

1) La consommation de la stack devrait être réduite et écrite comme optimisation de la récursion de la queue.

gcc -O3 prog.c

 #include  unsigned long long int add(unsigned long int n, unsigned long long int sum){ return (n == 0) ? sum : add(n-1, n+sum); //tail recursion form } int main(){ printf("result : %llu \n", add(1000000, 0));//OK return 0; } 

La norme C ne définit pas la profondeur minimale prise en charge pour les appels de fonction. Si c’était le cas, ce qui est assez difficile à garantir de toute façon, il serait mentionné quelque part dans la section 5.2.4 Environmental limits .