Tail recursive function still blowing the stack in Java

I have read that JAVA 8 supports Tail call optimization, but I am thinking I must not be implementing it correctly.

Then you have read wrong. Or, you've read a correct statement but didn't interpret it correctly.

Java, the language, does not support tail call recursion. It never has. It probably never will*.

However, java, the VM, has a few features that make it easier for other, non-java languages which nevertheless compile into class files to run on a java runtime, to support TCO. That's, presumably, what you read about.

I am just looking for any advice on how to get this to use real tail call optimization, lambda expressions or however I can.

Write it in scala or some such.

Seriously, how does java not have TCO???

TCO is pricey: Java has this rule that when errors occur you get a stack trace, and stack traces are a well defined concept that, crucially, tracks 1 stack frame for each logical call. This cannot continue if TCO exists. There are options, of course: Each individual frame on stack could gain a 'counter' so that the stack trace remains a smallish memory footprint while correctly representing 'and this sequence of calls has recurred 8190581 times'. It's also a boatload of text in the lang spec about how it works, when it does and doesn't kick in, and what it all means, and any additional pages in the spec are maintenance burdens forever - it's not a case of 'it is strictly superior to add TCO to java so when we get around to it, slam dunk, and any Pull Requests with the feature will be integrated immediately'.

Furthermore, TCO as a model is a way of doing things, but it's not the only way. For anything that could be written as a TCO-recursive application, it is generally not all that difficult to refactor that into a loop-based, non-recursing algorithm. Contrast to, say, yield-based async operations, where you can of course rewrite (hey, it's all turing machines), but the rewrite would be difficult, and the resulting code considerably harder to understand. I don't want to get into the value (or lack thereof) of yield/async style coding, just making the point that TCO does not have that veneer of 'ah, but, if TCO is a good idea, then only TCO will do'.

I don't have the links off-hand, but statements in this vein have been said by those who hold quite a bit of sway over the future of java, such as Brian Goetz, Mark Reinhold, etc. If you are really dedicated to try to see this added to java, I suggest you search the web for these statements and then try to shape some arguments specifically to address the concerns they state. Because if you can't convince those folks, it's never going to happen.

So what do I do in java?

Don't use recursion; use while or for instead.

UPDATE: What about that blog entry?

In comments you have linked to this blog entry. That's.. not TCO.

That's using lambdas to write a framework that lets you more or less emulate TCO, but it isn't TCO. The blog describes a little framework - and thus, you need all that stuff they pasted: The TailCall interface in particular.

That code works like this:

• Your 'recursive' method isn't recursive at all, it always returns quickly without calling itself.
• It returns a lambda which may call itself, though. But, as we just covered, calling yourself returns quickly without recursion, and it returns a function.
• The framework will execute your function, which produces, usually, a function (or an actual result). It loops (so no recursion), repeatedly applying the process of: "Call the function. If it returns a function, then loop. If it returns a result, okay, that's the result we wanted so just return that".

That describes what TCO tries to accomplish (repeatedly invoke the same function over and over with different arguments until a hardcoded edge case is reached, and then reverse back out), but doesn't use TCO to do it.

Hence, that blog post saying 'look, TCO in java!' is misleading.

It's like me saying: "Look, paintbrushes on tunnels walls!" and describing how to use cans of spray paint to paint the tunnel wall in a way that looks like it was hand brushed. That is nice, but it's misleading to call it 'paintbrushing a wall'. At best you can say: "Looking to make paintbrush style art in tunnels? Well, you can't, and I can't fix that, but I can tell you how to get similar results!".

*) Never say never and all that, but I mean: There are no plans on the horizon, and the plans for the future of the java platform go many years into the future and are quite public. I'd take 1 to 40 odds on 'java (the language) does not have tail call recursion within 4 years' and still take that bet.

You may find this useful. I was able to get some improvement over your previous attempt but in this case it is not the size of the BigInteger object that causes the SO. On my machine, both of these methods result in a Stack Overflow between 14000 and 15000 for n. The simpleLong is just a basic recursive method to decrement the Long and it still blows up at 15000. Both succeed at 14000.

public static void main(String[] args) {
    count = 0;
    long n = 14000;
    simpleLong(n);
    factoriel(BigInteger.valueOf(n));
    
}
    
static BigInteger factoriel(BigInteger n) {
    if (n.compareTo(BigInteger.TWO) == 1) {
        return factoriel(n.subtract(BigInteger.ONE)).multiply(n);
    }
    return n;
}
    
static long simpleLong(long n) {
    if (n > 1) {
        simpleLong(n-1);
    }
    return n;
}