Recursive implementation of Java execution compared to other / functional languages?

Question

I like recursion, but in Java at some point you come across a dead end. For example. I had a case where recursion with ~ 100K iterations did not work (StackOverflowError). Too bad I had to switch to the annoying "imperative loop" for these stack time limits at runtime.

I wonder how other (especially functional) languages ​​overflow stacks at runtime? I assume that especially functional language runtimes handle this problem better, because recursion is a basic concept ...

Does anyone have information or external resources?

Answer 1

Most languages ​​have compiler optimizations for tail recursion . Tail recursion means that the recursive call must be the last call of your recursive method. The compiler can then optimize this in a loop, preventing errors.

I'm not sure if all javac implementations implement tail recursion. This is not what is required in the specification. However, this is an important optimization method for any recursive program, so I assume that main thread implementations provide tail recursion.

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

EDIT . Previously, there was a question about tail recursion in Java, as stated in a comment by sje397. Also take a look at Stephen C's answer to this question, which provides more information.

Answer 2

This is the answer to @Ronald Wildenberg's question:

I'm not sure if all javac implementations implement tail recursion. This is not what the specification requires.

The short answer is that they do not support it.

The longer answer is that tail recursion optimization is a difficult Java problem due to the JVM design. Read this blog post by John Rose @Oracle where he talks about this issue. The main focus of the blog entry is to offer bytecode extensions to support hard tail calls. But the last paragraph hints at why using soft (i.e. Transparent) tail calls is difficult. Tail call optimization interferes with the JVM's ability to capture stack traces and has “implications” for the Java security architecture.

This Sun Bug Database Entry provides more detailed information about the problem. Read also the comments.

It seems like a way to implement tail recursion on the current JVM is to implement it in the compiler interface. Scala seems to be doing this.

Answer 3

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

Recursion is one of those concepts that people tend to abuse when they first learn, because it seems like it's too cool to not show off everywhere ...

Answer 4

You can increase java package size with:

 java -Xss1024k MyProgram 

(increase java stack size to 1024 KB). But, as a rule, it is not recommended to use this deep recursion. Try making an iterative solution.

Answer 5

As other people have said, supporting proper tail recursion helps. But this alone is not enough to support deep recursion. And, despite what BLUB programmers might think, deep recursion is natural for some tasks, such as processing deep recursive data structures.

Support strategies for deep (not tail) recursion are often divided into strategies for supporting first-class continuations. You can find Implementation Strategies for first-class continua (Clinger et al.).

A few strategies from the head:

• CPS-convert your program or otherwise heaps-allocate continuation frames (disadvantage: loses some stack performance benefits)
• when the stack is full, copy the stack to a separate memory block and reset the stack pointer to the base; at the bottom level, copy the old stack back to
• when the stack overflows, select the new stack area from the heap and reset the stack pointer there; when overflow, return to the end of the old stack
• when the stack overflows, create a new thread to continue performing the calculations, and wait for the result of the stream (drawbacks: creating a stream can be expensive (but worker threads can be cached), and moving the calculations through the streams can lead to a local storage hook, etc. .)