Increasing the size of the stack will only serve as a temporary dressing. As others have pointed out, what you really want is to eliminate the tail call, and Java does not have this for various reasons. However, you can cheat if you want.
Red pill in the hand? Good, please.
There are ways in which you can exchange the stack for a bunch. For example, instead of making a recursive call inside a function, return a lazy datastructure that makes the call when evaluating. You can then expand the stack using Java for-construct. I will demonstrate an example. Consider this Haskell code:
map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = (fx) : map f xs
Note that this function never evaluates the tail of the list. Thus, functions do not actually need to make a recursive call. In Haskell, it actually returns a thin tail that is called if it is ever needed. We can do the same in Java (classes from Functional Java are used here):
public <B> Stream<B> map(final F<A, B> f, final Stream<A> as) {return as.isEmpty() ? nil() : cons(ff(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 similar to thunk, which returns the rest of the stream when _1 () is called. Although this, of course, looks like a recursion, a map does not recursively call, but it becomes part of the Stream data structure.
It can then be unwound using a regular for-construction.
for (Stream<B> b = bs; b.isNotEmpty(); b = b.tail()._1()) {System.out.println(b.head());}
Here is another example as you talked about Project Euler. This program uses mutually recursive functions and does not explode 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 swap a stack for a bunch is to use multiple threads . The idea is that instead of making a recursive call, you create a thunk that makes the call, pass that thunk to a new thread and let the current thread exit the function. This is an idea for things like Stackless Python.
The following is an example of this in Java. Sorry it's a bit opaque to watch without import static suggestions:
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, Pp(b)) : liftM2(f).f (promise(s, Pp(as.head()))).f (join(s, new P1<Promise<B>>>() {public Promise<B> _1() {return foldRight(s, f, b, as.tail());}}));}
Strategy<Unit> s supported by the thread pool, and the promise function passes thunk to the thread pool, returning a promise , which is very similar to java.util.concurrent.Future , only better. See here. The fact is that the above method flushes the right recursive data structure to the right in the O (1) stack, which usually requires a tail - elimination. Thus, we have effectively achieved 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);
Note that this latest technique works great for nonlinear recursion. That is, it will work in constant stacks of even algorithms that do not have tail calls.
Another thing you can do is use the trampolining method. A trampoline is a computation described as a data structure that can be overcome. The Java functional library includes Trampoline data that I wrote, which effectively allows you to turn any function call into a tail call. As an example, here is the foldRightC trampoline, which folds to the right in a 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(ff(head()));}});}
This is the same principle as when using multiple threads, except that instead of calling each step in our thread, we build each step on the heap very similar to Stream , and then perform all the steps in a single cycle with Trampoline.run .