Usando Recursión en C #

Question

¿Existen reglas generales al usar la recursión sobre cómo evitar el desbordamiento de pila?

Answer 1

La cantidad de veces que podrá responder dependerá de:

• El tamaño de la pila (que generalmente es de 1MB IIRC, pero el binario se puede editar manualmente; no recomendaría hacerlo)
• la cantidad de pila que utiliza cada nivel de la recursión (un método con 10 variables locales Guid no capturadas tomará más pila que un método que no tenga variables locales, por ejemplo)
• El JIT que está utilizando, a veces el JIT usará la recursión de la cola, otras veces no. Las reglas son complicadas y no las recuerdo. (Hay un publicación del blog de David Broman desde 2007 , y una página de MSDN del mismo autor / fecha , pero pueden estar desactualizadas hasta ahora.)

¿Cómo evitar desbordamientos de pila? No hagas recursiones demasiado lejos :) Si no puedes estar razonablemente seguro de que tu recursión terminará sin llegar muy lejos (estaría preocupado por " más de 10 '', aunque eso es muy seguro), entonces vuelve a escribirla para evitar la recursión.

Answer 2

Realmente depende de qué algoritmo recursivo estés usando. Si es una simple recursión, puedes 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 útil solo cuando el nivel de recursión 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 versus las limitaciones de rendimiento versus recursos. En estos casos, es posible que tenga que cambiar de método una vez que alcance un límite predefinido de forma arbitraria. Un medio eficaz para hacer esto que he usado en el algoritmo de ordenamiento rápido 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 3

No tengo conocimiento de ningún conjunto duro para evitar los flujos de desbordamiento de pila. Yo personalmente trato de asegurar -
1. Tengo mis casos base correctos.
2. El código llega al caso base en algún punto.

Answer 4

Si te encuentras generando tantos marcos de pila, es posible que quieras considerar el desenrollar tu recursión en un bucle.

Especialmente si está realizando múltiples niveles de recursión (A- > B- > C- > A- > B ...) puede encontrar que puede extraer uno de esos niveles en un bucle y guardar 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 estás en IIS 6+.

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

Hay varias formas de aumentar el espacio de pila asignado, pero primero te permitiré encontrar una versión iterativa. :)

Answer 6

Además de tener un tamaño de pila razonable y asegurarte de dividir y vencer el problema, de manera que no siempre trabajas en un problema menor.

Answer 7

Acabo de pensar en la recursión de la cola, pero resultó que C # no lo admite. Sin embargo, el .Net-Framework parece admitirlo:

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

Answer 8

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

Afortunadamente, puedes especificar un tamaño de pila cuando creas un nuevo hilo usando el constructor correcto. En mi experiencia, rara vez es necesario, pero he visto un caso donde esta fue la solución.

Puede editar el encabezado PE del propio binario para cambiar el tamaño predeterminado. Esto es útil si desea cambiar el tamaño del hilo principal. De lo contrario, recomendaría utilizar el constructor adecuado al crear subprocesos.

Answer 9

Escribí un breve artículo sobre esto aquí . Básicamente, paso un parámetro opcional llamado profundidad que le agrego 1 cada vez que profundizo en él. Dentro del método recursivo compruebo la profundidad para un valor. Si es mayor que el valor que establezco, lanzo una excepción. El valor (umbral) dependerá de las necesidades de sus aplicaciones.

Answer 10

Recuerde, si tiene que preguntar sobre los límites del sistema, entonces probablemente esté haciendo algo terriblemente mal.

Por lo tanto, si piensa que podría tener 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 una 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 ubicar los datos en el disco. Pero consideraría seriamente otras soluciones si llegas a esta etapa.