Увеличение размера стопки послужит только временной повязкой. Как уже отмечали другие, то, что вам действительно нужно, это исключение хвостовых вызовов, а в Java этого нет по разным причинам. Тем не менее, вы можете обмануть, если хотите.
Красная таблетка в руке? Хорошо, сюда, пожалуйста.
Есть способы, которыми вы можете обменять стек на кучу. Например, вместо того, чтобы делать рекурсивный вызов внутри функции, пусть она возвращает ленивую структуру данных , которая выполняет вызов при оценке. Затем вы можете раскрутить «стек» с помощью for-конструкции Java. Я продемонстрирую на примере. Считайте этот код Хаскеля:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs
Обратите внимание, что эта функция никогда не оценивает хвост списка. Таким образом, функция на самом деле не должна делать рекурсивный вызов. В Haskell он на самом деле возвращает thunk для хвоста, который вызывается, если он когда-либо нужен. Мы можем сделать то же самое в 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 не выполняется, но становится частью структуры данных Stream.
Затем его можно развернуть с помощью обычной for-конструкции.
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 передает поток в пул потоков, возвращая 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
Обратите внимание, что этот последний метод отлично работает для нелинейной рекурсии. То есть он будет работать в постоянном стеке даже в алгоритмах, которые не имеют хвостовых вызовов.
Еще одна вещь, которую вы можете сделать, - это использовать технику под названием 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.