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

Stack overflows from deep recursion in Java?

提问by Lucky

After some experience with functional languages, I'm starting to use recursion more in Java - But the language seems to have a relatively shallow call stack of about 1000.

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

Is there a way to make the call stack bigger? Like can I make functions that are millions of calls deep, like in Erlang?

有没有办法使调用堆栈更大？就像我可以创建数百万次调用深度的函数，就像在 Erlang 中一样？

I'm noticing this more and more when I do Project Euler problems.

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

Thanks.

谢谢。

采纳答案by Tom

I guess you could use these parameters

我想你可以使用这些参数

-ss Stacksize to increase the native stack size or

-oss Stacksize to increase the Java stack size,

The default native stack size is 128k, with a minimum value of 1000 bytes. The default java stack size is 400k, with a minimum value of 1000 bytes.

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

-oss Stacksize 增加 Java 堆栈大小，

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

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

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

EDIT:

编辑：

After reading the first comment (Chuck′s), as well as re reading the question and reading another answers, i′d like to clarify that i interpreted the question as just "increase stack size". I didn′t intend to say that you can have infinite stacks, such as in functional programming (a programming paradigm which i′ve only scratched its surface).

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

回答by Sean

Most functional languages have support for tail recursion. However, most Java compilers don't support this. Instead it make another function call. This means that there will always be an upper bound on number of recursive calls you can make (as you'll eventually run out of stack space).

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

With tail recursion you reuse the stack frame of the function that is recursing, so you don't have the same constraints on the stack.

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

回答by Jon Skeet

It's up to the JVM whether or not to use tail recursion - I don't know offhand whether any of them do, but you shouldn't rely on it. In particular, changing the stack size would veryrarely be the right thing to do, unless you had some hard limit of how many levels of recursion you would actually use, and you knew exactly how much stack space each would take up. Very fragile.

是否使用尾递归取决于 JVM - 我不知道它们中的任何一个是否这样做，但你不应该依赖它。特别是，改变堆栈大小将非常很少是做正确的事，除非你有你需要多少递归级别实际上使用了硬限制，你知道每个会到底有多少堆栈空间占用。非常脆弱。

Basically, you shouldn't use unbounded recursion in a language which isn't build for it. You'll have to use iteration instead, I'm afraid. And yes, that can be a slight pain sometimes :(

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

回答by Lasse V. Karlsen

If you have to ask, you're probably doing something wrong.

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

Now, while you can probably find a way to increase the default stack in java, let me just add my 2 cents in that you really need to find another way to do what you want to do, instead of relying on an increased stack.

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

Since the java spec doesn't make it mandatory for JVM's to implement tail-recursion optimization techniques, the only way to get around the problem is to reduce the stack pressure, either by reducing the number of local variables/parameters that needs to be kept track of, or ideally by just reducing the level of recursion significantly, or just rewrite without recursion at all.

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

回答by stili

You can set this on the commandline:

您可以在命令行上设置：

java -Xss8M class

java -Xss8M 类

回答by Svante

Clojure, which runs on the Java VM, would very much like to implement tail call optimization, but it can't due to a restriction in the JVM bytecode (I don't know the details). As a consequence, it can only help itself with a special "recur" form, which implements a few basic features you'd expect from proper tail recursion.

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

Anyway, this means that the JVM currently cannotsupport tail call optimization. I would strongly suggest not to use recursion as a general looping construct on the JVM. My personal view is that Java is not a sufficiently high level language.

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

回答by Apocalisp

Increasing the stack size will only serve as a temporary bandage. As others have pointed out, what you really want is tail call elimination, and Java does not have this for various reasons. However, you can cheat if you want.

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

Red pill in hand? OK, this way please.

手里拿着红药丸？好的，这边请。

There are ways in which you can exchange stack for heap. For example, instead of making a recursive call within a function, have it return a lazy datastructurethat makes the call when evaluated. You can then unwind the "stack" with Java's for-construct. I'll demonstrate with an example. Consider this Haskell code:

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

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs

Note that this function never evaluates the tail of the list. So the function doesn't actually need to make a recursive call. In Haskell, it actually returns a thunkfor the tail, which is called if it's ever needed. We can do the same thing in Java (this uses classes from Functional Java):

请注意，此函数从不评估列表的尾部。因此该函数实际上并不需要进行递归调用。在 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);}});}

Note that Stream<A>consists of a value of type Aand a value of type P1which is like a thunk that returns the rest of the stream when _1() is called. While it certainly looks like recursion, the recursive call to map is not made, but becomes part of the Stream datastructure.

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

This can then be unwound with a regular for-construct.

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

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

Here's another example, since you were talking about Project Euler. This program uses mutually recursive functions and does not blow the stack, even for millions of calls:

这是另一个例子，因为你在谈论 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())));}}

Another thing you can do to exchange stack for heap is to use multiple threads. The idea is that instead of making a recursive call, you create a thunk that makes the call, hand this thunk off to a new thread and let the current thread exit the function.This is the idea behind things like Stackless Python.

用堆交换堆栈可以做的另一件事是使用多个线程。这个想法是，不是进行递归调用，而是创建一个进行调用的 thunk，将此 thunk 交给一个新线程并让当前线程退出该函数。这就是 Stackless Python 之类的东西背后的想法。

The following is an example of that in Java. Apologies that it's a bit opaque to look at without the import staticclauses:

以下是 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> sis backed by a thread pool, and the promisefunction hands a thunk to the thread pool, returning a Promise, which is very much like java.util.concurrent.Future, only better. See here.The point is that the method above folds a right-recursive datastructure to the right in O(1) stack, which ordinarily requires tail-call elimination. So we've effectively achived TCE, in exchange for some complexity. You would call this function as follows:

Strategy<Unit> s由线程池支持，该promise函数将一个 thunk 传递给线程池，返回一个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

Note that this latter technique works perfectly well for nonlinear recursion. That is, it will run in constant stack even algorithms that don't have tail calls.

请注意，后一种技术对于非线性递归非常有效。也就是说，即使算法没有尾调用，它也会在常量堆栈中运行。

Another thing you can do is employ a technique called trampolining. A trampoline is a computation, reified as a data structure, that can be stepped through. The Functional Java libraryincludes a Trampolinedata type that I wrote, which effectively lets you turn any function call into a tail call. As an example here is a trampolined foldRightCthat folds to the right in constant stack:

您可以做的另一件事是采用一种称为蹦床的技术。蹦床是一种计算，具体化为一种数据结构，可以单步执行。该功能的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()));}});}

It's the same principle as using multiple threads, except that instead of invoking each step in its own thread, we construct each step on the heap, very much like using a Stream, and then we run all the steps in a single loop with Trampoline.run.

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

回答by test

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

回答by Balaswamy Vaddeman

in eclipse if you are using, set -xss2mas vm arguments.

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

or

或者

-xss2m directly on commandline.

-xss2m 直接在命令行上。

java -xss2m classname

回答by Renaud

I ran into the same problem, and ended up rewriting the recursion into a for-loopand that did the trick.

我遇到了同样的问题，最终将递归重写为一个 for 循环，这解决了问题。