Excepción de tiempo de ejecución, recursión demasiado profunda

Question

Convertí el pseudo-código here en C#, y lo repitió recursivamente 10.000 veces. Pero recibo un error de tiempo de ejecución de C#, StackOverflow Exception después de 9217 veces. ¿Cómo puedo prevenir esto?

EDITAR Si se ayuda a nadie, aquí está el código:

private double CalculatePi(int maxRecursion) 
    { 
     return 2 * CalculatePi(maxRecursion, 1); 
    } 

    private double CalculatePi(int maxRecursion, int i) 
    { 
     if (i >= maxRecursion) 
      return 1; 
     return 1 + i/(2.0 * i + 1) * CalculatePi(maxRecursion, i + 1); 
    } 

    double pi = CalculatePi(10000); // 10,000 recursions 

Edit2 Así que todo el mundo parece estar de acuerdo que tengo que convertir esto en iterativo ... ¿alguien puede dar un poco de código? Me parece que no puede escribir ningún código iterativo que funciona ...

EDITAR Gracias a Paul Rieck para esta respuesta, que he probado, y funciona:

private static double CalculatePi(int maxRecursion) 
    { 
     double result = 1; 
     for (int i = maxRecursion; i >= 1; i--) 
     { 
      result = 1 + i/(2.0 * i + 1) * result; 
     } 
     return result * 2; 
    } 

Answer 1

El compilador "C#" compilará esta multa. En tiempo de ejecución, sin embargo, puede terminar con una excepción de StackOverflow (en mi máquina, 10.000 funciona bien, pero muere más tarde).

Esto no es una "excepción de recursión infinita": el desbordamiento de la pila es exactamente lo que dice; Llamar a un método significa colocar información en la pila y eliminarla cuando la llamada retorna. Tiene 10.000 llamadas y ninguna ha regresado, por lo que la pila está llena y se lanza la excepción.

Puede solucionar esto bastante fácilmente en este caso en particular eliminando la recursión y ejecutándose iterativamente. En el caso general, hay formas de eliminar la recursión por iteración, optimización de recursión de cola y aprobación de continuación.

Aquí es una traducción directa rápida a un estilo iterativo:

private static double CalculatePi(int maxRecursion) 
     { 
      double result = 1; 
      for (int i = maxRecursion -1; i >= 1; i--) 
      { 
       result = 1 + i/(2.0 * i + 1) * result; 
      } 
      return result * 2; 
     } 

Answer 2

La llamada recursiva no es recursivo de cola, e incluso si lo fuera, no ayudaría ya que el compilador de C# no optimiza actualmente las llamadas recursivas de cola. EDITAR: Como señalaron Eric Lippert y Gabe, el CLR podría optar por generar llamadas finales aun cuando las instrucciones explícitas de cola no estén en el IL emitido.

1. La mejor manera sería convertir esta solución recursiva en un proceso iterativo.
2. Dado que casi completa, un truco rápido puede ser aumentar el tamaño de pila del subproceso en el que se ejecuta este método.

No haga esto. sólo por diversión:

static void Main() 
{ 
    Console.WriteLine(SafeCalculatePi(10000)); 
} 

// Calculates PI on a separate thread with enough stack-space 
// to complete the computation 
public static double SafeCalculatePi(int maxRecursion) 
{ 
    // We 'know' that you can reach a depth of 9217 for a 1MB stack. 
    // This lets us calculate the required stack-size, with a safety factor 
    double requiredStackSize = (maxRecursion/9217D) * 1.5 * 1024 * 1024 ; 

    double pi = 0; 
    ThreadStart ts = delegate { pi = CalculatePi(maxRecursion); }; 
    Thread t = new Thread(ts, (int)requiredStackSize); 
    t.Start(); 
    t.Join(); 
    return pi; 
} 

Answer 3

No usar recursividad. Este es un buen ejemplo de caso en el que no debería recurrirse, ya que provocará un desbordamiento de la pila de llamadas.

Probablemente pueda convertir eso en no recursivo fácilmente.

Answer 4

No es infinito recursividad, obviamente, ya que se detiene después de 10.000 niveles, pero todavía no es la mejor idea.

Diez mil niveles de pila es una gran cantidad: la pila no es un recurso masivo. Debe convertirlo en una solución iterativa.

Answer 5

No puede evitarlo, la función se llama a sí misma muchas veces; hay un límite sobre qué tan profunda puede llegar la pila de llamadas, y su función la alcanza.

Answer 6

Para envolver a lo que todo el mundo está diciendo aquí-- este es un desbordamiento de pila (Woot! Una pregunta pregunta desbordamiento de pila en StackOverflow. Esto podría causar una pila...)

De todos modos, cada vez que el recursiva método se llama, empuja la pila, lo que quiere decir que pone una referencia a sí mismo en la pila, por lo que cuando se llama a la última llamada a CalculatePi, puede desenrollar el resto de las llamadas.

La pila no es un recurso infinito. Cada inserción en la pila consume un poco de memoria, y cuando la usas todo, obtienes un desbordamiento de la pila.

Answer 7

llamadas a funciones recursivas son casi siempre una manera realmente horrible para hacer las cosas.

Simplemente obtendría el valor de pi de un archivo de cabecera/biblioteca de matemáticas.

Answer 8

Dado que casi puede ejecutar el programa, puede hacer que utilice menos espacio de pila. Simplemente ejecute en modo Release en lugar de Debug y debería funcionar.

Answer 9

El código iterativo de hacer esto es simplemente:

private double CalculatePi(int iterations) { 
    double pi = 1.0; 
    for (int i = iterations - 1; i >= 1; i--) { 
    pi = 1 + i/(2.0 * i + 1) * pi; 
    } 
    return pi * 2.0; 
} 

Uso:

double pi = CalculatePi(51); 

Answer 10

Este woudl sea la variante recursiva no:

 private double CalculatePi(int maxRecursion) 
    { 
     return 2 * CalculatePi2(maxRecursion, 1); 
    } 

    private double CalculatePi2(int maxRecursion, int i) 
    { 
     double product = 1; 
     while (i < maxRecursion) 
     { 
      product = product * (1f + i/(2.0f * i + 1f)); 
      i++; 
     } 
     return product; 
    } 

Answer 11

versión iterativa:

public static double CalculatePi(int maxRecursion) 
{ 
    double result=1; 
    for(int i=maxRecursion-1;i>=1;i--) 
    { 
     result=1+i/(2.0*i+1)*result; 
    } 
    return result*2; 
} 

Answer 12

Así que todo el mundo parece estar de acuerdo con que necesito convertir esto a iterativo ... ¿Alguien puede dar algún código? Parece que no puedo escribir ningún código iterativo que funcione ...

¿Estás pidiendo un pez o pidiendo que te enseñen a pescar? Si el objetivo de este ejercicio es aprender cómo convertir código recursivo a código iterativo, entonces no está bien atendido simplemente obteniendo la respuesta.

Para convertir código recursivo a código iterativo hay muchas formas posibles de hacerlo. La forma más fácil en este caso es simplemente resolver el patrón. ¿Qué hace el código? Calcula:

(1 + 1/(2.0 * 1 + 1)) * 
(1 + 2/(2.0 * 2 + 1)) * 
(1 + 3/(2.0 * 3 + 1)) * 
(1 + 4/(2.0 * 4 + 1)) * 
(1 + 5/(2.0 * 5 + 1)) * 
(1 + 6/(2.0 * 6 + 1)) * 
(1 + 7/(2.0 * 7 + 1)) * 
... 
(1 + 9999/ (2.0 * 9999+ 1)) * 
1 

Ahora puede escribir un bucle que calcule eso? Por supuesto.

double product = 1.0; 
for (int i = 9999; i >= 0; --i) 
    product *= (1 + i/(2.0 * i + 1)); 

Esa es la forma más fácil de hacerlo. Pero hay muchas maneras de resolver este problema.

Puede usar un agregador . Considere la operación "total"; ese es un ejemplo de un agregador. Tienes una secuencia de cosas y mantienes un total acumulado de ellas, acumulando el resultado en un acumulador.Los operadores de consulta estándar someterse a una operación de agregación suministrada por usted:

double seed = 1.0; 
Enumerable.Range(0, 10000).Aggregate(seed, 
    (product, i) => product * (1 + i/(2.0 * i + 1)) 

O bien, puede mantener su algoritmo recursivo, sino eliminar el desbordamiento de pila por:

• la construcción de su propia estructura de pila en el montón
• define una máquina virtual, escribe su programa en el lenguaje de máquina virtual y luego implementa la máquina virtual para mantener su pila en el montón.
• reescribiendo su programa en Continuation Passing Style; cada paso en el camino luego devuelve una continuación a la persona que llama, que invoca la siguiente continuación; la pila nunca se pone profunda

Explicar esas técnicas lleva demasiado tiempo para una respuesta. Tengo una serie de blogs de seis partes sobre cómo usar esas técnicas para convertir los programas recursivos en programas que no consumen mucha pila; empieza a leer desde aquí:

http://blogs.msdn.com/b/ericlippert/archive/2005/07/25/recursion-part-zero.aspx