Utilisation de la récursion en C#

cela dépend vraiment de l'algorithme récursif que vous utilisez. Si c'est simple de récursivité, 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 est intéressant de noter que cette approche n'est vraiment utile que lorsque le niveau de récursion peut être défini comme une limite logique. Dans le cas où cela ne peut pas se produire (tel qu'un algorithme de diviser pour mieux régner), vous devrez décider comment vous voulez équilibrer la simplicité par rapport à la performance par rapport à la limitation des ressources. Dans ces cas, vous pouvez avoir à basculer entre les méthodes une fois que vous avez atteint une limite pré-définie arbritrary. Un moyen efficace de faire ce que j'ai utilisé dans l'algorithme quicksort est de le faire en tant que ratio de la taille totale de la liste. Dans ce cas, la limite logique résulte du fait que les conditions ne sont plus optimales.

je ne suis pas au courant de tout ensemble pour éviter les débordements de piles. J'essaie personnellement d'assurer -

1. J'ai ma base de cas.

2. Le code atteint le cas de base à un moment donné.

si vous vous trouvez à générer autant de cadres de pile, vous pourriez envisager de dérouler votre récursion en boucle.

surtout si vous faites plusieurs niveaux de récursion (A - >B - >C - >A - > B... vous pourriez trouver que vous pouvez extraire l'un de ces niveaux dans une boucle et vous épargner un peu de mémoire.

la limite normale, si peu est laissée sur la pile entre les appels successifs, est d'environ 15000-25000 niveaux de profondeur. 25% si vous êtes sur IIS 6+.

la plupart des algorithmes récursifs peuvent être exprimés de façon itérative.

il y a plusieurs façons d'augmenter l'espace alloué à la pile, mais je vais plutôt vous laisser trouver une version itérative d'abord. :)

autre que d'avoir une taille de pile raisonnable et de s'assurer que vous divisez et conquérir votre problème de sorte que vous travaillez continuellement sur un plus petit problème, pas vraiment.

je viens de penser à la queue-la récursivité, mais il s'est avéré, que le C# n'est pas en charge. Cependant, le .net-Framework semble le soutenir:

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

la taille de la pile par défaut pour un thread est de 1 MB, si vous utilisez le CLR par défaut. Cependant, d'autres hôtes peuvent changer. Par exemple, L'hôte ASP change la valeur par défaut à 256 KB. Cela signifie que vous pouvez avoir du code qui fonctionne parfaitement sous VS, mais qui se casse 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 correct. Dans mon expérience, il est rarement nécessaire, mais j'ai 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 voulez changer la taille du thread principal. Sinon, je recommanderais d'utiliser le constructeur approprié lors de la création de threads.

j'ai écrit un court article sur ce ici. Fondamentalement, je passe un paramètre optionnel appelé profondeur, ajoutant 1 à chaque fois que je vais plus profondément dans elle. Dans la méthode récursive je vérifie la profondeur pour une valeur. Si elle est supérieure à la valeur que j'ai fixée, je jette une exception. La valeur (seuil) dépend de vos besoins d'applications.

rappelez-vous, si vous devez poser des questions sur les limites du système, alors vous faites probablement quelque chose d'horriblement mal.

Donc, si vous pensez que vous pourriez obtenir un débordement de la pile en fonctionnement normal, alors vous devez penser à 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 générique::Stack. En utilisant le type de pile déplace la mémoire utilisée dans le tas du programme au lieu de la pile. Ce vous donne la gamme complète d'adresses pour stocker les données récursives. Si cela ne suffit pas, il n'est pas trop difficile de page les données sur le disque. Mais j'envisagerais sérieusement d'autres solutions si vous arrivez à ce stade.