Stack déborde de récursion profond en Java?

Question

Après une certaine expérience avec les langages fonctionnels, je commence à utiliser récursion plus en Java -. Mais la langue semble avoir une pile d'appel relativement faible d'environ 1000

Y at-il un moyen de rendre la pile plus appel? Comme je peux faire des fonctions qui sont des millions d'appels en profondeur, comme dans Erlang?

Je remarque cela de plus en plus quand je fais des problèmes Projet d'Euler.

Merci.

Answer 1

Je suppose que vous pouvez utiliser ces paramètres

  

-ss STACKSIZE pour augmenter le natif   taille de la pile ou

     

-oss STACKSIZE pour augmenter la Java   taille de la pile,

     

La taille de la pile par défaut native est 128k,   avec une valeur minimale de 1000 octets.   La taille de la pile java par défaut est 400k,   avec une valeur minimale de 1000 octets.

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

EDIT:

Après avoir lu le premier commentaire (Chuck's), ainsi que re lecture de la question et de lire une autre réponse, comme préciser que encore rapidement i interprété la question comme un simple « taille de la pile d'augmentation ». Je n'allez pas l'intention de dire que vous pouvez avoir des piles infinis, comme dans la programmation fonctionnelle (un paradigme de programmation qui ne se gratta sa Ive surface).

Answer 2

L'augmentation de la taille de la pile ne servira un bandage temporaire. Comme d'autres l'ont souligné, ce que vous voulez vraiment est l'élimination d'appel de queue et Java ne dispose pas pour diverses raisons. Cependant, vous pouvez tricher si vous voulez.

pilule rouge à la main? OK, cette façon s'il vous plaît.

Il y a des façons dont vous pouvez échanger pile pour tas. Par exemple, au lieu de faire un appel récursif au sein d'une fonction, il a un retour paresseux structure de données qui fait l'appel lors de l'évaluation. Vous pourrez ensuite vous détendre la « pile » avec Java est pour-construction. Je démontrerai un exemple. Considérez ce code Haskell:

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

Notez que cette fonction n'évalue la queue de la liste. Ainsi, la fonction n'a pas besoin réellement de faire un appel récursif. Dans Haskell, il retourne en fait un thunk pour la queue, qui est appelée si elle est toujours nécessaire. Nous pouvons faire la même chose en Java (celui-ci utilise les classes de Java fonctionnelle):

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

Notez que Stream<A> se compose d'une valeur de type A et une valeur de type P1 qui ressemble à un bruit sourd qui renvoie le reste du courant est appelé lorsque _1 (). Bien qu'il ressemble certainement récursivité, l'appel récursif à la carte ne se fait pas, mais devient une partie de la structure de données de flux.

Cela peut ensuite être dénouée avec un régulier-construction.

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

Voici un autre exemple, puisque vous parliez du projet Euler. Ce programme utilise les fonctions mutuellement récursives et ne souffle pas la pile, même pour des millions d'appels:

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())));}}

Une autre chose que vous pouvez faire pour échanger pile pour tas est d'utiliser plusieurs threads . L'idée est qu'au lieu de faire un appel récursif, vous créez un thunk qui fait appel à la main cette thunk hors d'un nouveau thread et laisser la sortie de thread courant la fonction. Telle est l'idée derrière les choses comme Stackless Python.

Ce qui suit est un exemple de ce en Java. Toutes mes excuses qu'il est un peu opaque de regarder sans les clauses 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 est soutenu par un pool de threads, et la fonction mains un thunk promise à la piscine de fil, un retour Promise, ce qui est très semblable à java.util.concurrent.Future, mais en mieux. Voir ici. Le point est que la méthode ci-dessus replie une structure de données récursive droit vers la droite en O (1) pile , ce qui nécessite habituellement l'élimination d'appel de queue. Nous avons donc effectivement achived TCE, en échange d'une certaine complexité. Vous appelez cette fonction comme suit:

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

Notez que cette dernière technique fonctionne parfaitement bien pour la récursivité non linéaire. Autrement dit, il se déroulera dans la pile constante même des algorithmes qui n'ont pas les appels de la queue.

Une autre chose que vous pouvez faire est employer une technique appelée trampolining . Un trampoline est un calcul, réifiée comme une structure de données, qui peut être renforcé par le biais. comprend un Trampoline type de données que j'ai écrit, ce qui vous permet de transformer efficacement un appel de fonction en un appel de queue. À titre d'exemple ici est un trampolined foldRightC qui se replie vers la droite dans la pile constant:

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()));}});}

Il est le même principe que l'utilisation de plusieurs threads, sauf qu'au lieu d'invoquer chaque étape dans son propre fil, on construit chaque étape sur le tas, très semblable à l'aide d'un Stream, puis nous courons toutes les étapes d'un boucle unique avec Trampoline.run.

Answer 3

Il est à la machine virtuelle Java ou non utiliser la récursivité queue - Je ne sais pas si une désinvolture d'entre eux, mais vous ne devriez pas compter sur elle. En taille particulière, changer la pile serait très est rarement la bonne chose à faire, à moins que vous aviez une certaine limite stricte du nombre de niveaux de récursivité vous utilisez réellement, et vous saviez exactement comment beaucoup d'espace de pile chaque prendrait. Très fragile.

En fait, vous ne devriez pas utiliser la récursivité dans une langue sans borne qui est construit pas pour elle. Vous devrez utiliser l'itération à la place, j'ai peur. Et oui, cela peut être une légère douleur parfois: (

Answer 4

Si vous devez demander, vous faites probablement quelque chose mal .

Maintenant, alors que vous pouvez probablement trouver un moyen d'augmenter la pile par défaut en java, laissez-moi ajouter mes 2 cents que vous avez vraiment besoin de trouver une autre façon de faire ce que vous voulez faire, au lieu de compter sur une augmentation de empiler.

Depuis la spécification Java ne permet pas obligatoire pour JVM pour mettre en œuvre des techniques d'optimisation récursion queue, la seule façon de contourner le problème est de réduire la pression de la pile, soit en réduisant le nombre de variables / paramètres locaux qui ont besoin être suivi gardé, ou idéalement en réduisant simplement le niveau de récursivité de manière significative, ou tout simplement réécrire sans récursion du tout.

Answer 5

langues les plus fonctionnels ont un soutien pour la récursivité queue. Cependant, la plupart des compilateurs Java ne prennent pas en charge cela. Au contraire, il fait un autre appel de fonction. Cela signifie qu'il y aura toujours une limite supérieure du nombre d'appels récursifs que vous pouvez faire (comme vous finirez par manquer d'espace de pile).

Avec la récursivité queue vous réutilisez le cadre de pile de la fonction qui est récursion, de sorte que vous n'avez pas les mêmes contraintes sur la pile.

Answer 6

Vous pouvez régler cela sur la ligne de commande:

classe java -Xss8M

Answer 7

Clojure, qui fonctionne sur la machine virtuelle Java, aimerait bien mettre en œuvre l'optimisation des appels de queue, mais il ne peut pas en raison d'une restriction dans le bytecode JVM (je ne connais pas les détails). En conséquence, il ne peut s'aider à une forme particulière « se reproduire », qui met en œuvre quelques fonctionnalités de base que vous attendez d'récursion de queue appropriée.

En tout cas, cela signifie que la machine virtuelle Java actuellement ne peut pas support optimisation des appels récursifs. Je suggère fortement de ne pas utiliser la récursivité comme une construction générale de mise en boucle sur la machine virtuelle Java. Mon opinion personnelle est que Java est pas une langue de niveau suffisamment élevé.

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

Je suis tombé sur le même problème, et a fini par réécrire la récursion dans une boucle for et qui a fait l'affaire.

Answer 10

Eclipse si vous utilisez, définissez -xss2m comme arguments vm.

ou

-xss2m directement sur commandline.

java -xss2m classname