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

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 idioma 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.

Ten en cuenta 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 es no llamada de cola optimizable debido a la inspección necesaria en la devolución. ( Ejemplo de código fuente y salida compilada )

Para hacer que esta llamada final sea 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);
}

Compilando 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 que un humano lea ...)

_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

( Código fuente de ejemplo y salida compilada )

Uno puede ver en el segmento .L3 , el jne en lugar de un call (lo 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 Tail en Java es difícil y depende de la implementación de JVM (es decir, no he visto ninguna que lo haga, porque es difícil y tiene implicaciones del modelo de seguridad Java requerido). que requieren marcos de pila, que es lo que TCO evita) - tail-recursion + java y tail-recursion + optimization son buenos conjuntos de etiquetas para navegar. Es posible que otros lenguajes JVM puedan optimizar la recursión de la cola (pruebe clojure (que requiere recurrir para optimizar la llamada a la cola), o scala).

Dicho esto,

Hayunaciertaalegríaalsaberqueescribistealgocorrecto,delamaneraidealenquepuedehacerse.
_{^{Yahora, Voy a tomar un poco de whisky y poner 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 recursión. Esto es más para detectar bucles infinitos causados por situaciones fuera del control (y 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 haces una llamada, incrementas el contador. Si el contador se vuelve demasiado grande, se produce un error (aquí, solo una devolución de -1, aunque en otros idiomas puede preferir lanzar una excepción). La idea es evitar que ocurran cosas peores (errores de memoria) cuando se realiza una recursión que es mucho más profunda de lo esperado y es probable que se produzca un bucle infinito.

En teoría, no deberías necesitar esto. En la práctica, he visto un 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).

Usa el algoritmo correcto y resuelve el problema correcto. Específicamente para la Conjetura de Collatz, aparece que está intentando resolverlo de la forma xkcd :

Estáscomenzandoconunnúmeroyhaciendounrecorridodeárbol.Estoconducerápidamenteaunespaciodebúsquedamuygrande.Unaejecuciónrápidaparacalcularelnúmerodeiteracionesparalosresultadosdelarespuestacorrectaenunos500pasos.Estonodeberíaserunproblemaparalarecursiónconunmarcodepilapequeño.

Aunquesaberquelasoluciónrecursivanoesalgomalo,tambiéndeberíadarsecuentadequemuchasveceslasolucióniterativa es mejor . Se pueden ver varias formas de acercar un algoritmo recursivo a uno iterativo en Desbordamiento de pila en Cómo pasar de la recursión a la iteración .

Tenga en cuenta que la implementación del lenguaje debe ser compatible con la optimización de recursión de cola. No creo que los principales compiladores de java lo hagan.

Memoización significa que recuerdas el resultado de un cálculo en lugar de recalcularlo 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á mucha repetición al final de las secuencias. La memorización hace que sea una búsqueda rápida en la tabla hash de valores anteriores en lugar de tener que hacer que la pila sea cada vez más profunda.

Me sorprende que nadie haya mencionado trampolining todavía. Un trampolín (en este sentido) es un bucle que invoca de manera iterativa funciones de retorno de procesador (estilo de paso de continuación) y se puede usar para implementar llamadas de función recursiva de cola en un lenguaje de programación orientado a la pila.

Esta pregunta de StackOverflow contiene bastante 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 reconocen las funciones recursivas de la cola y los maneja correctamente (es decir, "reemplaza al llamante en su lugar con la persona que llama "), entonces sí, la pila no debería crecer fuera de control. Esta optimización esencialmente reduce un método recursivo a uno iterativo. No creo que Java haga esto, pero sé que Racket lo hace.

Si adopta 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 pila (de todas formas, de las llamadas recursivas).

La memoria 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 incurrirá en muchos cálculos más pequeños y repetidos. Esta idea es genial, también es independiente de si está utilizando un enfoque iterativo o recursivo o no.

usted podría crear una Enumeración que reemplazará la recursión ... aquí hay un ejemplo para calcular la facultad haciendo eso ... (no funcionará para números grandes, ya que solo usé mucho 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 memoización, de esta manera anulará un desbordamiento de pila

EDIT

Lo siento si molesto a algunos de ustedes. Mi única intención era mostrar una manera 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 rápido y rápido.

El siguiente código

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

... umm ... si lo ejecutas, asegúrate de configurar tu ventana de shell de comandos para tener un búfer de 9999 líneas ... las 300 habituales no serán suficientes para ejecutar los resultados del programa a continuación ... .

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 "instancia" estática en la clase de Facultad para almacenar un singleton. De esa manera, siempre que su programa se ejecute, siempre 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 anotación @tailrec a un método recursivo. De esta manera, el compilador garantiza que la optimización de la llamada de cola realmente tuvo lugar:

Así que esto no se 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 la posición final

Por otro lado:

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 la optimización de la llamada de cola tuvo lugar.

Una posibilidad que aún no se ha mencionado es tener una recursión, pero sin utilizar 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?), No tiene otra opción.

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

Otra solución sería simular tu 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 en teoría, solo obtendrá StackOverflow cuando no tenga memoria.