Stack overflows from deep recursion in Java?

Question

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.

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

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

Thanks.

Answer 1

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.

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 datastructure that 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:

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 thunk for the tail, which is called if it's ever needed. We can do the same thing in Java (this uses classes 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 type A and a value of type P1 which 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.

This can then be unwound with a regular 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:

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.

The following is an example of that in Java. Apologies that it's a bit opaque to look at without 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 the promise function 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 = 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 library includes a Trampoline data type that I wrote, which effectively lets you turn any function call into a tail call. As an 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 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.

Answer 2

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

Answer 3

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 very rarely 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.

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 :(

Answer 4

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.

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.

Answer 5

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.

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).

Answer 6

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).

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.