Переполнение стека из глубокой рекурсии в Java?

увеличение размера стека будет служить только в качестве временной повязки. Как указывали другие, то, что вы действительно хотите, - это устранение хвостового вызова, и Java не имеет этого по разным причинам. Тем не менее, вы можете обмануть, если хотите.

Красная таблетка в руке? Хорошо, сюда, пожалуйста.

есть способы, которыми вы можете обменять стек на кучу. Например, вместо рекурсивного вызова внутри функции, пусть она возвращает a ленивый структура данных что делает вызов при оценке. Затем вы можете размотать "стек" с помощью Java for-construct. Я продемонстрирую на примере. Рассмотрим этот код Хаскелла:

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

обратите внимание, что эта функция не оценивает хвосте списка. Так что функция на самом деле не нужно делать рекурсивный вызов. В Haskell он фактически возвращает подумать для хвоста, который называется, если он когда-нибудь понадобится. Мы можем сделать то же самое в Java (для этого используются классы функциональные 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);}});}

отметим, что Stream<A> состоит из значения типа A и значение типа P1 который похож на thunk, который возвращает остальную часть потока при вызове _1 (). Хотя это, конечно, выглядит как рекурсия, рекурсивный вызов map не выполняется, но становится частью структуры данных потока.

это может быть размотано с помощью обычного for-construct.

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

вот еще один пример, так как вы говорили о проекте Эйлер. Эта программа использует взаимно рекурсивные функции и не взрывает стек, даже для миллионов вызовов:

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

еще одна вещь, которую вы можете сделать для обмена стека на кучу, - это использовать несколько потоков. Идея заключается в том, что вместо рекурсивного вызова,вы создаете thunk, который делает вызов, передаете этот thunk новому потоку и позволяете текущему потоку выйти из функции. это идея, стоящая за такими вещами, как Stackless Питон.

ниже приведен пример этого в Java. Извиняюсь, что это немного непрозрачно смотреть без 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 поддерживается пулом потоков, а promise функция передает удар в пул потоков, возвращая Promise, что очень похоже на java.util.concurrent.Future, только лучше. см. здесь. дело в том, что метод выше складывает правую рекурсивную структуру данных вправо в стеке O(1), которым обычно требуется устранение хвостового вызова. Таким образом, мы эффективно достигли TCE, в обмен на некоторую сложность. Эту функцию можно вызвать следующим образом:

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

обратите внимание, что этот последний метод отлично работает для нелинейной рекурсии. То есть, он будет работать в постоянном стеке даже алгоритмы, которые не имеют хвостовых вызовов.

еще одна вещь, которую вы можете сделать, это использовать технику под названием Прыжки на батуте. Батут-это вычисление, воплощенное в виде данных структура, которую можно шагнуть до конца. Элемент функциональная библиотека Java включает в себя Trampoline тип данных, который я написал, что эффективно позволяет превратить любой вызов функции в хвостовой вызов. В качестве примера вот это батут foldRightC что складывается вправо в постоянный стек:

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

это тот же принцип, что и использование нескольких потоков, за исключением того, что вместо вызова каждого шага в своем собственном потоке мы строим каждый шаг на куча, очень похоже на использование Stream, а затем мы запускаем все шаги в один цикл с Trampoline.run.

Это зависит от JVM, следует ли использовать хвостовую рекурсию - я не знаю, навскидку ли кто-либо из них, но вы не должны полагаться на это. В частности, изменение размера стека будет очень редко бывает правильным, если у вас нет жесткого ограничения на то, сколько уровней рекурсии вы действительно используете, и вы точно знаете, сколько места в стеке займет каждый. Очень хрупкая.

в принципе, вы не должны использовать неограниченную рекурсию в языке, который не является стройте для него. Боюсь, вам придется использовать итерацию вместо этого. И да, иногда это может быть небольшая боль: (

Если вы должны спросить, вы, вероятно, делаете что-то неправильно.

теперь, хотя вы, вероятно, можете найти способ увеличить стек по умолчанию в java, позвольте мне просто добавить мои 2 цента в том, что вам действительно нужно найти другой способ сделать то, что вы хотите сделать, вместо того, чтобы полагаться на увеличенный стек.

поскольку спецификация java не делает обязательным для JVM реализацию методов оптимизации хвостовой рекурсии, единственный способ обойти эту проблему-уменьшить давление стека, либо путем уменьшения количества локальных переменных / параметров, которые необходимо отслеживать, либо в идеале просто значительно снизить уровень рекурсии, либо просто переписать без рекурсии вообще.

большинство функциональных языков поддерживает хвостовую рекурсию. Однако, большинство компиляторов Java не поддерживает. Вместо этого он делает другой вызов функции. Это означает, что всегда будет верхняя граница количества рекурсивных вызовов, которые вы можете сделать (так как в конечном итоге у вас закончится пространство стека).

с помощью хвостовой рекурсии вы повторно используете кадр стека рекурсивной функции, поэтому у вас нет одинаковых ограничений на стек.

вы можете установить это в командной строке:

java-xss8m class

Clojure, который работает на виртуальной машине Java, очень хотел бы реализовать оптимизацию хвостового вызова, но он не может из-за ограничения в байт-коде JVM (я не знаю подробностей). Как следствие, он может помочь только с помощью специальной формы "recur", которая реализует несколько основных функций, которые вы ожидаете от правильной хвостовой рекурсии.

в любом случае, это означает, что JVM в настоящее время не может поддержка оптимизации хвостового вызова. Я бы настоятельно рекомендовал не использовать рекурсию как общая петлевая конструкция на JVM. Мое личное мнение заключается в том, что Java не является достаточно высоким уровнем языка.

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

Я столкнулся с той же проблемой, и в конечном итоге перезапись рекурсии в for-loop и это сделало трюк.

в eclipse если вы используете, установите -xss2m как аргументы vm.

или

-xss2m непосредственно в командной строке.

java -xss2m classname