Stack Overflow Error on recursion java

Question

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 why this happened.

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);
    }

start++ returns the original value of start and adds 1 to start after. ++start adds 1 to start before returning the value. — Ray O'Kalahjan
– Ray O'Kalahjan, Commented Aug 23, 2016 at 10:35
You should add a Log.i("Start", start.toString()); to your find method as first line, so you see what happens. — Squirrelkiller
– Squirrelkiller, Commented Aug 23, 2016 at 10:36

Eran · Accepted Answer · 2016-08-23 10:45:47Z

5

First of all change

find(route, start++)

to

find(route, start+1)

since post-increment returns the original value of the variable, so the recursion never advances, leading to StackOverflowError.

You should also add a stopping condition, otherwise your next exception would be ArrayIndexOutOfBoundsException.

As Kevin commented, you should also do something with the value returned by find(route, start++);. Otherwise there is no point in calling it at all.

Besides those issues, your logic is wrong. The method will return the last index of the descending sequence starting at the beginning of the array, which tells you nothing about the longest descending sequence. For example, for { 1, 4, 6, 20, 19, 16, 10, 6, 4, 7, 6, 1 ...} your method would return 0 (the first index of the array), since route[0] > route[1] is false.

edited Aug 23, 2016 at 10:45

answered Aug 23, 2016 at 10:31

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

SomeJavaGuy Over a year ago

he should also return find there.

Davide Lorenzo MARINO · Accepted Answer · 2016-08-23 10:58:44Z

3

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);

edited Aug 23, 2016 at 10:58

answered Aug 23, 2016 at 10:34

Davide Lorenzo MARINO

27k4 gold badges45 silver badges58 bronze badges

1 Comment

Davide Lorenzo MARINO Over a year ago

Note that this code is only a starting point. You need to handle empty route array, null route array for example.

Radek Wroblewski · Accepted Answer · 2016-08-23 10:38:54Z

1

When you call start++ you perform a postincrementation. It means that the operation occurs after passing the parameter to the method - which means that your method just keeps going around in circles on the first parameter until the memory runs out. Replace it with start+1 and you'll get the whole new bunch of exceptions to have fun with ;)

answered Aug 23, 2016 at 10:38

Radek Wroblewski

2992 silver badges8 bronze badges

Comments

Andrew Lygin · Accepted Answer · 2016-08-23 10:52:11Z

1

You have several problems in the algorithm that other users pointed here. But the main problem is that this algorithm must not be recursive. Recursively, you can only find the length of the descending sequence that starts at the zero index.

A correct algorithm must run through the whole array:

public static int find(long[] route) {
    int maxIdx = 0;
    int maxCount = 1;
    for (int i = 1, c = 0; i < route.length; i++) {
        if (route[i] < route[i - 1]) {
            if (++c >= maxCount) {
                maxCount = c;
                maxIdx = i - c;
            }
        } else {
            c = 0;
        }
    }
    return route.length == 0 ? -1 : maxIdx;
}

edited Aug 23, 2016 at 10:52

answered Aug 23, 2016 at 10:46

Andrew Lygin

6,2271 gold badge35 silver badges38 bronze badges

Collectives™ on Stack Overflow

Stack Overflow Error on recursion java

4 Answers 4

1 Comment

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related