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

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

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

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

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

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

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

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

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

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

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

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

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

Стратегия s поддерживается пулом потоков, а функции обещают передают функции преобразователь в пул потоков, возвращающий Promise , который очень похож на java.util.concurrent.Future , только лучше. См. Здесь. Дело в том, что описанный выше метод сворачивает праворекурсивную структуру данных вправо в стеке O (1) , что обычно требует исключения хвостового вызова. Итак, мы Мы эффективно получили ТВК в обмен на некоторые сложности. Вы могли бы вызвать эту функцию следующим образом:

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

Это тот же принцип, что и при использовании нескольких потоков, за исключением того, что вместо вызова каждого шага в отдельном потоке,

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

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

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

java -Xss8M class

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

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