3

Java doesn't have a predefined recursion depth limit. As a result the recursion below (a dummy method that returns the value) throws java.lang.StackOverflowError after 62844 (with static) and 14002 (without static) iterations.

public static int testRecursion(int number) {
    if (number == 1) {
        return 1;
    } else {
        int result = 1 + testRecursion(number - 1);
        return result;
    }    
}


public int testIteration(int number){
int result = 0;
while (number > 0){
     result++;
     number--;
     }
return result;
}

I have two concerns:

  1. Iteration method works correctly for all positive int values, whereas recursion throws an exception
  2. Changes to a method change the recursion depth at which the exception will be thrown.

Recursion in Java seems like a way to add floating bugs. Recursion depth is greater than a magic number? Program throws exception. Author modified recursive method - allowed recursion depth decreased and an exception is thrown again.

Recursions are widely used in Java. Does it mean that recursion limit is rarely reached in practical situations? Or are there some general and robust methods to deal with floating recursion depth limit?

I've read these questions:

But none of those questions discuss a problem of recursion depth in Java.

Community
  • 1
sixtytrees
  • 469
  • 5
  • 10
  • see [When there's no TCO, when to worry about blowing the stack?](http://programmers.stackexchange.com/questions/216840/when-theres-no-tco-when-to-worry-about-blowing-the-stack) – gnat Jul 25 '16 at 18:37
  • 2
    Maximum recursion depth can be tuned in the JVM via stack-memory-per-thread allocation param (`-Xss`). The fact that most people aren't even aware of this fact should tell you how often this limit is hit. As a side note - doing this, you're essentially trading heap space and some pre-written logic for stack space. As always, you should be mindful of the consequences of your choice and decide if this is the best thing for you. – Ordous Jul 25 '16 at 18:48
  • While this is a good question and recursion will eventually blow it's stack, I find it hard to believe that a mere 14000 or 62000 function calls reaches the limit. We're you running with extremely low memory? – user949300 Jul 26 '16 at 19:20
  • Try that code to see how deep your JVM can go. I didn't specify Xms, Xmx or Xss. I am making two qualitative judgements: (1) a simple recursion lows up stack way below 1M calls. (2) A small change (toggling `static` keyword) drastically changes maximum recursion depth. This made me wonder: "sure, recursion can be more readable, but does it justify the Damocles sword of stack overflow?" – sixtytrees Jul 26 '16 at 19:47

1 Answers1

8

Recursion limit hits are indicated by corresponding messages and a recursion can easily be rewritten as iterations. This makes detection and fix easy.

Recursions are typically used in situations where the recursion depth is low. As Ordous pointed out -Xss parameter can be tuned to address borderline cases.

Deep recursive calls should be avoided. Tight loops are not really suited for recursive calls.

Jowan
  • 104
  • 3