Java中的深度递归的堆栈溢出？

functional-programming stack java overflow

2022-08-31 19:40:27

在函数式语言方面有一些经验之后，我开始在Java中更多地使用递归 - 但是该语言似乎有一个相对浅的调用堆栈，大约1000。

有没有办法使调用堆栈更大？就像我能像在Erlang中那样，使数百万次调用深度的函数吗？

当我做欧拉项目问题时，我越来越注意到这一点。

谢谢。

答案 1

增加堆栈大小只能用作临时绷带。正如其他人所指出的，你真正想要的是尾部调用消除，而Java由于各种原因没有这个。但是，如果您愿意，您可以作弊。

红色药丸在手里？好的，请这样。

您可以通过多种方式将堆栈交换为堆。例如，与其在函数中进行递归调用，不如让它返回一个在计算时进行调用的惰性数据结构。然后，您可以使用Java的for-construct展开“堆栈”。我将通过一个示例进行演示。考虑以下 Haskell 代码：

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);}});}

请注意，它由一个 type 值和一个 type 值组成，该值类似于在调用 _1（）时返回流的其余部分的 thunk。虽然它看起来像递归，但对map的递归调用并没有进行，而是成为Stream数据结构的一部分。Stream<A>AP1

然后可以使用常规的 for-construct 将其展开。

for (Stream<B> b = bs; b.isNotEmpty(); b = b.tail()._1())
  {System.out.println(b.head());}

这是另一个例子，因为你正在谈论欧拉计划。该程序使用相互递归函数，即使对于数百万次调用，也不会破坏堆栈：

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由线程池支持，函数将一个 thunk 交给线程池，返回一个，这很像，只是更好。请参阅此处。关键是上面的方法在O（1）堆栈中将右递归数据结构折叠到右侧，这通常需要尾部调用消除。因此，我们有效地实现了TCE，以换取一些复杂性。您可以按如下方式调用此函数：promisePromisejava.util.concurrent.Future

Strategy<Unit> s = Strategy.simpleThreadStrategy();
int x = foldRight(s, Integers.add, List.nil(), range(1, 10000)).claim();
System.out.println(x); // 49995000

请注意，后一种技术非常适合非线性递归。也就是说，它将在常量堆栈中运行，即使没有尾部调用的算法也是如此。

你可以做的另一件事是采用一种叫做蹦床的技术。蹦床是一种计算，作为数据结构重新化，可以单步执行。函数式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()));}});}

这与使用多个线程的原理相同，不同之处在于，我们不是在自己的线程中调用每个步骤，而是在堆上构造每个步骤，非常类似于使用，然后使用在单个循环中运行所有步骤。StreamTrampoline.run

答案 2

我想你可以使用这些参数