Uso de recursividad en C#

Question

¿Existen reglas generales al usar la recursión para evitar los desbordamientos de pila?

Answer 1

¿Cuántas veces usted será capaz de recursivo dependerá de:

• El tamaño de la pila (que suele ser de 1 MB IIRC, pero el binario puede ser editado a mano, yo no recomendaría hacerlo)
• ¿Cuánto pila cada nivel de los usos de recursividad (un método con 10 Guid variables locales no capturadas será tarda más pila que un método que no tiene ningún variables locales, por ejemplo)
• El JIT que está utilizando - a veces el JIT va a usar recursividad de cola, otras veces no lo hará . Las reglas son complicadas y no puedo recordarlas. (Hay una blog post by David Broman back from 2007 y an MSDN page from the same author/date, pero pueden estar fuera de fecha por ahora.)

¿Cómo evitar desbordamientos de pila? No recurse demasiado lejos :) Si no puede estar razonablemente seguro de que su recursividad terminará sin ir muy lejos (me preocuparía "más de 10", aunque eso es muy seguro), vuelva a escribir para evitar la recursión.

Answer 2

Aparte de tener un tamaño de pila razonable y asegurarse de dividir y conquistar su problema de manera que trabaje continuamente en un problema menor, realmente no.

Answer 3

No conozco ningún conjunto duro para evitar stackoverflows. Personalmente, intento asegurar -
1. Tengo mis fundas de base correctas.
2. El código llega al caso base en algún momento.

Answer 4

Si se encuentra generando tantos marcos de pila, puede considerar desenrollar su recursividad en un bucle.

Especialmente si está haciendo múltiples niveles de recursión (A-> B-> C-> A-> B ...) puede encontrar que puede extraer uno de esos niveles en un bucle y ahorrarse un poco de memoria .

Answer 5

El límite normal, si no queda mucho en la pila entre llamadas sucesivas, es de alrededor de 15000-25000 niveles de profundidad. 25% de eso si tienes IIS 6+.

La mayoría de los algoritmos recursivos se pueden expresar de forma iterativa.

Hay varias maneras de aumentar el espacio asignado en la pila, pero prefiero que primero encuentre una versión iterativa. :)

Answer 6

Realmente depende del algoritmo recursivo que estés usando. Si se trata de la repetición simple, puede hacer algo como esto:

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); 
} 

Vale la pena señalar que este enfoque es realmente sólo es útil cuando el nivel de recursividad se puede definir como un límite lógico. En el caso de que esto no pueda ocurrir (como un algoritmo de dividir y conquistar), tendrá que decidir cómo desea equilibrar la simplicidad con el rendimiento frente a las limitaciones de recursos. En estos casos, es posible que tenga que cambiar de método una vez que haya alcanzado el límite predefinido de la arquitectura. Un medio eficaz de hacer esto que he usado en el algoritmo de la solución rápida es hacerlo como una proporción del tamaño total de la lista. En este caso, el límite lógico es el resultado de cuando las condiciones ya no son óptimas.

Answer 7

Solo pensé en recursividad de cola, pero resultó que C# no lo admite. Sin embargo, el .Net Framework parece apoyarlo:

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

Answer 8

Recuerde, si usted tiene que preguntar acerca de los límites del sistema, entonces es probable que esté haciendo algo muy mal.

Por lo tanto, si cree que podría obtener un desbordamiento de pila en el funcionamiento normal, entonces debe pensar en un enfoque diferente del problema.

No es difícil convertir una función recursiva en iterativa, especialmente porque C# tiene la colección Generic :: Stack. El uso del tipo de pila mueve la memoria utilizada en el montón del programa en lugar de la pila. Esto le proporciona el rango completo de direcciones para almacenar los datos recursivos. Si eso no es suficiente, no es demasiado difícil colocar los datos en el disco. Pero consideraría seriamente otras soluciones si llega a esta etapa.

Answer 9

El tamaño de pila predeterminado para un hilo es de 1 MB, si se está ejecutando con el CLR predeterminado. Sin embargo, otros hosts pueden cambiar eso. Por ejemplo, el host ASP cambia el valor predeterminado a 256 KB. Esto significa que puede tener un código que se ejecute perfectamente bajo VS, pero que se rompa cuando lo implemente en el entorno de alojamiento real.

Afortunadamente puede especificar un tamaño de pila, cuando crea una nueva cadena utilizando el constructor correcto. En mi experiencia, rara vez es necesario, pero he visto un caso donde esta era la solución.

Puede editar el encabezado PE del binario para cambiar el tamaño predeterminado. Esto es útil si quiere cambiar el tamaño del hilo principal. De lo contrario, recomendaría usar el constructor apropiado al crear hilos.

Answer 10

Escribí un breve artículo sobre este here. Básicamente, paso un parámetro opcional llamado profundidad, que le agrega 1 cada vez que profundizo en él. Dentro del método recursivo, verifico la profundidad de un valor. Si es mayor que el valor que configuro, arrojo una excepción. El valor (umbral) dependería de las necesidades de su aplicación.