Utiliser la récursion en C #

Question

Existe-t-il des règles générales lors de l’utilisation de la récursivité pour éviter le débordement de pile?

Answer 1

Le nombre de fois que vous pourrez recurse dépendra:

• La taille de la pile (qui correspond généralement à 1MB IIRC, mais le fichier binaire peut être édité à la main; je ne le recommanderais pas)
• Combien de piles chaque niveau de la récursivité utilise-t-il (une méthode avec 10 variables locales Guid non capturées utilisera plus de pile qu'une méthode qui n'a pas de variables locales, par exemple)
• Le JIT que vous utilisez - parfois, le JIT utilisera la récursion de la queue, d'autres fois non. Les règles sont compliquées et je ne m'en souviens pas. (Il y a un billet de blog de David Broman de 2007 , et une page MSDN du même auteur / date , mais ils peuvent ne plus être à jour à ce jour.)

Comment éviter les débordements de pile? Ne pas recurse trop loin :) Si vous ne pouvez pas être raisonnablement sûr que votre récursion se terminera sans aller très loin (je serais inquiet si "plus de 10" bien que ce soit très sûr), alors réécrivez-le pour éviter la récursivité.

Answer 2

Cela dépend vraiment de l’algorithme récursif que vous utilisez. Si c'est une simple récursion, vous pouvez faire quelque chose comme ceci:

public int CalculateSomethingRecursively(int someNumber)
{
    return doSomethingRecursively(someNumber, 0);
}

private int doSomethingRecursively(int someNumber, int level)
{
    if (level >= MAX_LEVEL || !shouldKeepCalculating(someNumber))
        return someNumber;
    return doSomethingRecursively(someNumber, level + 1);
}

Il convient de noter que cette approche n’est vraiment utile que lorsque le niveau de récursivité peut être défini comme une limite logique. Si cela ne peut pas se produire (par exemple, un algorithme de division et de conquête), vous devrez décider de la manière dont vous souhaitez équilibrer la simplicité par rapport aux performances et aux ressources limitées. Dans ces cas, vous devrez peut-être basculer entre les méthodes une fois que vous avez atteint une limite prédéfinie sur plusieurs bibliothèques. Un moyen efficace de le faire que j'ai utilisé dans l'algorithme quicksort est de le faire sous forme de ratio de la taille totale de la liste. Dans ce cas, la limite logique résulte du moment où les conditions ne sont plus optimales.

Answer 3

Je ne suis au courant d'aucun ensemble difficile pour éviter les débordements de pile. J'essaie personnellement de m'assurer -
1. J'ai bien mon cas de base.
2. Le code atteint le cas de base à un moment donné.

Answer 4

Si vous vous retrouvez à générer autant de cadres de pile, vous pouvez envisager de dérouler votre récursivité dans une boucle.

Surtout si vous faites plusieurs niveaux de récursivité (A- > B- & Gt; C- > A- > B ...), vous constaterez que vous pouvez extraire l'un de ces niveaux dans une boucle et enregistrez un peu de mémoire.

Answer 5

La limite normale, s'il ne reste pas grand-chose sur la pile entre des appels successifs, est d'environ 15 000-25 000 niveaux. 25% de cela si vous êtes sur IIS 6 +.

La plupart des algorithmes récursifs peuvent être exprimés de manière itérative.

Il existe différentes manières d’augmenter l’espace de pile alloué, mais je vous laisserai plutôt trouver une version itérative en premier. :)

Answer 6

Autre chose que d'avoir une taille de pile raisonnable et de vous assurer de diviser et de vaincre votre problème de telle sorte que vous travailliez continuellement sur un problème plus petit, pas vraiment.

Answer 7

Je viens de penser à la récursion de la queue, mais il s’est avéré que C # ne la prend pas en charge. Cependant, le .Net-Framework semble le supporter:

http: // blogs .msdn.com / abhinaba / archive / 2007/07/27 / tail-recursion-on-net.aspx

Answer 8

La taille de pile par défaut pour un thread est de 1 Mo, si vous utilisez le CLR par défaut. Cependant, d'autres hôtes peuvent changer cela. Par exemple, l'hôte ASP modifie la valeur par défaut en 256 Ko. Cela signifie que vous pouvez avoir un code qui fonctionne parfaitement sous VS, mais se brise lorsque vous le déployez dans l'environnement d'hébergement réel.

Heureusement, vous pouvez spécifier une taille de pile lorsque vous créez un nouveau thread en utilisant le constructeur approprié. D'après mon expérience, cela est rarement nécessaire, mais j'ai déjà vu un cas où c'était la solution.

Vous pouvez éditer l'en-tête PE du binaire lui-même pour changer la taille par défaut. Ceci est utile si vous souhaitez modifier la taille du fil principal. Sinon, je recommanderais d'utiliser le constructeur approprié lors de la création de threads.

Answer 9

J'ai écrit un court article à ce sujet ici . En gros, je transmets un paramètre optionnel appelé profondeur, auquel je rajoute 1 chaque fois que je vais plus en profondeur. Dans la méthode récursive, je vérifie la profondeur d'une valeur. S'il est supérieur à la valeur que j'ai définie, je lève une exception. La valeur (seuil) dépend des besoins de vos applications.

Answer 10

N'oubliez pas que si vous devez poser des questions sur les limites du système, vous faites probablement quelque chose de terriblement faux.

Ainsi, si vous pensez que votre pile risque de déborder, vous devrez alors envisager une approche différente du problème.

Il n’est pas difficile de convertir une fonction récursive en une fonction itérative, d’autant plus que C # possède la collection Generic :: Stack. L'utilisation du type Stack déplace la mémoire utilisée dans le tas du programme au lieu de la pile. Cela vous donne la plage d'adresses complète pour stocker les données récursives. Si cela ne suffit pas, il n'est pas trop difficile de paginer les données sur le disque. Mais j’envisagerais sérieusement d’autres solutions si vous arriviez à cette étape.