Je reçois un segfault que je crois être causé par un grand nombre d'appels récursifs. Cela a été noté ici . Ma confusion est que la récursion n'est pas infinie; Il y a un point de rupture définitive une fois qu'un événement donné se produit et cet événement se produira toujours, finalement. Je soupçonne que le problème est que le nombre d'appels récursifs avant la rupture est trop élevé. Sortie de Valgrind: tentative de reproduire: dois-je augmenter la taille de la pile principale comme suggérée par Valgrind? Ou juste éviter la récursion tout à fait?
3 Réponses :
Chaque niveau de récursivité prend une certaine mémoire sur la pile. Sur toutes les plateformes, je suis au courant des piles ont une taille fixe (mais configurable) relativement petite.
En fin de compte, le nombre de récursions est limité à Un moyen de diminuer la taille de chaque appel consiste à transmettre une référence à une structure contenant des paramètres statiques plutôt que des paramètres individuels. Dans votre exemple exemple, cela ne vous aidera pas car vous n'avez qu'un seul paramètre statique. Ce qui pourrait aider sur les plates-formes où un Si ce qui précède ne fonctionne pas, la récursion doit être remplaçable avec une implémentation non récursive et stocker votre état dans un (taille de la pile) / (pile utilisé par appel) afin d'augmenter le nombre de récursions dont vous avez besoin pour augmenter la taille de la pile ou diminuer la taille de la pile ou de diminuer la taille. requis pour chaque appel. Dans votre exemple, vous semblez avoir une pile de 8 Mo afin d'atteindre 1 000 000 niveaux de récursivité, chaque niveau ne peut affecter que 8 octets sur la pile qui n'est probablement pas possible dans la plupart des implémentations.
int est inférieur à un pointeur (par exemple, la plupart des plates-formes 64 bits) serait de supprimer le const & car la référence est susceptible d'être transmise un pointeur.
std :: pile qui est un tas alloué et ne provoquera donc pas des débordements de pile .
Vous devez changer la fonction pour être non récursive. Dans la plupart des architectures modernes (y compris X86), la récursion est implémentée sur la pile et la pile est limitée: elle est relativement petite et ne pousse pas au besoin. En tant que tel, vous devriez éviter les fonctions récursives en règle générale, car elles ont le problème connu de faim de la pile.
Récursion peut sembler être le match parfait pour un problème, mais c'est comme si vous êtes comme un homme humain de l'algorithme. Cependant, chaque fonction récursive peut être relativement facile à transformer en une fonction non récursive qui maintient l'état de l'étape dans une structure dynamique comme Je vous encourage donc à transformer la fonction en une seule et à éviter les fonctions récursives totalement (en dehors des exercices d'apprentissage) std :: pile . En outre, beaucoup d'algorithme récursif ont au moins un algorithme équivalent non récursif connu.
Comme d'autres personnes ont mentionné la récursion est chère et que vous devriez passer une manière itérative .. Toutefois, dans votre cas, si vous avez un peu de connaissances sur les mathématiques, vous pouvez vous faire un problème très très efficace ...
Mettez simplement vous pouvez stockez votre dernière valeur à l'intérieur d'une variable comme suit: puis procédez comme suit: donc cela fait de votre part algorithme o (1);
Pouvez-vous éventuellement réduire la taille de l'enregistrement d'activation? Sinon, la taille de la pile changeante semble être la meilleure mise.
Toutes les ressources de n'importe quel ordinateur sont finies. Quelle méthode à utiliser pour résoudre efficacement un problème dépend du problème et des circonstances. Vous avez apparemment caché le code et le problème actuel, il est donc impossible de donner des conseils définis. Très probablement, vous devriez éviter la récursion. C'est rarement une bonne solution en dehors des cours d'informatique.
@ERICPOSTPISCHIL Pas tout à fait correct, la récursion est bonne quand elle fait ce qui est requis efficacement et en douceur, jetez un coup d'œil à la tour de Hanoi ou à BST récursif ou geeksforgeeks.org/euclidean-algorithms-basic-and-extended .
@Yunfeichen - Le site
geeksforgeeks est notorious pour les exemples de code pauvres, de buggy, de code. Si vous apprenez à programmer de ce site, il y a beaucoup de meilleures options.@Yunfeichen - En outre, le
gcd que vous avez lié à est implémenté dans std :: gcd à l'aide d'unpendant boucle, pas de récursivité.Cela ne résout pas la question, mais vous pouvez supprimer ce
d'autre retourner; . Ça ne fait rien.@Yunfeichen: la tour de Hanoi, les algorithmes euclidiens et les algorithmes d'insertion et de recherche pour les arbres de recherche binaires sont facilement écrits comme des algorithmes itératifs et les mettre en œuvre avec récursivité est inutile et non efficace.
@algae: rien interne au programme "pense" quelque chose est infini. L'erreur se produit car une ressource finie a été dépassée par une utilisation qui est, au moment de l'erreur, finie mais plus grande que la ressource disponible.