После некоторого опыта работы с функциональными языками я начинаю использовать рекурсию больше в Java. Но у языка, кажется, есть относительно мелкий стек вызовов около 1000.
Есть ли способ увеличить стек вызовов? Как я могу сделать функции, которые являются миллионами вызовов в глубину, например, в Erlang?
Я замечаю это все больше и больше, когда я сталкиваюсь с проблемами Project Euler.
Спасибо.
Я думаю, вы могли бы использовать эти параметры
-ss Стекизировать, чтобы увеличить собственный размер стека или
-oss Стекировать, чтобы увеличить Java размер стека,
Размер основного стека по умолчанию - 128k, с минимальным значением 1000 байтов. Размер пакета java по умолчанию составляет 400 тыс. с минимальным значением 1000 байтов.
http://edocs.bea.com/wls/docs61/faq/java.html#251197
EDIT:
После прочтения первого комментария (Chuck's), а также повторного чтения вопроса и чтения других ответов, я хотел бы уточнить, что я интерпретировал этот вопрос как "увеличить размер стека". Я не собирался говорить, что у вас могут быть бесконечные стеки, например, в функциональном программировании (парадигма программирования, которая только поцарапала ее поверхность).
Увеличение размера стека будет служить лишь временной повязкой. Как указывали другие, то, что вы действительно хотите, - это устранение хвостового вызова, и Java не имеет этого по разным причинам. Однако вы можете обмануть, если хотите.
Красная таблетка в руке? Хорошо, пожалуйста.
Есть способы, с помощью которых вы можете обменивать стек на кучу. Например, вместо того, чтобы делать рекурсивный вызов внутри функции, верните ленивую datastructure, которая делает вызов при оценке. Затем вы можете развернуть "стек" с помощью 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> состоит из значения типа A и значения типа P1, которое похоже на thunk, который возвращает остальную часть потока при вызове _1(). Хотя это, конечно, похоже на рекурсию, рекурсивный вызов карты не производится, но становится частью структуры данных Stream.
Затем его можно разматывать с помощью регулярной для-конструкции.
for (Stream<B> b = bs; b.isNotEmpty(); b = b.tail()._1())
{System.out.println(b.head());}
Вот еще один пример, поскольку вы говорили о Project Euler. Эта программа использует взаимно рекурсивные функции и не взрывает стек даже для миллионов вызовов:
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 Python.
Ниже приведен пример этого в 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 передает thunk в пул потоков, возвращая 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
Заметим, что эта последняя техника отлично работает для нелинейной рекурсии. То есть, он будет работать в постоянных стеках даже алгоритмов, которые не имеют хвостовых вызовов.
Еще одна вещь, которую вы можете сделать, - это использовать метод trampolining. Батут - это вычисление, охарактеризованное как структура данных, которое можно преодолеть. Функциональная библиотека 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 класс
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())));
}
Я столкнулся с той же проблемой и закончил переписывание рекурсии в цикл, и это сделало трюк.
в eclipse, если вы используете, установите -xss2m как аргументы vm.
или
-xss2m непосредственно в командной строке.
java -xss2m classname