récursivité c ++ se déroule sans raison évidente

Vous êtes probablement en train de déborder de la stack, à quel point votre programme sera tué sommairement. La profondeur de la stack limite toujours le montant que vous pouvez récupérer, et si vous atteignez cette limite, cela signifie que votre algorithme doit changer.

Je pense que vous avez raison d’attendre que le code fonctionne pour toujours, comme expliqué dans

Comment puis-je vérifier si gcc effectue une optimisation de la récursion de la queue?

Votre code devrait pouvoir fonctionner à tout moment si gcc effectue une récursion de la queue. Sur ma machine, il semble que -O3 oblige gcc à générer des appels de fin de ligne et à aplatir la stack. 🙂

Je suppose que vous définissez le drapeau d’optimisation sur O2 ou O3.

Vous provoquez un dépassement de capacité de la stack (à court d’espace de stack) car vous ne fournissez pas de condition de sortie.

 void rek(double x){ if(x > 10) return; std::cout << x << std::endl; rek(x + 1); } 

Vous attendez-vous à ce que cela fonctionne pour toujours?

Ce ne sera pas le cas. À un moment donné, vous allez manquer de stack.

C’est drôle, en parlant de débordement de stack sur stackoverflow.com. 😉 La stack d’appels est limitée (vous pouvez la personnaliser à partir des parameters du projet), mais à un moment donné, lorsque vous aurez des appels de boucle infinis, elle sera dépassée et votre programme terminé.

Si vous voulez éviter un débordement de stack avec une récursion infinie, vous devrez malheureusement fouiller dans un assemblage afin de changer la stack de sorte qu’un nouvel enregistrement d’activation ne soit pas constamment poussé sur la stack, ce qui après un certain temps provoquer le débordement. Comme vous effectuez l’appel récursif à la fin de la fonction, cela est appelé dans d’autres langages où la récursivité est populaire (c.-à-d. Lisp, Scheme, Haskell, etc.), une optimisation d’appel de piste. Cela évite un débordement de stack en transformant essentiellement l’appel de queue en une boucle. Ce serait quelque chose comme ça en C (note: j’utilise un assemblage en ligne avec gcc sur x86, et j’ai changé vos arguments en double afin de simplifier l’assemblage. J’ai aussi changé en C de C ++ pour éviter la gestion des noms de fonctions par des noms de fichiers Enfin, le “\ n \ t” à la fin de chaque instruction n’est pas une commande d’assemblage réelle mais est nécessaire pour l’assemblage en ligne dans gcc):

 #include  void rek(int x) { printf("Value for x: %d\n", x); //we now duplicate the equvalent of `rek(x+1);` with tail-call optimization __asm("movl 8(%ebp), %eax\n\t" //get the value of x off the stack "incl %eax\n\t" //add 1 to the value of x "movl 4(%ebp), %ecx\n\t" //save the return address on the stack "movl (%ebp), %edx\n\t" //save the caller's activation record base pointer "addl $12, %ebp\n\t" //erase the activation record "movl %ebp, %esp\n\t" //reset the stack pointer "pushl %eax\n\t" //push the new value of x on the stack for function call "pushl %ecx\n\t" //push the return value back to the caller (ie, main()) on the stack "movl %edx, %ebp\n\t" //restore the old value of the caller's stack base pointer "jmp rek\n\t"); //jump to the start of rek() } int main() { rek(1); printf("Finished call\n"); //<== we never get here return 0; } 

Compilé avec gcc 4.4.3 sur Ubuntu 10.04, il fonctionnait à peu près "à l'infini" dans une boucle infinie sans débordement de stack, où, sans l'optimisation des appels, il se heurtait rapidement à une erreur de segmentation. Vous pouvez voir à partir des commentaires dans la section __asm comment l'espace d'enregistrement de l'activation de la stack est "recyclé" afin que chaque nouvel appel n'utilise pas d'espace sur la stack. Cela implique de sauvegarder les valeurs de clé dans l'ancien enregistrement d'activation (le pointeur de base de l'enregistrement d'activation de l'appelant précédent et l'adresse de retour) et de les restaurer, mais avec les arguments modifiés pour le prochain appel récursif à la fonction.

Et encore, d’autres langages, principalement les langages fonctionnels, effectuent l’optimisation de l’appel en tant que caractéristique de base du langage. Donc, une fonction récursive d’appel dans Scheme / Lisp / etc. ne débordera pas la stack car ce type de manipulation de stack est fait sous le capot pour vous lorsqu'un nouvel appel de fonction est effectué en tant que dernière instruction d'une fonction existante.

Eh bien, vous avez défini la récursion infinie et le débordement de la stack, ce qui tue votre application. Si vous voulez vraiment imprimer tous les nombres; puis utilisez une boucle.

 int main(...) { double x = 1; while (true) { std:cout << x << std::endl; x += 1; } } 

Chaque méthode récursive devrait implémenter une condition de sortie, sinon vous obtiendrez un débordement de stack et le programme se terminera.

Dans votre cas, il n’y a pas de condition sur le paramètre que vous passez à la fonction, par conséquent, il s’exécute pour toujours et finit par tomber en panne.