Estouros de pilha do fundo recursão em Java?

Question

Depois de alguma experiência com linguagens funcionais, estou começando a usar recursão mais em Java -. Mas a linguagem parece ter uma pilha de chamadas relativamente rasa de cerca de 1000

Existe uma maneira de fazer a pilha maior chamada? Como eu posso fazer funções que são milhões de chamadas profundo, como em Erlang?

Eu estou percebendo isso mais e mais quando eu faço problemas de projeto Euler.

Graças.

Answer 1

Eu acho que você poderia usar esses parâmetros

-ss STACKSIZE para aumentar o nativo tamanho da pilha ou

-oss STACKSIZE para aumentar o Java tamanho da pilha,

O tamanho da pilha nativa padrão é 128k, com um valor mínimo de 1000 bytes. O tamanho da pilha java padrão é 400k, com um valor mínimo de 1000 bytes.

http://edocs.bea.com/wls/docs61/ faq / java.html # 251197

EDIT:

Depois de ler o primeiro comentário (Chuck's), bem como re lendo a pergunta e lendo mais respostas, eu gostaria de esclarecer que eu interpretei a questão apenas como "tamanho da pilha aumento". I Não sofreu a intenção de dizer que você pode ter pilhas infinitas, como na programação funcional (um paradigma de programação que só Ive riscado sua superfície).

Answer 2

Aumentar o tamanho da pilha só vai servir como um curativo temporário. Como outros têm para fora pontas, o que você realmente quer é a eliminação chamada cauda, ??e Java não tem isso por várias razões. No entanto, você pode enganar, se quiser.

pílula vermelha na mão? OK, desta forma, por favor.

Existem maneiras em que você pode trocar de pilha para pilha. Por exemplo, em vez de fazer uma chamada recursiva dentro de uma função, tê-lo retornar um datastructure preguiçoso que faz a chamada quando avaliados. Você pode, em seguida, desfazer a "pilha" com Java do para-construção. Vou demonstrar com um exemplo. Considere este código Haskell:

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs

Note que esta função não avalia a cauda da lista. Então, a função não realmente precisa fazer uma chamada recursiva. Em Haskell, ele realmente retorna um conversão para a cauda, ??que é chamado se ele é sempre necessária. Nós podemos fazer a mesma coisa em Java (Isto usa as classes de Funcional Java ):

public <B> Stream<B> map(final F<A, B> f, final Stream<A> as)
  {return as.isEmpty()
     ? nil()
     : cons(f.f(as.head()), new P1<Stream<A>>()
         {public Stream<A> _1()
           {return map(f, as.tail);}});}

Note que Stream<A> consiste em um valor do tipo A e um valor do tipo P1 que é como uma conversão que retorna o resto do fluxo quando _1 () é chamado. Embora certamente se parece com recursividade, a chamada recursiva ao mapa não é feito, mas torna-se parte da estrutura de dados Stream.

Este pode então ser desenrolado com um para-construção regular.

for (Stream<B> b = bs; b.isNotEmpty(); b = b.tail()._1())
  {System.out.println(b.head());}

Aqui está outro exemplo, uma vez que você estava falando sobre o Projeto Euler. Este programa usa funções mutuamente recursivas e não tocar a pilha, mesmo para milhões de chamadas:

import fj.*; import fj.data.Natural;
import static fj.data.Enumerator.naturalEnumerator;
import static fj.data.Natural.*; import static fj.pre.Ord.naturalOrd;
import fj.data.Stream; import fj.data.vector.V2;
import static fj.data.Stream.*; import static fj.pre.Show.*;

public class Primes
  {public static Stream<Natural> primes()
    {return cons(natural(2).some(), new P1<Stream<Natural>>()
       {public Stream<Natural> _1()
         {return forever(naturalEnumerator, natural(3).some(), 2)
                 .filter(new F<Natural, Boolean>()
                   {public Boolean f(final Natural n)
                      {return primeFactors(n).length() == 1;}});}});}

   public static Stream<Natural> primeFactors(final Natural n)
     {return factor(n, natural(2).some(), primes().tail());}

   public static Stream<Natural> factor(final Natural n, final Natural p,
                                        final P1<Stream<Natural>> ps)
     {for (Stream<Natural> ns = cons(p, ps); true; ns = ns.tail()._1())
          {final Natural h = ns.head();
           final P1<Stream<Natural>> t = ns.tail();
           if (naturalOrd.isGreaterThan(h.multiply(h), n))
              return single(n);
           else {final V2<Natural> dm = n.divmod(h);
                 if (naturalOrd.eq(dm._2(), ZERO))
                    return cons(h, new P1<Stream<Natural>>()
                      {public Stream<Natural> _1()
                        {return factor(dm._1(), h, t);}});}}}

   public static void main(final String[] a)
     {streamShow(naturalShow).println(primes().takeWhile
       (naturalOrd.isLessThan(natural(Long.valueOf(a[0])).some())));}}

Outra coisa que você pode fazer para pilha troca de pilha é usar vários segmentos . A idéia é que em vez de fazer uma chamada recursiva, você cria uma conversão que faz a chamada, entregar este conversão fora a um novo segmento e deixe a corrente saída de segmento a função. Esta é a idéia por trás das coisas como Stackless Python.

A seguir é um exemplo de que em Java. Desculpas que é uma opaca pouco para olhar sem as cláusulas import static:

public static <A, B> Promise<B> foldRight(final Strategy<Unit> s,
                                          final F<A, F<B, B>> f,
                                          final B b,
                                          final List<A> as)
  {return as.isEmpty()
     ? promise(s, P.p(b))
     : liftM2(f).f
         (promise(s, P.p(as.head()))).f
         (join(s, new P1<Promise<B>>>()
            {public Promise<B> _1()
              {return foldRight(s, f, b, as.tail());}}));}

Strategy<Unit> s é apoiada por um pool de threads, ea função promise mãos uma conversão para o pool de threads, retornando um Promise, que é muito parecido com java.util.concurrent.Future, só que melhor. Veja aqui. O ponto é que o método acima dobras uma estrutura de dados direito recursivo para a direita em o (1) pilha , que normalmente requer a eliminação tail-call. Então, nós temos efetivamente achived TCE, em troca de alguma complexidade. Você poderia chamar esta função da seguinte forma:

Strategy<Unit> s = Strategy.simpleThreadStrategy();
int x = foldRight(s, Integers.add, List.nil(), range(1, 10000)).claim();
System.out.println(x); // 49995000

Note que esta última técnica funciona perfeitamente bem para a recursividade não-linear. Ou seja, ele será executado em constantes pilha mesmo algoritmos que não têm chamadas de cauda.

Outra coisa que você pode fazer é empregar uma técnica chamada trampolim . Um trampolim é um cálculo, reified como uma estrutura de dados, que pode ser reforçada através de. A Funcional biblioteca Java inclui um Trampoline tipo de dados que eu escrevi, o que efetivamente permite transformar qualquer chamada de função em uma chamada de cauda. Como exemplo aqui é um trampolined foldRightC que se dobra à direita na pilha constante:

public final <B> Trampoline<B> foldRightC(final F2<A, B, B> f, final B b)
  {return Trampoline.suspend(new P1<Trampoline<B>>()
    {public Trampoline<B> _1()
      {return isEmpty()
         ? Trampoline.pure(b)
         : tail().foldRightC(f, b).map(f.f(head()));}});}

É o mesmo princípio como a utilização de vários segmentos, exceto que em vez de chamar cada etapa em seu próprio segmento, nósconstruir cada etapa na pilha, muito parecido com um Stream, e então executar todos os passos em um único laço com Trampoline.run.

Answer 3

É até a JVM ou não ao uso cauda recursão - Eu não sei offhand se algum deles fazer, mas você não deve confiar nele. Em particular, mudando o tamanho da pilha que muito raramente ser a coisa certa a fazer, a menos que você teve algum limite rígido de quantos níveis de recursão você realmente usar, e você sabia exatamente quanto espaço de pilha cada ocuparia. Muito frágil.

Basicamente, você não deve usar recursão ilimitada numa língua que não é construir para ele. Você terá que usar iteração em vez disso, eu estou com medo. E sim, isso pode ser uma ligeira dor, por vezes: (

Answer 4

Se você tem que perguntar, você provavelmente está fazendo algo errado .

Agora, enquanto você provavelmente poderá encontrar uma maneira de aumentar a pilha padrão em java, deixe-me apenas adicionar meus 2 centavos no que você realmente precisa encontrar outra maneira de fazer o que você quer fazer, em vez de depender de um aumento pilha.

Uma vez que o java especificação não torná-lo obrigatório para do JVM para implementar técnicas de otimização de cauda-recursão, a única maneira de contornar o problema é reduzir a pressão pilha, quer reduzindo o número de variáveis ??/ parâmetros locais que as necessidades para ser mantido a par, ou, idealmente, apenas por reduzir o nível de recursividade significativamente, ou simplesmente reescrever sem recursão em tudo.

Answer 5

A maioria das linguagens funcionais têm suporte para recursão de cauda. No entanto, a maioria dos compiladores de Java não suportam isso. Em vez disso, fazer uma outra chamada de função. Isto significa que sempre haverá um limite superior no número de chamadas recursivas que você pode fazer (como você eventualmente ficar sem espaço de pilha).

Com a recursão de cauda você reutilizar o quadro de pilha da função que é recursivo, então você não tem as mesmas limitações na pilha.

Answer 6

Você pode definir esta na linha de comando:

java -Xss8M classe

Answer 7

Clojure, que é executado no Java VM, gostaria muito de implementar otimização de chamada de cauda, ??mas não pode devido a uma restrição na bytecode JVM (Eu não sei os detalhes). Como consequência, ele só pode ajudar a si mesmo com um especial "recorrência" forma, que implementa algumas características básicas que você esperaria de recursão de cauda adequada.

De qualquer forma, isto significa que o JVM atualmente não pode suporte chamada cauda otimização. Gostaria de sugerir a não usar recursividade como uma construção looping geral sobre a JVM. Minha opinião pessoal é que o Java não é uma linguagem de nível suficientemente elevado.

Answer 8

public static <A, B> Promise<B> foldRight(final Strategy<Unit> s,
                                          final F<A, F<B, B>> f,
                                          final B b,
                                          final List<A> as)
{
    return as.isEmpty() ? promise(s, P.p(b))
    : liftM2(f).f(promise(s, P.p(as.head())))
      .f(join(s, new F<List<A>, P1<Promise<B>>>()
        {
             public Promise<B> f(List<A> l)
             {
                 return foldRight(s, f, b, l);
             }
         }.f(as.tail())));
}

Answer 9

Eu corri para o mesmo problema, e acabou reescrevendo a recursividade em um loop for e que fez o truque.

Answer 10

no eclipse se você estiver usando, set -xss2m como argumentos vm.

ou

-xss2m diretamente na linha de comando.

java -xss2m classname