java stack overflow error recursion

Question

Im making a method that shifts chars in an array both left and right with a parameter that tells how many times to shift. It has to finish within 20 milliseconds, so i tried recursion.

//Method that switches place in array

public static void bytt(char[] c, int i, int j){
    char temp = c[i];
    c[i] = c[j];
    c[j] = temp;
}

//This method shifts left

public static char rotasjon1(char[] a, int i){
    if(i > 0){
        bytt(a,i,i-1);
        return rotasjon1(a,i-1);
    }
    else
        return ' ';
}

//This method shifts right

public static char reverseRotasjon(char[] a, int i){
    if(i < a.length-1){
        bytt(a,i,i+1);
        return reverseRotasjon(a,i+1);
    }
    else
        return ' ';
}

//This method decides to use right shift or left shift depending on the parameter

public static void rotasjon(final char[] a, int k){
    if(a.length == 1 || a.length == 0){
        return;
    }
    if(k >= 0){
        for(int i = 0; i< k; i++){
            char temp = a[a.length-1];
            rotasjon1(a,a.length-1);
            a[0] = temp;
        }
    }

    if(k < 0){
        for(int i = k; i< 0; i++) {
            char temp = a[0];
            reverseRotasjon(a, 0);
            a[a.length - 1] = temp;
        }
    }
}

//All these work fine with this array

char[] d = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
    char[] d0 = {'G', 'H', 'I', 'J', 'A', 'B', 'C', 'D', 'E', 'F'};

    Oblig1.rotasjon(d, 4);

d = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
    Oblig1.rotasjon(d, -6);

//But i get java.lang.StackOverflowError with this array

char[] x = new char[100_000];
    Oblig1.rotasjon(x, 99_999);

I know the array is big an stuff, but is it possible to fix this or do i have to go back to traditional for loops ? it have to execute within 20 millisecods

Recursion can be an elegant way to *describe* an algorithm, but typically it is not the most efficient way to *implement* one. And yes, there is often a relatively modest practical limit on recursion depth. In this case, though, recursion is neither elegant nor efficient for the rotation methods. — John Bollinger, Sep 11 '15 at 21:21
I believe generally speaking iterative programming (using a for loop) is faster, just requires more code. Where recursion is lighter on the code but a heavier tax on the machine. So to Berry's question, why did you choose recursion? — Acludia, Sep 11 '15 at 21:22
honestly you'll probably get the same time complexity for both iterative and recursive versions. The recursive version just looks prettier :D — Bryan Herrera, Sep 11 '15 at 21:22
The fastest way to rotate the characters in an array is probably `System.arraycopy`. Or you could use a `Character[]` instead and then do `Collections.rotate(Arrays.asList(array), val);`. — Paul Boddington, Sep 11 '15 at 21:22
The recurison used under 1 millisecond on all the smaller arrays i tested, and my regular algorithm used 4 seconds, but i guess thats just bad code from my side. Thanks for the replys! — Aleksander Aleksic, Sep 11 '15 at 21:37

score 2 · Answer 1 · edited May 23 '17 at 11:51

I know the array is big an stuff, but is it possible to fix this or do i have to go back to traditional for loops ?

The exception occurs because the recursion is too deep; i.e. it requires too many nested calls.

Now in many languages this would not matter. For example, with a typical functional language you can recurse as deeply as you want / need. But the reason that works is that functional languages (and many other language) implement something known as tail-call optimization, where a recursive call at the end of a method call is optimized (by the compiler) into a jump to the start of the method.

Reference: What Is Tail Call Optimization?

But Java doesn't support tail-call optimization. (There are sound but complicated reasons for that.) Instead, each call gets a stack frame on the current thread's stack; i.e. N-deep recursion requires N stack frames. The problem is that a Java thread has a fixed amount of stack space. (The default is typically 1M bytes or less.) Once created, a thread's stack cannot be expanded. If an algorithm recurses too deeply, the thread runs out of stack space, and the JVM raises an exception ... as you are observing.

So what is the answer?

In general, avoid implementing algorithms in Java that may be deeply recursive:
- If the algorithm is recursive, try to convert it to an iterative equivalent; e.g. do the tail-call optimization by hand.
- If the algorithm is iterative, leave it like that!
If you really need deep recursion, you can specify the maxiumum stack size for a thread as a constructor parameter. (I'm not sure if there are architectural limits, but you will certainly be limited to the amount of memory available ...)

if so, mabye you have some advice ? Remember it have to execute within 20 milliseconds.

If your primary goal is to implement this efficiently, don't use recursion instead of iteration. In Java - it won't be faster, and there is always a potential risk of stack overflow.
In this case, look at using a temporary array and System.arraycopy. (If you are rotating by 1, you don't need a temporary array. You can rotate by N in steps of 1 at a time, but that is inefficient.)
In this case, look at implementing it as you would rearrange playing cards by hand ... using just two hands (temporary variables). This gives a solution to the "rotate by N" problem without using O(N) extra storage.

I had no idea `Thread` had a constructor with a `stackSize` argument. That's really interesting. This might be a strange question but do you know if there is ever a reason to supply a value for this that is smaller than the default? — Paul Boddington, Sep 11 '15 at 22:28
@PaulBoddington - You might do that if you are creating lots and lots of threads, and you know that they only need a small stack. (If each thread has a default stack of 1Mb and you are creating thousands of them ... that's a significant amount of memory.) — Stephen C, Sep 11 '15 at 22:45

score 1 · Answer 2 · answered Sep 11 '15 at 21:53

Super fast rotation using System.arraycopy as suggested by Paul Boddington:

private static void rotate(char[] array, int distance) {
    if (array == null || array.length == 0)
        return; // nothing to rotate
    final int len = array.length;
    int d = distance % len; // eliminate distance overflow, e.g. for len=10, shift +28 is same as +8
    if (d == 0)
        return; // not rotating
    if (d < 0)
        d += len; // convert left shift to right shift, e.g. for len=10, -2 is same as +8
    if (d < len / 2) { // right shift less than half the array
        char[] temp = new char[d];
        System.arraycopy(array, len - d, temp, 0, d);  // save d values at end
        System.arraycopy(array, 0, array, d, len - d); // shift right by d
        System.arraycopy(temp, 0, array, 0, d);        // add saved value at start
    } else { // right shift more than half the array, so better to use left shift for smaller temp space
        d = len - d; // e.g. for len=10, right by 8 is left by 2
        char[] temp = new char[d];
        System.arraycopy(array, 0, temp, 0, d);        // save d values at start
        System.arraycopy(array, d, array, 0, len - d); // shift left by d
        System.arraycopy(temp, 0, array, len - d, d);  // add saved value at end
    }
}

Test

String s = "ABCDEFGHIJ";
for (int i = -11; i <= 11; i++) {
    char[] array = s.toCharArray();
    long start = System.nanoTime();
    rotate(array, i);
    long end = System.nanoTime();
    System.out.printf("%3d: %s   (%dns)%n", i, new String(array), end-start);
}

char[] x = new char[100_000];
for (int d : new int[] { 0, 1, 50_000, 99_999 }) {
    long start = System.nanoTime();
    rotate(x, d);
    long end = System.nanoTime();
    System.out.printf("%5d: %6dns = %fms%n", d, end-start, (end-start) / 1_000_000d);
}

Output

-11: BCDEFGHIJA   (7128ns)
-10: ABCDEFGHIJ   (285ns)
 -9: JABCDEFGHI   (856ns)
 -8: IJABCDEFGH   (855ns)
 -7: HIJABCDEFG   (855ns)
 -6: GHIJABCDEF   (855ns)
 -5: FGHIJABCDE   (855ns)
 -4: EFGHIJABCD   (855ns)
 -3: DEFGHIJABC   (856ns)
 -2: CDEFGHIJAB   (855ns)
 -1: BCDEFGHIJA   (855ns)
  0: ABCDEFGHIJ   (286ns)
  1: JABCDEFGHI   (855ns)
  2: IJABCDEFGH   (856ns)
  3: HIJABCDEFG   (1710ns)
  4: GHIJABCDEF   (856ns)
  5: FGHIJABCDE   (1141ns)
  6: EFGHIJABCD   (855ns)
  7: DEFGHIJABC   (856ns)
  8: CDEFGHIJAB   (855ns)
  9: BCDEFGHIJA   (571ns)
 10: ABCDEFGHIJ   (285ns)
 11: JABCDEFGHI   (855ns)

    0:    285ns = 0.000285ms
    1:  55885ns = 0.055885ms
50000:  43339ns = 0.043339ms
99999:  56169ns = 0.056169ms

If you use JMH to benchmark it, you get something close to 15ns regardless of how large the array is, which is likely a lot more accurate than the `System.nanoTime` approach. — Makoto, Sep 11 '15 at 22:24
@Makoto Thanks for benchmarking. I'd assume that's because JMH warms up the JVM, causing `arraycopy` to be JIT-compiled. I just wanted to show that even without warm-up, the code was way below the goal of 20ms. — Andreas, Sep 11 '15 at 23:28

score 0 · Accepted Answer · answered Sep 11 '15 at 21:20

0

Java does not support tail call optimization, so you'll either need a different algorithm or a for loop.

answered Sep 11 '15 at 21:20

Coburn Berry

262
1
8

Roman Postanciuc · Answer 4 · 2015-09-11T22:26:20.927

What you are trying to do is call the function 100 000 times with an input array of size 100 000 to 1. The max size that you are trying to fit into the memory is (100 000 + 1) * (100 000 / 2) * 8 (the size of all chars) + 100 000 * 8 (the size of array references) + 100 000 * 24 (the memory required to keep an array structure) bits. This is 5 000 450 000 bytes or ~5GB, hence the StackOverflowError. You can still make it run by tweaking the JVM, but in general it's a very bad idea to use deep recursion for large data structures.

java stack overflow error recursion

4 Answers4