L'aumento delle dimensioni dello stack servirà solo come benda temporanea. Come altri hanno sottolineato, ciò che si vuole veramente è l'eliminazione della coda, e Java non ha questo per vari motivi. Tuttavia, puoi imbrogliare se vuoi.
Pillola rossa in mano? OK, in questo modo per favore.
Ci sono modi in cui è possibile scambiare lo stack per l'heap. Ad esempio, invece di effettuare una chiamata ricorsiva all'interno di una funzione, è necessario restituire una infrastruttura lazy che effettua la chiamata quando viene valutata. È quindi possibile scaricare lo "stack" con for-construct di Java. Dimostrerò con un esempio. Considera questo codice Haskell:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs
Si noti che questa funzione non valuta mai la coda dell'elenco. Quindi la funzione in realtà non ha bisogno di effettuare una chiamata ricorsiva. In Haskell, in realtà restituisce un thunk per la coda, che viene chiamato se è mai necessario. Siamo in grado di fare la stessa cosa in Java (questo utilizza le classi da 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);}});}
noti che Stream<A> è costituito da un valore di tipo A e un valore di tipo P1 che è come un tonfo che restituisce il resto della stream quando viene chiamato _1(). Sebbene sembri certamente una ricorsione, la chiamata ricorsiva alla mappa non viene creata, ma diventa parte della struttura del flusso.
Questo può quindi essere svolto con un normale costrutto.
for (Stream<B> b = bs; b.isNotEmpty(); b = b.tail()._1())
{System.out.println(b.head());}
Ecco un altro esempio, dal momento che si stava parlando di Project Euler. Questo programma utilizza le funzioni ricorsive reciprocamente e non suona lo stack, anche per milioni di chiamate:
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())));}}
Un'altra cosa che potete fare per lo scambio di stack per heap è quello di utilizzare più thread . L'idea è che invece di fare una chiamata ricorsiva, si crea un thunk che effettua la chiamata, si passa questo thunk a un nuovo thread e si lascia che il thread corrente esca dalla funzione. Questa è l'idea alla base di cose come Stackless Python.
Di seguito è riportato un esempio di ciò in Java. Scuse che è un po 'opaco a guardare senza i import static clausole:
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 è sostenuta da un pool di thread, e la funzione promise mani un tonfo al pool di thread, restituendo un Promise, che è molto simile java.util.concurrent.Future, solo meglio. See here. Il punto è che il metodo sopra piega una infrastruttura destra ricorsiva a destra nello stack O (1), che di solito richiede l'eliminazione di coda. Quindi abbiamo effettivamente ottenuto TCE, in cambio di una certa complessità. Si potrebbe chiamare questa funzione come segue:
Strategy<Unit> s = Strategy.simpleThreadStrategy();
int x = foldRight(s, Integers.add, List.nil(), range(1, 10000)).claim();
System.out.println(x); // 49995000
Si noti che quest'ultima tecnica funziona perfettamente bene per non lineare ricorsione. Cioè, verrà eseguito in algoritmi di stack costanti che non hanno chiamate tail.
Un'altra cosa che puoi fare è impiegare una tecnica chiamata trampolino. Un trampolino è un calcolo, reificato come una struttura di dati, che può essere attraversato. Lo Functional Java library include un tipo di dati Trampoline che ho scritto, che consente in effetti di trasformare qualsiasi chiamata di funzione in una coda. Come esempio 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()));}});}
È lo stesso principio utilizzando più thread, salvo che invece di invocare ogni passo nel proprio thread, si costruisce ogni passaggio sul mucchio, molto simile utilizzando un Stream, e poi eseguire tutti i passaggi in un unico ciclo con Trampoline.run.
Questo può darti più livelli, ma le dimensioni dello stack sono ancora limitate. Non sarai in grado di recitare all'infinito come in un linguaggio funzionale con l'eliminazione chiamata alta. – Chuck
non proprio una risposta ... soluzione di aiuto per banda –
Il collegamento è interrotto. – free6om