Les appels récursifs infinis devraient déclencher un débordement de pile dans ce cas?

Question

J'ai récemment pensé à ce cas de débordement de la pile:

int f() 
{ 
    return f(); 
} 

int main(void) 
{ 
    f(); 
    return 0; 
} 

qui bloque définitivement le programme. Mais ma question est pourquoi n'est-ce pas la même chose qu'une boucle infinie? Le compilateur dans le cas d'un appel récursif sur la ligne de retour pourrait se rendre compte qu'il n'est pas nécessaire de conserver des informations sur la fonction appelante puisque le point de retour à la fonction appelée est le même que celui de l'appelant. Maintenant, dans ce cas, je suis d'accord que le compilateur a besoin de garder les informations des fonctions qui font les appels dans la pile:

int f() 
{ 
    int x = f(); 
    return x; 
} 

int main(void) 
{ 
    f(); 
    return 0; 
} 

Pour que je me manque quelque chose, je vous en serais reconnaissant si quelqu'un me l'explique . Cordialement

Answer 1

Il s'avère que dans certains compilateurs, avec les bons indicateurs d'optimisation, ce ne sera pas causer un débordement de pile! En fait, j'ai essayé de compiler votre programme en g++. Avec l'optimisation aux valeurs par défaut, cela provoque un débordement de pile, mais au niveau d'optimisation -O3, il passe simplement dans une boucle infinie.

La raison pour laquelle il existe une différence entre la récurrence infinie et les boucles infinies est liée à la manière dont le compilateur, par défaut, implémente ces constructions. Les boucles ont historiquement été implémentées en utilisant des instructions de branchement qui indiquent au processeur de prendre en charge l'exécution dans une partie différente du programme. Toutes ces instructions font sauter le compteur de programme ailleurs, ce qui modifie simplement le contenu d'un registre. D'autre part, les appels de fonction sont implémentés en ajoutant un nouvel enregistrement d'activation à la pile pour coder les arguments, l'adresse de retour, etc. de sorte que lorsque la fonction revient, elle sait où retourner. Ceci dit, ce n'est pas "la manière" que des appels de fonction ou des branches doivent être implémentés. Vous pourriez, en théorie, implémenter des boucles en utilisant les appels et les retours de fonctions, bien qu'aucun compilateur ne le fasse. De même, avec les fonctions qui sont récursives à la queue (comme vous le voyez), les compilateurs sont souvent assez intelligents pour éviter toutes les manipulations de pile et les convertir en instructions de branchement naïves pour éviter la surcharge de la pile.En bref, la raison pour laquelle vous obtenez un comportement différent est basée sur la façon dont le compilateur décide d'implémenter le code. S'il est assez intelligent pour voir qu'il n'a pas besoin de faire une configuration d'appel de fonction coûteuse, alors il convertira l'appel en une simple instruction de boucle et boucle pour toujours. S'il ne le détecte pas, il se repliera sur le mécanisme d'appel de fonction naïf.

Answer 2

Vous ne manquez rien. Compilez le programme en utilisant gcc -O2 et il n'y a pas de débordement de pile.

Answer 3

Il doit toujours appuyer sur le compteur de programmes de la pile chaque fois qu'une nouvelle fonction est appelée. C'est l'une des raisons pour lesquelles la pile se développe à chaque invocation de fonction.

Answer 4

Je pense que les auteurs du compilateur C ne se sentent pas probablement qu'il est très nécessaire pour optimiser la sortie des appels récursifs infiniment à des fonctions vides ...

Answer 5

C n'est pas nécessaire pour éliminer les appels de la queue. (Le schéma est nécessaire pour effectuer TCO.)

Answer 6

Je pense que c'est vraiment une question de compilateur alors et comment c'est optimisé. J'imagine que dans les deux cas, une boucle while et cet appel interminablement récursif, les instructions écrites de la machine sont aussi explicitement que possible convertir vos souhaits en instructions. Comme vous le savez, pour la boucle while, vous revenez juste à l'endroit spécifique et continuez à partir de là. avec l'appel récursif, vous poussez sur une nouvelle valeur sur la pile, donc, par votre question, je suppose que c'est vraiment une question de savoir comment votre compilateur est intelligent ...