java - Java中的深度递归导致堆栈溢出？

Question

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

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

当我做 Project Euler 问题时，我越来越注意到这一点。

谢谢。

Answer 1

增加堆栈大小只会作为临时绷带。正如其他人所指出的那样，您真正想要的是消除尾调用，而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 传递给线程池，返回 a Promise，这非常像java.util.concurrent.Future，只是更好。看这里。关键是上面的方法在 O(1) stack 中将右递归数据结构折叠到右侧，这通常需要消除尾调用。因此，我们有效地实现了 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 库包含我编写的一种数据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()));}});}

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

Answer 2

我想你可以使用这些参数

-ss Stacksize 增加本机堆栈大小或

-oss Stacksize 增加 Java 堆栈大小，

默认的本机堆栈大小为 128k，最小值为 1000 字节。默认的 java 堆栈大小为 400k，最小值为 1000 字节。

http://edocs.bea.com/wls/docs61/faq/java.html#251197

编辑：

在阅读了第一条评论（Chuck´s）以及重新阅读问题并阅读了另一个答案之后，我想澄清一下我将这个问题解释为“增加堆栈大小”。我并不打算说你可以拥有无​​限的堆栈，例如在函数式编程中（我只是触及其表面的一种编程范式）。

Answer 3

是否使用尾递归取决于 JVM - 我不知道它们中的任何一个是否使用，但你不应该依赖它。特别是，更改堆栈大小很少是正确的做法，除非您对实际使用的递归级别有一些硬性限制，并且您确切知道每个级别会占用多少堆栈空间。非常脆弱。

基本上，您不应该在不是为它构建的语言中使用无限递归。恐怕您将不得不使用迭代。是的，有时这可能会有点痛苦:(

Answer 4

如果你不得不问，你可能做错了什么。

现在，虽然您可能可以找到一种方法来增加 java 中的默认堆栈，但让我添加我的 2 美分，因为您确实需要找到另一种方法来做您想做的事情，而不是依赖增加的堆栈。

由于 java 规范没有强制要求 JVM 实现尾递归优化技术，解决这个问题的唯一方法是减少堆栈压力，或者通过减少需要保留的局部变量/参数的数量跟踪，或者理想情况下只是显着降低递归级别，或者根本不进行递归重写。

Answer 5

大多数函数式语言都支持尾递归。但是，大多数 Java 编译器不支持这一点。相反，它会进行另一个函数调用。这意味着您可以进行的递归调用的数量总是有一个上限（因为您最终会用完堆栈空间）。

使用尾递归，您可以重用正在递归的函数的堆栈框架，因此您对堆栈没有相同的约束。

Answer 6

您可以在命令行上进行设置：

java -Xss8M 类

Answer 7

运行在 Java VM 上的 Clojure 非常想实现尾调用优化，但由于 JVM 字节码的限制（我不知道细节），它不能。因此，它只能通过一种特殊的“递归”形式来帮助自己，它实现了一些您期望从正确的尾递归中获得的基本功能。

无论如何，这意味着 JVM 目前无法支持尾调用优化。我强烈建议不要将递归用作 JVM 上的一般循环结构。我个人的观点是，Java 不是一种足够高级的语言。

Answer 8

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 F<List<A>, P1<Promise<B>>>()
        {
             public Promise<B> f(List<A> l)
             {
                 return foldRight(s, f, b, l);
             }
         }.f(as.tail())));
}

Answer 9

我遇到了同样的问题，最后将递归重写为一个 for 循环，这就成功了。

Answer 10

如果您正在使用 Eclipse，请将-xss2m设置为 vm 参数。

或者

-xss2m 直接在命令行上。

java -xss2m classname