堆栈从Java中深递归溢出？

Question

在与函数式语言的一些经验，我开始使用递归更在Java中 - 但这种语言似乎有大约1000相对较浅的调用堆栈

有没有一种方法，使调用堆栈更大？我就像可以使数以百万计的呼叫深，就像在二郎山功能？

我注意到这个越来越多，当我做项目欧拉问题。

感谢。

Answer 1

我想你可以使用这些参数

  

-ss STACKSIZE增加天然   堆栈大小或

     

-oss STACKSIZE增加了Java   堆栈大小，

     

默认本地堆栈大小为128K，   具有1000个字节的最小值。   默认的Java堆栈大小为400K，   具有1000个字节的最小值。

http://edocs.bea.com/wls/docs61/常见问题/ java.html＃251197

编辑：

读取所述第一注释（Chuck's）后，以及重新读取的问题，并读取另一个答案，我倒是希望澄清我解释问题作为只是“增加堆栈大小”。我didn't打算说，你可以有无限的叠层，如在函数式编程（编程范式，从来就只触及它的表面）。

Answer 2

增加的堆栈大小将仅作为临时绷带。正如其他人所指出的那样，你真正想要的是尾调用消除，和Java没有这个因各种原因。不过，如果你愿意，你可以欺骗。

红色丸在手？ OK，这边请。

有您可以在其中对堆交换栈的方式。例如，而不是使一个函数内的递归调用，使其返回一个的懒惰数据结构评价时，使呼叫。然后，您可以放松“堆栈” Java的换结构。我将用一个例子证明。考虑这个Haskell代码：

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

请注意，该函数从未评估列表的尾部。所以功能实际上并不需要进行递归调用。在Haskell中，它实际上返回的咚的用于尾部，如果是以往任何时候都需要被调用。我们可以做在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);}});}

请注意Stream<A>由类型A的值和类型P1的值，它是这样的返回流的其余部分时_1（）被调用一个thunk的。尽管它当然看起来像递归，递归调用以映射不进行，但成为流数据结构的一部分。

这然后可以用常规用于构建体展开。

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，使通话，掌握了这些咚开了一个新的线程，并让当前线程退出的功能。的这是事物背后的理念像无堆栈的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，只有更好。 见这里。的要点是，上述折叠右递归数据结构，以在O右（1）堆，其通常需要尾部调用消除。因此，我们已经有效地achived TCE，以换取一定的复杂性。您可以按如下调用该函数：

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

请注意，这后一种技术工作得很好非线性递归。即，将在恒定堆甚至算法运行不具有尾巴的呼叫。

您可以做的另一件事是使用一种叫做蹦床。一种蹦床是一个计算，物化为数据结构，可以通过被踩踏。的功能的Java库包括 Trampoline 我写的数据类型，从而有效地让你把任何函数调用到尾调用。作为一个例子这里一个trampolined 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()));}});}

这是相同的原理使用多个线程，不同之处在于代替调用在其自己的线程的每个步骤中，我们构建在堆中的每个步骤中，很象使用Stream，然后我们运行与Trampoline.run单个环路的所有步骤。

Answer 3

这是到JVM是否要使用尾递归 - 我不知道随便他们中是否这样做，但你不应该依赖它。特别是，改变堆栈大小会的非常的很少是做正确的事，除非你有你居然会用递归多少级的一些硬性限制，你知道每个到底有多少堆栈空间会占用。很脆弱。

基本上，不应该在未建立它语言使用无限递归。你必须使用迭代相反，我害怕。是的，这可以是有时轻微疼痛：（

Answer 4

如果你要问，你可能做的事情错。

现在，虽然你也许可以找到一种方法来增加Java中的默认堆栈，让我补充我的2美分，你真正需要的，而不是依靠增加另寻出路做你想做的事，叠加。

因为Java规范没有强制要求JVM的实现尾递归优化技术，来解决这个问题的唯一办法就是要么通过减少需要的局部变量/参数的数量减少堆压，到由刚刚还原递归的水平显著，或者只是改写而不递归在所有保持轨道，或理想地

Answer 5

大多数功能的语言有尾递归支持。然而，大多数Java编译器不支持此功能。相反，它使另一个函数调用。这意味着将永远是递归调用就可以使数上限（您将最终运行的堆栈空间）。

使用尾递归你重新使用被递归函数的堆栈帧，所以不必在堆栈上相同的约束。

Answer 6

可以设置该命令行上的：

的java -Xss8M类

Answer 7

Clojure的，它运行在Java虚拟机，非常希望实现尾调用优化，但它不能由于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