ansaurus

Question

Recursion runtime implementation Java vs. other/functionals languages?

Answer 1

+8 A:

Most languages have compiler optimizations for tail recursion. Tail recursion means that the recursive call should be the last call of your recursive method. The compiler can then optimize this into a loop, preventing stack overflow errors from happening.

I'm not sure whether all javac implementations implement tail recursion. It is not something that is required by the specification. However, it's an important optimization technique for any recursive program, so I suppose the mainstream implementations do provide tail recursion.

You can test this yourself by taking a (simple) non-tail-recursive program that generates a StackOverflowError and make it tail-recursive (calculating a factorial, for example).

EDIT: There has been a question about tail recursion in Java before, as indicated in a comment by user sje397. Also take a look at Stephen C's answer to this question, which provides some additional info.

Ronald Wildenberg 2010-09-28 10:17:02

I've never heard that java compiler optimizes tail recursion. But scala compiler does.

Roman 2010-09-28 11:10:53

Answer 2

A:

You can increase java stack size with:

java -Xss1024k MyProgram

(will increase the stack size of java upto 1024 KB.) But generally it is not a good idea to use that deep recursion. Try to make iterative solution.

Klark 2010-09-28 10:24:54

thanks for the param hint. but I wouldn't use it to bypass the core large stack problem.

manuel aldana 2010-09-28 11:14:33

Answer 3

+3 A:

"recursion with ~100K iterations" is something that should be avoided, not just in Java. It works only due to tail call optimization, which is not always possible. So it's better not to get into the habit of excessive recursion in the first place.

Recursion is one of those concepts people tend to overuse when they first learn them, because it seems just too cool not to show off everywhere...

Michael Borgwardt 2010-09-28 10:42:53

I agree, that recursion isn't the solution for all problems, I just wondered how language runtimes solve big-data. Reading answers tail-recursion is the only optimization. You saying tail recursion not always possible this implies that you generally have to change your algorithm when facing bigger data-sets.

manuel aldana 2010-09-28 11:12:50

@manuel: most good/useful recursive algorithm do some sort of divide-and-conquer thing which limits the maximal recursion depth to log(n), which means that it can't realistically become a problem (assuming that single recursive steps do not require very much additional memory).

Michael Borgwardt 2010-09-28 11:28:54

'"recursion with ~100K iterations" is something that should be avoided, not just in Java' Well it's hard to avoid in languages where recursion is the only means of iteration. But of course those languages guarantee tail recursion to be optimized - you just need to make sure that your function is tail recursive.

sepp2k 2010-09-28 11:41:07

There's nothing inherently wrong with "recursion with 100k iterations", except in languages that can't handle it. There are a number of algorithms that are more cleanly expressed in recursion. The ability of a language not to express them in this way is a limitation of the language (though many times for perfectly valid reasons). For those languages, there's generally ways to solve the problem that take advantage of what they gained by giving up the ability to handle such.

RHSeeger 2010-10-06 16:53:24

Answer 4

+3 A:

This is a followup to @Ronald Wildenberg's answer:

I'm not sure whether all javac implementations implement tail recursion. It is not something that is required by the specification.

The short answer is that they don't support it.

The longer answer is that tail recursion optimization is a tricky problem in Java because of the JVM design. Read this blog entry by John Rose @ Oracle where he talks about this problem. The main thrust of the blog entry is a proposal for a bytecode extension to support "hard" tail calls. But the last paragraph hints as why implementing "soft" (i.e. transparent) tail calls is hard. Tail call optimization interferes with the JVM's ability to capture a stack trace, and that has "implications" for the Java security architecture.

This Sun Bug Database Entry gives more details on the problem. Read the comments as well.

It seems that the way to implement tail recursion on the current JVM is to implement it in the compiler front-end. Apparently Scala does this.

Stephen C 2010-09-28 10:55:11

ansaurus

tags:

views:

answers:

Recursion runtime implementation Java vs. other/functionals languages?

related questions