Quais métodos existem para evitar um estouro de pilha em um algoritmo recursivo?

Pergunta, questão

Quais são as formas possíveis de resolver um estouro de pilha causado por um algoritmo recursivo?

Exemplo

Estou tentando resolver o problema do Project Euler 14 e decidi tentar com um algoritmo recursivo. No entanto, o programa para com um java.lang.StackOverflowError. Compreensível. O algoritmo realmente sobrecarregou a pilha porque tentei gerar uma sequência Collatz para um número muito grande.

Soluções

Então, eu estava pensando: que maneiras padrão existem para resolver um estouro de pilha assumindo que seu algoritmo recursivo foi escrito corretamente e sempre acabaria transbordando? Dois conceitos que vieram à mente foram:

1. recursão da cauda
2. iteração

As idéias (1) e (2) estão corretas? Existem outras opções?

Editar

Seria bom ver algum código, de preferência em Java, C #, Groovy ou Scala.

Talvez não use o problema do Project Euler mencionado acima, para que não seja estragado por outros, mas use outro algoritmo. Fatorial talvez, ou algo semelhante.

A otimização da chamada de cauda está presente em vários idiomas e compiladores. Nessa situação, o compilador reconhece uma função do formulário:

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

Aqui, o idioma é capaz de reconhecer que o resultado retornado é o resultado de outra função e alterar uma chamada de função com um novo quadro de pilha em um salto.

Perceba que o método fatorial clássico:

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

não é otimizado para chamada final devido à inspeção necessária no retorno. ( Exemplo de código fonte e saída compilada )

Para tornar essa chamada final otimizável,

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 esse código com gcc -O2 -S fact.c(o -O2 é necessário para ativar a otimização no compilador, mas com mais otimizações de -O3 fica difícil para um ser humano ler ...)

_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

( Exemplo de código fonte e saída compilada )

Pode-se ver no segmento .L3, em jnevez de um call(que faz uma chamada de sub-rotina com um novo quadro de pilha).

Observe que isso foi feito com C. A otimização de chamada de cauda em Java é difícil e depende da implementação da JVM (isto é, eu não vi nenhum que faça isso, porque é difícil e implicações do modelo de segurança Java necessário que requer quadros de pilha - que é o que o TCO evita) - recursão de cauda + java e recursão de cauda + otimização são bons conjuntos de tags para navegar. Você pode achar que outros idiomas da JVM são capazes de otimizar melhor a recursão da cauda (tente o clojure (que requer que a repetição para otimizar a chamada da cauda) ou scala).

Dito isto,

Há uma certa alegria em saber que você escreveu algo certo - da maneira ideal que isso pode ser feito.
_{^{E agora, vou pegar um pouco de uísque e colocar alguma música eletrônica alemã ...}}

À questão geral de "métodos para evitar um estouro de pilha em um algoritmo recursivo" ...

Outra abordagem é incluir um contador de recursão. Isso é mais para detectar loops infinitos causados ​​por situações fora do controle de alguém (e codificação ruim).

O contador de recursão assume a forma de

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

Cada vez que você faz uma chamada, você incrementa o contador. Se o contador ficar muito grande, você errará (aqui, apenas um retorno de -1, embora em outros idiomas você prefira lançar uma exceção). A idéia é impedir que coisas piores aconteçam (erros de falta de memória) ao fazer uma recursão muito mais profunda do que o esperado e provavelmente um loop infinito.

Em teoria, você não deveria precisar disso. Na prática, eu vi códigos mal escritos que atingiram isso devido a uma infinidade de pequenos erros e práticas ruins de codificação (problemas de simultaneidade multithread em que algo muda algo fora do método que faz com que outro encadeamento entre em um loop infinito de chamadas recursivas).

Use o algoritmo certo e resolva o problema certo. Especificamente para a conjectura de Collatz, parece que você está tentando resolvê-lo da maneira xkcd :

Você está começando em um número e fazendo uma travessia em árvore. Isso leva rapidamente a um espaço de pesquisa muito grande. Uma execução rápida para calcular o número de iterações para a resposta correta resulta em cerca de 500 etapas. Isso não deve ser um problema de recursão com um pequeno quadro de pilha.

Embora conhecer a solução recursiva não seja algo ruim, é preciso também perceber que muitas vezes a solução iterativa é melhor . Várias maneiras de abordar a conversão de um algoritmo recursivo para um iterativo podem ser vistas no Stack Overflow at Way para ir de recursão para iteração .

Lembre-se de que a implementação do idioma deve suportar a otimização da recursão da cauda. Eu não acho que os principais compiladores java fazem.

Memoização significa que você se lembra do resultado de um cálculo, em vez de recalculá-lo toda 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]

Quando você calcula cada sequência com menos de um milhão, haverá muita repetição no final das seqüências. A memorização torna uma pesquisa rápida na tabela de hash para valores anteriores, em vez de precisar tornar a pilha cada vez mais profunda.

Estou surpreso que ninguém tenha mencionado trampolim ainda. Um trampolim (nesse sentido) é um loop que invoca iterativamente funções de retorno de thunk (estilo de passagem de continuação) e pode ser usado para implementar chamadas de função recursivas de cauda em um idioma de programação orientado a pilha.

Esta questão do StackOverflow entra em detalhes um pouco mais sobre várias implementações de trampolins em Java: Manipulando StackOverflow em Java para Trampolim

Se você estiver usando um idioma e um compilador que reconheça as funções recursivas da cauda e as manipule adequadamente (por exemplo, "substitui o chamador no lugar pelo chamado"), então sim, a pilha não deve ficar fora de controle. Essa otimização reduz essencialmente um método recursivo a um método iterativo. Não acho que Java faça isso, mas sei que o Racket faz.

Se você adota uma abordagem iterativa, em vez de uma abordagem recursiva, está removendo grande parte da necessidade de lembrar de onde as chamadas são originadas e praticamente eliminando a chance de um estouro de pilha (de qualquer maneira, de chamadas recursivas).

A memorização é excelente e pode reduzir o número geral de chamadas de método, procurando resultados calculados anteriormente em um cache, já que seu cálculo geral incorrerá em muitos cálculos menores e repetidos. Essa ideia é ótima - também é independente de você estar ou não usando uma abordagem iterativa ou recursiva.

você pode criar uma enumeração que substituirá a recursão ... aqui está um exemplo para o cálculo da faculdade que faz isso ... (não funcionará para grandes números, como eu usei apenas por muito tempo no exemplo :-))

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++;
        }
    }
}

mesmo que isso não seja memorização, você anulará um estouro de pilha

EDITAR

Sinto muito por incomodar alguns de vocês. Minha única intenção era mostrar uma maneira de evitar um estouro de pilha. Provavelmente eu deveria ter escrito um exemplo de código completo, em vez de apenas um pequeno trecho de um trecho de código rapidamente escrito e aproximado.

O código a seguir

• evita recursão enquanto uso, calcule os valores necessários iterativamente.
• inclui memorização, pois os valores já calculados são armazenados e recuperados, se já calculados
• também inclui um cronômetro, para que você possa ver que a memorização funciona corretamente

... umm ... se você executá-lo, certifique-se de definir sua janela do shell de comando para ter um buffer de 9999 linhas ... os 300 habituais não serão suficientes para executar os resultados do programa abaixo ...

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 variável estática "instance" na classe Faculty como uma loja como um singleton. Dessa forma, enquanto seu programa estiver em execução, sempre que você "GetInstance ()" da classe, obtém a instância que armazenou todos os valores já calculados. * 1 SortedList estático que conterá todos os valores já calculados

No construtor, também adiciono 2 valores especiais da lista 1 para as entradas 0 e 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;

        }
    }
}

Quanto ao Scala, você pode adicionar a @tailrecanotação a um método recursivo. Dessa forma, o compilador garante que a otimização da chamada de cauda realmente ocorra:

Portanto, isso não será compilado (fatorial):

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

a mensagem de erro é:

scala: não foi possível otimizar o método anotado @tailrec fak1: contém uma chamada recursiva que não está na posição final

Por outro 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ções e otimização de chamada de cauda ocorreu.

Uma possibilidade que ainda não foi mencionada é ter recursão, mas sem usar uma pilha do sistema. É claro que você também pode estourar sua pilha, mas se seu algoritmo realmente precisar voltar atrás de uma forma ou de outra (por que usar a recursão?), Você não terá escolha.

Existem implementações sem pilha de algumas linguagens, por exemplo, Stackless Python .

Outra solução seria simular sua própria pilha e não confiar na implementação do compilador + tempo de execução. Essa não é uma solução simples nem rápida, mas teoricamente você obterá o StackOverflow somente quando estiver com falta de memória.