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

A otimização da chamada de cauda está presente em muitos idiomas e compiladores. Nesta 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 que está sendo 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 chamada de cauda otimizável por causa da inspeção necessária no retorno. ( Exemplo de código-fonte e saída compilada )

Para tornar essa chamada 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 este código com gcc -O2 -S fact.c (o -O2 é necessário para permitir 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 , o jne em vez de um call (que faz uma chamada de sub-rotina com um novo quadro de pilha).

Por favor, note que isso foi feito com C. A otimização da chamada tail em Java é difícil e depende da implementação da JVM (que disse, eu não vi nenhum que faça isso, porque é difícil e implicações do modelo de segurança Java necessário requerer quadros de pilha - que é o que o TCO evita) - tail-recursion + java e tail-recursion + optimization são bons conjuntos de tags para navegar. Você pode descobrir que outras linguagens JVM são capazes de otimizar a recursão de cauda (tente clojure (que requer o recorrente para otimizar a chamada de retorno), ou scala).

Dito isto,

Háumacertaalegriaemsaberquevocêescreveualgocorreto-damaneiraidealqueissopodeserfeito.
_{^{Eagora, Vou pegar um scotch e colocar um pouco de eletrônica alemã ...}}

Para a 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 além do controle (e códigos ruins).

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ê cometeu um erro (aqui, apenas um retorno de -1, embora em outras linguagens você possa preferir lançar uma exceção). A ideia é evitar que coisas piores aconteçam (erros de falta de memória) ao fazer uma recursão que é muito mais profunda do que o esperado e, provavelmente, um loop infinito.

Em teoria, você não deveria precisar disso. Na prática, vi um código mal escrito que atingiu isso por causa de uma infinidade de pequenos erros e más práticas de codificação (problemas de simultaneidade multithread onde algo muda algo fora do método que faz com que outro thread entre em um loop infinito de chamadas recursivas).

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

Vocêestácomeçandoemumnúmeroefazendoumatravessiadeárvore.Issolevarapidamenteaumespaçodepesquisamuitogrande.Umaexecuçãorápidaparacalcularonúmerodeiteraçõesparaarespostacorretaresultaemcercade500etapas.Issonãodeveserumproblemapararecursãocomumpequenoquadrodepilha.

Emboraconhecerasoluçãorecursivanãosejaumacoisaruim,tambéméprecisoperceberquemuitasvezesasoluçãoiterativa é melhor . Uma série de maneiras de abordar a conversão de um algoritmo recursivo para um iterativo pode ser vista no Stack Overflow em Caminho a percorrer da recursão à iteração .

Tenha em mente que a implementação da linguagem deve oferecer suporte à otimização de recursão de cauda. Eu não acho que os principais compiladores Java façam.

Memoização significa que você lembra do resultado de um cálculo em vez de recalculá-lo sempre, 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ê está calculando cada sequência de menos de um milhão, haverá muita repetição no final das seqüências. A memorização faz com que seja uma rápida pesquisa na tabela de hash para valores anteriores, em vez de ter que tornar a pilha cada vez mais profunda.

Estou surpreso que ninguém tenha mencionado trampolining 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 linguagem de programação orientada a pilha.

Esta questão do StackOverflow detalha um pouco mais sobre várias implementações de trampolining em Java: Gerenciando StackOverflow em Java para Trampoline

Se você estiver usando uma linguagem e um compilador que reconheçam funções recursivas finais e os manipule corretamente (isto é, "substitui o chamador no local com o callee "), então, sim, a pilha não deve crescer fora de controle. Essa otimização reduz essencialmente um método recursivo para um iterativo. Eu não acho que o Java faça isso, mas eu sei que o Racket faz isso.

Se você usar uma abordagem iterativa, em vez de uma abordagem recursiva, estará removendo muita da necessidade de lembrar de onde as chamadas estão vindo e praticamente eliminando a possibilidade de um estouro de pilha (de chamadas recursivas).

A memorização é ótima e pode reduzir o número total de chamadas de método observando os resultados calculados anteriormente em um cache, já que o cálculo geral acarretará 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ê poderia criar uma Enumeração que substituirá a recursão ... aqui está um exemplo para calcular o corpo docente fazendo isso ... (não vai funcionar para números grandes 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 se isso não for memoization, desta forma você vai anular um estouro de pilha

EDITAR

Me desculpe se eu chateado alguns de vocês. Minha única intenção era mostrar uma maneira de evitar um estouro de pilha. Eu provavelmente deveria ter escrito um exemplo de código completo em vez de apenas uma pequena parte de um trecho de código rapidamente escrito e áspero.

O seguinte código

• evita a recursão conforme eu uso o cálculo dos valores necessários de forma iterativa.
• inclui memoização, pois os valores já calculados são armazenados e recuperados se já tiverem sido calculados
• também inclui um cronômetro, para que você possa ver que a memoização funciona corretamente

... umm ... se você executá-lo, certifique-se de definir sua janela de shell de comando para ter um buffer de 9999 linhas ... o habitual 300 não será suficiente para percorrer 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");
       }
    }

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

No construtor eu 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 anotação @tailrec a um método recursivo. Dessa forma, o compilador garante que a otimização da chamada final realmente ocorreu:

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: could not optimize @tailrec annotated method fak1: it contains a recursive call not in tail position

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 e a otimização da chamada final ocorreu.

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

Existem implementações sem empilhamento de alguns idiomas, por ex. Stackless Python .

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