在对函数式语言有一些经验后,我开始在 Java 中更多地使用递归 - 但该语言的调用堆栈似乎相对较浅,约为 1000。
有没有办法让调用栈变大?就像在 Erlang 中那样,我可以制作数百万次调用的函数吗?
我在做 Project Euler 问题时越来越多地注意到这一点。
谢谢。
最佳答案
增加堆栈大小只会作为临时绷带。正如其他人所指出的那样,您真正想要的是消除尾调用,而Java由于各种原因没有这个。但是,您可以根据需要作弊。
手里拿着红色药丸?好的,请这边走。
您可以通过多种方式将堆栈换成堆。例如,不要在函数内进行递归调用,而是让它返回一个 惰性数据结构,以便在评估时进行调用。然后,您可以使用 Java 的 for-construct 展开“堆栈”。我将用一个例子来演示。考虑这个 Haskell 代码:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs
请注意,此函数从不计算列表的尾部。所以该函数实际上并不需要进行递归调用。在 Haskell 中,它实际上为尾部返回一个 thunk,如果需要,它就会被调用。我们可以在 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() 时返回流的其余部分。虽然它看起来确实像递归,但不会对 map 进行递归调用,而是成为 Stream 数据结构的一部分。
然后可以使用常规的 for-construct 展开。
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
,只有更好。 See here.关键是上面的方法在 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
请注意,后一种技术非常适用于非线性递归。也就是说,即使没有尾调用的算法,它也会在常量堆栈中运行。
您可以做的另一件事是采用一种称为蹦床的技术。蹦床是一种计算,具体化为一种数据结构,可以单步执行。 Functional Java library包括 Trampoline
我编写的数据类型,它可以有效地将任何函数调用转换为尾调用。以 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()));}});}
这与使用多线程的原理相同,只是我们不是在自己的线程中调用每个步骤,而是在堆上构造每个步骤,非常类似于使用 Stream
, 然后我们用 Trampoline.run
在一个循环中运行所有步骤.
关于java - Java中的深度递归导致堆栈溢出?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/860550/