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

Question

在使用函数式语言之后,我开始在Java中使用更多的递归 - 但是语言似乎有一个相对较浅的调用堆栈,大约1000.

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

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

谢谢.

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>由type的值和type A的值组成P1,类似于在调用_1()时返回流的其余部分的thunk.虽然它看起来像递归,但是没有对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,只是更好.看这里.关键是上面的方法将右递归数据结构折叠到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

请注意,后一种技术非常适用于非线性递归.也就是说,它将以常量堆栈运行,甚至是没有尾调用的算法.

你可以做的另一件事就是采用一种叫做蹦床的技术.蹦床是一种计算,具体化为数据结构,可以逐步实现.该功能的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不是一种足够高级的语言.