[ACCEPTED]-Stack overflows from deep recursion in Java?-overflow

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

Red pill in hand? OK, this 55 way please.

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

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

Note 48 that this function never evaluates the tail 47 of the list. So the function doesn't actually 46 need to make a recursive call. In Haskell, it 45 actually returns a thunk for the tail, which 44 is called if it's ever needed. We can do 43 the same thing in Java (this uses classes 42 from 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 41 type A and a value of type P1 which is like 40 a thunk that returns the rest of the stream 39 when _1() is called. While it certainly 38 looks like recursion, the recursive call 37 to map is not made, but becomes part of 36 the Stream datastructure.

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

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

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

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 30 thing you can do to exchange stack for heap 29 is to use multiple threads. The idea is that instead of 28 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 27 behind things like Stackless Python.

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

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

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

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

Another thing 12 you can do is employ a technique called 11 trampolining. A trampoline is a computation, reified 10 as a data structure, that can be stepped 9 through. The Functional Java library includes a Trampoline data type that 8 I wrote, which effectively lets you turn 7 any function call into a tail call. As an 6 example here is a trampolined foldRightC that folds to the right in constant stack:

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 5 multiple threads, except that instead of 4 invoking each step in its own thread, we 3 construct each step on the heap, very much 2 like using a Stream, and then we run all the steps 1 in a single loop with Trampoline.run.

I guess you could use these parameters

-ss 14 Stacksize to increase the native stack size 13 or

-oss Stacksize to increase the Java stack 12 size,

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

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

EDIT:

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

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

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

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

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

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

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

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

You can set this on the commandline:

java 1 -Xss8M class

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

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

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

0

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