La pile déborde d'une récursivité profonde en Java?

Question

Après quelques expériences avec les langages fonctionnels, je commence à utiliser davantage la récursivité en Java - mais le langage semble avoir une pile d'appels relativement peu profonde d'environ 1 000.

Y a-t-il un moyen de rendre la pile d'appels plus grande? Comme puis-je créer des fonctions qui comptent des millions d’appels, comme dans Erlang?

Je le remarque de plus en plus quand je fais des problèmes avec Project Euler.

Merci.

Answer 1

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

Pilule rouge dans la main? OK, cette manière s'il vous plaît.

Il ya des façons dont vous pouvez échanger la pile pour tas. Par exemple, au lieu de faire un appel récursif à l'intérieur d'une fonction, de retour d'un paresseux discbased qui fait de l'appel au moment de l'évaluation. Vous pourrez ensuite vous détendre la "pile" avec Java pour construire. Je vais le démontrer par un exemple. Considérer ce code Haskell:

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

Notez que cette fonction ne jamais évalue la queue de la liste. Si la fonction n'a pas vraiment besoin de faire un appel récursif. En Haskell, il retourne en fait un thunk pour la queue, qui est appelé si c'est nécessaire. Nous pouvons faire la même chose en Java (ce qui utilise des classes à partir Fonctionnel 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);}});}

Notez que Stream<A> consiste en une valeur de type A et une valeur de type P1 qui est comme un thunk qui renvoie le reste du flux lorsque _1() est appelée. Bien qu'il ressemble certainement la récursivité, l'appel récursif de la carte n'est pas faite, mais devient une partie du Flux de discbased.

Cela peut ensuite être déroulés avec un régulier pour-construire.

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

Voici un autre exemple, puisque vous parlions 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 l'échange de la pile pour le segment 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 l'appel, à la main cette thunk un nouveau fil de discussion et de laisser le thread courant de sortie de la fonction.

Ce qui suit est un exemple de cela. Les excuses qu'il est un peu opaque à regarder sans le import static clauses: voir ici en contexte

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

Strategy<Unit> s , soutenu par un pool de threads, et l' promise fonction mains d'un thunk pour le pool de threads, de retour d'un Promise, ce qui est très bien comme java.util.concurrent.Future, mais en mieux. Voir ici. Le point est que la méthode ci-dessus les plis d'un droit récursive discbased à droite en O(1) de la pile, qui normalement nécessite la queue-appel d'élimination. Donc, nous avons effectivement reçu le 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 pour les non-linéaire de la récursivité. C'est, il sera exécuté en constante pile de même des algorithmes qui n'ont pas de queue appels.

Une autre chose que vous pouvez faire est d'employer une technique appelée le trampoline. Un trampoline est un calcul, réifiée comme une structure de données, qui peut être franchi. La Fonctionnelle de la bibliothèque Java comprend un Trampoline type de données que j'ai écrit, ce qui vous permet de transformer n'importe quel appel de fonction dans une queue d'appel. Comme un exemple ici est un trampolined foldRightC que les plis à droit constant de la pile:

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

C'est le même principe que l'utilisation de plusieurs threads, sauf qu'au lieu d'invoquer chaque étape dans son propre thread, nous construisons chaque étape sur le tas, très semblable à l'aide d'un Stream, et puis nous avons l'exécution de toutes les étapes en une seule boucle avec Trampoline.run.

Answer 2

Je suppose que vous pourriez utiliser ces paramètres

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

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

Le natif par défaut la taille de la pile est 128k, avec une valeur minimale de 1000 octets. Java par défaut la taille de la pile 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 (Plateaux), ainsi que la lecture de la question et de lire les réponses, id tiens à préciser que j'ai interprété la question comme juste "augmenter la taille de la pile". Je n'ai pas l'intention de dire que vous pouvez avoir un infini piles, comme dans la programmation fonctionnelle (un paradigme de programmation qui ive fait qu'effleurer sa surface).

Answer 3

C'est à la JVM de savoir si ou de ne pas utiliser la récursivité tail - je ne sais pas désinvolte, si l'un d'entre eux, mais vous ne devriez pas compter sur elle. En particulier, la modification de la taille de la pile serait très rarement être la bonne chose à faire, sauf si vous avez déjà eu une dure limite du nombre de niveaux de récursivité vous réellement utiliser, et vous savait exactement comment beaucoup d'espace de pile de chaque de prendre. Très fragile.

En fait, vous ne devriez pas utiliser la surabondance de la récursivité dans une langue qui n'est pas construit pour elle. Vous aurez à utiliser une itération au lieu de cela, j'en ai peur. Et oui, cela peut être une légère douleur, parfois :(

Answer 4

Si vous vous posez, vous êtes probablement fait quelque chose de mal.

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

Depuis la java spec n'est pas obligatoire pour la JVM est de mettre en œuvre la queue de la récursivité des techniques d'optimisation, le seul moyen de contourner le problème est de réduire la pile de la pression, soit en réduisant le nombre de variables locales et les paramètres qui doit être gardé la trace d'un, ou de préférence par seulement de réduire le niveau de récursion de manière significative, ou tout simplement réécrire sans récursivité.

Answer 5

La plupart des langages fonctionnels prennent en charge la récursion de la queue. Cependant, la plupart des compilateurs Java ne le supportent pas. Au lieu de cela, il fait un autre appel de fonction. Cela signifie qu'il y aura toujours une limite supérieure sur le nombre d'appels récursifs que vous pouvez faire (car vous manquerez éventuellement d'espace de pile).

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