current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Dismiss
Announcing Stack Overflow Documentation

We started with Q&A. Technical documentation is next, and we need your help.

Whether you're a beginner or an experienced developer, you can contribute.

Sign up and start helping → Learn more about Documentation →
up vote 2 down vote favorite

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);
    }
share|improve this question
    
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 Aug 23 at 10:35
    
You should add a Log.i("Start", start.toString()); to your find method as first line, so you see what happens. – Marlon Regenhardt Aug 23 at 10:36
up vote 2 down vote accepted

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);
share|improve this answer
    
thank you very much for help! – Igor Skryl Aug 23 at 11:05
    
Note that this code is only a starting point. You need to handle empty route array, null route array for example. – Davide Lorenzo MARINO Aug 23 at 11:06
up vote 5 down vote

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.

share|improve this answer
3  
he should also return find there. – Kevin Esche Aug 23 at 10:32
    
@KevinEsche Good point – Eran Aug 23 at 10:35
    
@Eran thank you very much for explanation! – Igor Skryl Aug 23 at 11:04
up vote 1 down vote

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

share|improve this answer
up vote 1 down vote

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;
}
share|improve this answer
    
thank you very much for help! – Igor Skryl Aug 23 at 11:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.