¿Qué métodos existen para evitar un desbordamiento de pila en un algoritmo recursivo?

44

Pregunta

¿Cuáles son las formas posibles de resolver un desbordamiento de pila causado por un algoritmo recursivo?

Ejemplo

Estoy tratando de resolver el problema 14 del Proyecto Euler y decidí intentarlo con un algoritmo recursivo. Sin embargo, el programa se detiene con un java.lang.StackOverflowError. Comprensiblemente. De hecho, el algoritmo desbordó la pila porque intenté generar una secuencia de Collatz para un número muy grande.

Soluciones

Entonces me preguntaba: ¿qué formas estándar existen para resolver un desbordamiento de la pila suponiendo que su algoritmo recursivo se escribió correctamente y siempre terminaría desbordando la pila? Dos conceptos que me vinieron a la mente fueron:

  1. recursión de la cola
  2. iteración

¿Son correctas las ideas (1) y (2)? ¿Hay otras opciones?

Editar

Sería útil ver algún código, preferiblemente en Java, C #, Groovy o Scala.

Quizás no use el problema del Proyecto Euler mencionado anteriormente para que no se eche a perder para otros, pero tome algún otro algoritmo. Tal vez factorial, o algo similar.

Lernkurve
fuente
3
Iteración. Memoisation
James
2
Obviamente, Memoization solo funciona cuando en realidad hay cálculos repetidos.
Jörg W Mittag el
2
También vale la pena señalar que no todas las implementaciones de lenguaje pueden hacer optimizaciones de recursión de cola de todos modos
jk.
2
Esto probablemente se resolvería mejor con corecursion que con recursion.
Jörg W Mittag
3
Si está trabajando desde un número menor a 1,000,000 y va al 1, la respuesta a esta pregunta involucra aproximadamente 500 pasos para llegar a 1. Esto no debería gravar la recurrencia dado un pequeño marco de pila. --- Si está intentando resolver comenzando en 1, luego sigue a 2, 4, 8, 16, {5,32} y sube desde allí, lo está haciendo mal.

Respuestas:

35

La optimización de llamadas de cola está presente en muchos idiomas y compiladores. En esta situación, el compilador reconoce una función de la forma:

int foo(n) {
  ...
  return bar(n);
}

Aquí, el lenguaje puede reconocer que el resultado que se devuelve es el resultado de otra función y cambiar una llamada de función con un nuevo marco de pila en un salto.

Darse cuenta de que el método factorial clásico:

int factorial(n) {
  if(n == 0) return 1;
  if(n == 1) return 1;
  return n * factorial(n - 1);
}

No se puede optimizar la llamada de cola debido a la inspección necesaria en la devolución. ( Ejemplo de código fuente y salida compilada )

Para hacer esta llamada de cola optimizable,

int _fact(int n, int acc) {
    if(n == 1) return acc;
    return _fact(n - 1, acc * n);
}

int factorial(int n) {
    if(n == 0) return 1;
    return _fact(n, 1);
}

Compilar este código con gcc -O2 -S fact.c(el -O2 es necesario para habilitar la optimización en el compilador, pero con más optimizaciones de -O3 se hace difícil para un humano leer ...)

_fact(int, int):
    cmpl    $1, %edi
    movl    %esi, %eax
    je  .L2
.L3:
    imull   %edi, %eax
    subl    $1, %edi
    cmpl    $1, %edi
    jne .L3
.L2:
    rep ret

( Ejemplo de código fuente y salida compilada )

Se puede ver en el segmento .L3, en jnelugar de un call(que hace una llamada de subrutina con un nuevo marco de pila).

Tenga en cuenta que esto se hizo con C. La optimización de llamadas de cola en Java es difícil y depende de la implementación de JVM (dicho esto, no he visto ninguna que lo haga, porque es difícil e implica que el modelo de seguridad de Java requerido requiere marcos de pila - que es lo que evita el TCO) - tail-recursion + java y tail-recursion + optimization son buenos conjuntos de etiquetas para navegar. Puede encontrar que otros lenguajes JVM pueden optimizar mejor la recursividad de cola (intente clojure (que requiere la recurrencia para optimizar la llamada de cola) o scala).

Dicho eso

Hay una cierta alegría en saber que escribiste algo correctamente , de la manera ideal que se puede hacer.
Y ahora, voy a conseguir un poco de whisky y ponerme algo de electrónica alemana ...


A la pregunta general de "métodos para evitar un desbordamiento de pila en un algoritmo recursivo" ...

Otro enfoque es incluir un contador de recursividad. Esto es más para detectar bucles infinitos causados ​​por situaciones fuera del control de uno (y una codificación deficiente).

El contador de recursión toma la forma de

int foo(arg, counter) {
  if(counter > RECURSION_MAX) { return -1; }
  ...
  return foo(arg, counter + 1);
}

Cada vez que realiza una llamada, incrementa el contador. Si el contador se vuelve demasiado grande, se produce un error (aquí, solo un retorno de -1, aunque en otros idiomas puede preferir lanzar una excepción). La idea es evitar que sucedan cosas peores (errores de falta de memoria) cuando se hace una recursión que es mucho más profunda de lo esperado y probablemente un bucle infinito.

En teoría, no deberías necesitar esto. En la práctica, he visto código mal escrito que ha afectado a esto debido a una gran cantidad de pequeños errores y malas prácticas de codificación (problemas de concurrencia multiproceso donde algo cambia algo fuera del método que hace que otro hilo entre en un bucle infinito de llamadas recursivas).


Use el algoritmo correcto y resuelva el problema correcto. Específicamente para la Conjetura de Collatz, parece que estás tratando de resolverlo de la manera xkcd :

XKCD # 710

Estás comenzando en un número y haciendo un recorrido transversal del árbol. Esto lleva rápidamente a un espacio de búsqueda muy grande. Una ejecución rápida para calcular el número de iteraciones para la respuesta correcta da como resultado unos 500 pasos. Esto no debería ser un problema para la recursividad con un marco de pila pequeño.

Si bien conocer la solución recursiva no es algo malo, uno también debe darse cuenta de que muchas veces la solución iterativa es mejor . En Stack Overflow at Way se pueden ver varias formas de abordar la conversión de un algoritmo recursivo a uno iterativo para pasar de la recursividad a la iteración .

Comunidad
fuente
1
Me encontré con esa caricatura de xkcd hoy mientras navegaba por la web. :-) Las caricaturas de Randall Munroe son una delicia.
Lernkurve
@Lernkurve Noté la adición de la edición de código después de haber comenzado a escribir esto (y publicado). ¿Necesita otros ejemplos de código para esto?
No, en absoluto. Es perfecto. Muchas gracias por preguntar!
Lernkurve
¿Puedo sugerir agregar esta caricatura también: imgs.xkcd.com/comics/functional.png
Ellen Spertus
@espertus gracias. Lo agregué (limpié algunas fuentes de generación y agregué un poco más)
17

Tenga en cuenta que la implementación del lenguaje debe admitir la optimización de recursión de cola. No creo que los principales compiladores de Java lo hagan.

La memorización significa que recuerda el resultado de un cálculo en lugar de volver a calcularlo cada vez, como:

collatz(i):
    if i in memoized:
        return memoized[i]

    if i == 1:
        memoized[i] = 1
    else if odd(i):
        memoized[i] = 1 + collatz(3*i + 1)
    else
        memoized[i] = 1 + collatz(i / 2)

    return memoized[i]

Cuando calcules cada secuencia menos de un millón, habrá muchas repeticiones al final de las secuencias. Memoization lo convierte en una búsqueda rápida de la tabla hash para valores anteriores en lugar de tener que hacer que la pila sea cada vez más profunda.

Karl Bielefeldt
fuente
1
Explicación muy comprensible de la memorización. Sobre todo, gracias por ilustrarlo con un fragmento de código. Además, "habrá mucha repetición al final de las secuencias" me dejó las cosas claras. Gracias.
Lernkurve
10

Me sorprende que nadie haya mencionado el trampolín todavía. Un trampolín (en este sentido) es un bucle que invoca iterativamente funciones de retorno de troncos (estilo de paso de continuación) y puede usarse para implementar llamadas a funciones recursivas de cola en un lenguaje de programación orientado a la pila.

Esta pregunta de StackOverflow entra en más detalles sobre varias implementaciones de trampolining en Java: Manejo de StackOverflow en Java para Trampoline

Rein Henrichs
fuente
Pensé en esto de inmediato también. Los trampolines son un método para realizar la optimización de las llamadas de cola, por lo que la gente lo está diciendo (casi). +1 Para la referencia específica.
Steven Evers
6

Si está utilizando un lenguaje y un compilador que reconoce las funciones recursivas de cola y las maneja correctamente (es decir, "reemplaza a la persona que llama en su lugar con la persona que llama"), entonces la pila no debería descontrolarse. Esta optimización esencialmente reduce un método recursivo a uno iterativo. No creo que Java haga esto, pero sé que Racket sí.

Si opta por un enfoque iterativo, en lugar de un enfoque recursivo, está eliminando gran parte de la necesidad de recordar de dónde provienen las llamadas, y prácticamente eliminando la posibilidad de un desbordamiento de la pila (de todas formas llamadas recursivas).

La memorización es excelente y puede reducir el número total de llamadas a métodos al buscar resultados calculados previamente en un caché, dado que su cálculo general generará muchos cálculos más pequeños y repetidos. Esta idea es genial, también es independiente de si está utilizando o no un enfoque iterativo o recursivo.

Benjamin Brumfield
fuente
1
+1 para señalar la memorización también es útil en enfoques iterativos.
Karl Bielefeldt
Todos los lenguajes de programación funcionales tienen optimización de llamada de cola.
3

podría crear una enumeración que reemplace la recursividad ... aquí hay un ejemplo para calcular la facultad haciendo eso ... (no funcionará para números grandes ya que solo usé mucho tiempo en el ejemplo :-))

public class Faculty
{

    public static IEnumerable<long> Faculties(long n)
    {
        long stopat = n;

        long x = 1;
        long result = 1;

        while (x <= n)
        {
            result = result * x;
            yield return result;
            x++;
        }
    }
}

incluso si esto no es una memoria, de esta manera anulará un desbordamiento


EDITAR


Lo siento si molesto a algunos de ustedes. Mi única intención era mostrar una forma de evitar un desbordamiento de pila. Probablemente debería haber escrito un ejemplo de código completo en lugar de solo una pequeña parte de un extracto de código escrito rápidamente y aproximado.

El siguiente código

  • evita la recursividad mientras uso calcular los valores requeridos de forma iterativa.
  • incluye la memorización ya que los valores ya calculados se almacenan y se recuperan si ya se calcularon
  • también incluye un cronómetro, para que pueda ver que la memorización funciona correctamente

... umm ... si lo ejecuta, asegúrese de configurar su ventana de shell de comandos para que tenga un búfer de 9999 líneas ... los 300 habituales no serán suficientes para ejecutar los resultados del siguiente programa ...

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.Timers;

namespace ConsoleApplication1
{
    class Program
    {
        static Stopwatch w = new Stopwatch();
        static Faculty f = Faculty.GetInstance();

        static void Main(string[] args)
        {
            Out(5);
            Out(10);
            Out(-5);
            Out(0);
            Out(1);
            Out(4);
            Out(29);
            Out(30);
            Out(20);
            Out(10000);
            Out(20000);
            Out(19999);
            Console.ReadKey();
        }

        static void Out(BigInteger n)
        {
             try
            {
                w.Reset();
                w.Start();
                var x = f.Calculate(n);
                w.Stop();
                var time = w.ElapsedMilliseconds;
                Console.WriteLine(String.Format("{0} ({2}ms): {1}", n, x, time));
            }
            catch (ArgumentException e)
            {
                Console.WriteLine(e.Message);
            }

            Console.WriteLine("\n\n");
       }
    }

Declaro * 1 variable variable "instancia" en la clase Facultad a una tienda un singleton. De esa manera, mientras su programa se esté ejecutando, cada vez que "GetInstance ()" de la clase obtenga la instancia que ha almacenado todos los valores ya calculados. * 1 lista ordenada estática que contendrá todos los valores ya calculados

En el constructor también agrego 2 valores especiales de la lista 1 para las entradas 0 y 1.

    public class Faculty
    {
        private static SortedList<BigInteger, BigInteger> _values; 
        private static Faculty _faculty {get; set;}

        private Faculty ()
        {
            _values = new SortedList<BigInteger, BigInteger>();
            _values.Add(0, 1);
            _values.Add(1, 1);
        }

        public static Faculty GetInstance() {
            _faculty = _faculty ?? new Faculty();
            return _faculty;
        }

        public BigInteger Calculate(BigInteger n) 
        {
            // check if input is smaller 0
            if (n < 0)
                throw new ArgumentException(" !!! Faculty is not defined for values < 0 !!!");

            // if value is not already calculated => do so
            if(!_values.ContainsKey(n))
                Faculties(n);

            // retrieve n! from Sorted List
            return _values[n];
        }

        private static void Faculties(BigInteger n)
        {
            // get the last calculated values and continue calculating if the calculation for a bigger n is required
            BigInteger i = _values.Max(x => x.Key),
                           result = _values[i];

            while (++i <= n)
            {
                CalculateNext(ref result, i);
                // add value to the SortedList if not already done
                if (!_values.ContainsKey(i))
                    _values.Add(i, result);
            }
        }

        private static void CalculateNext(ref BigInteger lastresult, BigInteger i) {

            // put in whatever iterative calculation step you want to do
            lastresult = lastresult * i;

        }
    }
}
Ingo
fuente
55
Técnicamente esto es iteración como se ha extraído por completo cualquier recursividad
monstruo de trinquete
que es :-) y memoriza los resultados dentro de las variables de métodos entre cada paso de cálculo
Ingo
2
Yo te entienden mal memoisation pienso, que es cuando facultades (100) se llama la primera vez que se calcula el resultado y lo almacena en un hash y regresaron, a continuación, cuando se le llama de nuevo el resultado almacenado se devuelve
monstruo de trinquete
@jk. Para su crédito, él nunca dice que esto es recursivo.
Neil
incluso si esto no es una memorización, de esta manera anulará un desbordamiento de pila
Ingo
2

En cuanto a Scala, puede agregar la @tailrecanotación a un método recursivo. De esta manera, el compilador asegura que la optimización de la llamada final se llevó a cabo:

Entonces esto no compilará (factorial):

@tailrec
def fak1(n: Int): Int = {
  n match {
    case 0 => 1
    case _ => n * fak1(n - 1)
  }
}

el mensaje de error es:

scala: no se pudo optimizar el método anotado @tailrec fak1: contiene una llamada recursiva que no está en posición de cola

Por otra parte:

def fak3(n: Int): Int = {
  @tailrec
  def fak3(n: Int, result: Int): Int = {
    n match {
      case 0 => result
      case _ => fak3(n - 1, n * result)
    }
  }

  fak3(n, 1)
}

compila y se realizó la optimización de la cola de llamadas.

Berilio
fuente
1

Una posibilidad que aún no se ha mencionado es tener recurrencia, pero sin usar una pila del sistema. Por supuesto, también puede desbordar su montón, pero si su algoritmo realmente necesita retroceder de una forma u otra (¿por qué usar la recursión de otra manera?), No tiene otra opción.

Hay implementaciones sin pila de algunos lenguajes, por ejemplo, Stackless Python .

SK-logic
fuente
0

Otra solución sería simular su propia pila y no confiar en la implementación del compilador + tiempo de ejecución. Esta no es una solución simple ni rápida, pero teóricamente obtendrá StackOverflow solo cuando no tenga memoria.

m3th0dman
fuente