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

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.

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 :

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 .

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.

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

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.

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;

        }
    }
}

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.

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 .

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.