Aumentar el tamaño de la pila solo servirá como un vendaje temporal. Como han señalado otros, lo que realmente quieres es la eliminación de llamadas de cola, y Java no tiene esto por varias razones. Sin embargo, puedes hacer trampa si quieres.
¿Pastilla roja en la mano? OK, de esta manera por favor.
Hay formas en que puede intercambiar pila por pila. Por ejemplo, en lugar de realizar una llamada recursiva dentro de una función, devuelva estructura de datos vagos que realiza la llamada cuando se evalúa. A continuación, puede desenrollar la "pila" con Java for-construct. Lo demostraré con un ejemplo. Considere este código de Haskell:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs
Tenga en cuenta que esta función nunca evalúa el final de la lista. Entonces, la función en realidad no necesita hacer una llamada recursiva. En Haskell, en realidad devuelve un thunk para la cola, que se llama si alguna vez se necesita. Podemos hacer lo mismo en Java (esto usa las clases de 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);}});}
Tenga en cuenta que Stream<A> consiste en un valor de tipo A y un valor de tipo P1 que es como un golpe seco que devuelve el resto de la transmitir cuando se llama _1(). Aunque ciertamente parece una recursión, la llamada recursiva al mapa no se hace, sino que se convierte en parte de la estructura de datos de Stream.
Esto se puede desenrollar con un for-build normal.
for (Stream<B> b = bs; b.isNotEmpty(); b = b.tail()._1())
{System.out.println(b.head());}
Aquí hay otro ejemplo, ya que hablabas Proyecto Euler. Este programa utiliza funciones mutuamente recursivas y no toca la pila, incluso para millones de llamadas:
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())));}}
Otra cosa que puede hacer para cambiar la pila de pila es el uso de múltiples hilos . La idea es que en lugar de hacer una llamada recursiva, crees un thunk que realiza la llamada, transfiere este thunk a un nuevo hilo y deja que el hilo actual salga de la función. Esta es la idea detrás de cosas como Stackless Python.
El siguiente es un ejemplo de eso en Java. Disculpas que es un poco opaco a mirar sin los import static cláusulas:
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 está respaldado por un grupo de subprocesos, y la función promise manos de un golpe seco a la agrupación de hebras, devolviendo un Promise, que es muy parecido java.util.concurrent.Future, solo que mejor. See here. El punto es que el método anterior dobla una estructura de datos recursiva a la derecha en O (1) pila, que ordinariamente requiere la eliminación de la llamada final. Así que efectivamente hemos logrado TCE, a cambio de cierta complejidad. Se podría llamar a esta función de la siguiente manera:
Strategy<Unit> s = Strategy.simpleThreadStrategy();
int x = foldRight(s, Integers.add, List.nil(), range(1, 10000)).claim();
System.out.println(x); // 49995000
Tenga en cuenta que esta última técnica funciona perfectamente bien para la recursividad no lineal. Es decir, se ejecutará en algoritmos de pila constante que no tienen llamadas de cola.
Otra cosa que puede hacer es emplear una técnica llamada trampolín. Un trampolín es un cálculo, reificado como una estructura de datos, que se puede atravesar. El Functional Java library incluye un tipo de datos Trampoline que escribí, que efectivamente le permite convertir cualquier llamada de función en una llamada final. Como un ejemplo here is a trampolined foldRightC that folds to the right in constant stack:
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()));}});}
Es el mismo principio que el uso de múltiples hilos, excepto que en lugar de invocar cada paso en su propio hilo, construimos cada paso en el montón, muy parecido usando un Stream, y luego ejecutar todos los pasos en un solo bucle con Trampoline.run.
Esto le puede dar más niveles, pero el tamaño de la pila sigue siendo limitado. No podrá recurrir infinitamente como en un lenguaje funcional con la eliminación de llamadas altas. – Chuck
realmente no es una respuesta ... solución de ayuda de banda –
El enlace está roto. – free6om