Igor Skryl Igor Skryl - 3 months ago 13
Java Question

Stack Overflow Error on recursion java

I need to find the longest way (from bigger to lower) between numbers in array.
I've tried to write

recursive
function and got
java.lang.StackOverflowError
, but for the lack of knowledge I didn't understand I this heppened.

Firstly, I've initialize array and fill it with random numbers:

public long[] singleMap = new long[20];
for (int i = 0; i < 20; i++) {
singleMap[i] = (short) random.nextInt(30);
}


Then, I try to find the longest route of counting down numbers (e.g. { 1, 4, 6, 20, 19, 16, 10, 6, 4, 7, 6, 1 ...} ) and to return the count such numbers.

public int find(long[] route, int start) {
if (route[start] > route[start + 1]) {
find(route, start++);
} else {
return start;
}
return start;
}


So here's log:

08-23 13:06:40.399 4627-4627/itea.com.testnotification I/dalvikvm: threadid=1: stack overflow on call to Litea/com/testnotification/MainActivity;.find:ILI
08-23 13:06:40.399 4627-4627/itea.com.testnotification I/dalvikvm: method requires 36+20+12=68 bytes, fp is 0x4189e318 (24 left)
08-23 13:06:40.399 4627-4627/itea.com.testnotification I/dalvikvm: expanding stack end (0x4189e300 to 0x4189e000)
08-23 13:06:40.400 4627-4627/itea.com.testnotification I/dalvikvm: Shrank stack (to 0x4189e300, curFrame is 0x418a3e88)
08-23 13:06:40.400 4627-4627/itea.com.testnotification D/AndroidRuntime: Shutting down VM
08-23 13:06:40.400 4627-4627/itea.com.testnotification W/dalvikvm: threadid=1: thread exiting with uncaught exception (group=0x41a8ed40)
08-23 13:06:40.414 4627-4627/itea.com.testnotification E/AndroidRuntime: FATAL EXCEPTION: main
Process: itea.com.testnotification, PID: 4627
java.lang.StackOverflowError
at itea.com.testnotification.MainActivity.find(MainActivity.java:46)
at itea.com.testnotification.MainActivity.find(MainActivity.java:46)


I appreciate any explanation because all related issues didn't help me. If there is a problem in my function, please correct or explain.

EDIT

I forgot to say, that I use
for
to check the longest way from each "point"

for (int i = 0; i < singleMap.length - 1; i++) {
int x = find(singleMap, i);
System.out.println("steps = " + x);
}

Answer

You need to mantain the current max find up to now, and the current value. So change it as follow:

public int find(int[] route, int start, int max, int currentMax) {
    if (currentMax > max) {
        max = currentMax;
    }
    if (start == route.length - 1) {
        return max;
    }
    if (route[start] > route[start + 1]) {
        return find(route, start + 1, max, currentMax + 1);
    }
    return find(route, start + 1, max, 1);
}

And call it with a starting

find(route, 0, 1, 0);

A second alternative is to rewrite it without recursion:

public int find(int[] route) {
    int max = 1;
    int currentMax = 1;
    for (int i = 0; i < route.length - 1; i++) {
        if (route[i] > route[i + 1]) {
            currentMax++;    // If next element is lower increment currentMax
            if (currentMax > max) {
                max = currentMax;   // If currentMax is the new max update max
            }

        } else {
            currentMax = 1;   // If next element is not lower restart from 1
        }
    }
    return max;
}

and call it as

find(route);