0

This code I have written works great until a certain input size. If the input gets too large, I get a "java.lang.StackOverflowError". I have read some other entries on stackoverflow regarding this topic and I think I got an error in my recursion- but I can't find it. Here is the code:

public int partition(int[] A, int l, int r, int x){

    int i = l-1;
    int j = r;
    int exchange;

    while(i <= j){
        while(A[i] > x){
            i++;
        }

        while(j >= i && A[j] <= x){
            j--;
        }

        if(i < j){
            exchange = A[i];
            A[i] = A[j];
            A[j] = exchange;
        }
    }

    if(A[i] < A[r]){
        exchange = A[i];
        A[i] = A[r];
        A[r] = exchange;
    }

    return i;
}

public void quicksort(int[] A, int l, int r){
    int pivot = 0;
    int x = 0;

    if(l < r){
        x = A[r];
        pivot = partition(A, l, r, x);
        quicksort(A, l, pivot-1);
        quicksort(A, pivot+1, r);
    }
}
6
  • 2
    How big does the input have to be to get a stackoverflow? Commented May 11, 2013 at 15:52
  • are you the same person who posted this question: stackoverflow.com/questions/16496233/… .. shouldn't you try and do your own homework? Commented May 11, 2013 at 15:55
  • 1
    What do you see when you step through your code in your debugger? If you have a bug in your code, your debugger is the first thing you should try. Commented May 11, 2013 at 15:57
  • java.lang.StackOverflowError appears where you allocate too much into the memory 'stack' so you probably have an infinite loop somewhere. Commented May 11, 2013 at 15:59
  • @mrhobo They don't look like the same... it's just that week of the Java 101 semester :) Commented May 11, 2013 at 16:04

1 Answer 1

1

If the input gets too large

What exactly do you mean by "too large"? Every recursion that is deep enough could end up with stack overflow, because stack is used to keep all local variables of your recursive method on all levels of recursion.

This is intrinsic disadvantage of recursion, and a reason why iterative implementation usually outperforms recursive.

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

2 Comments

hmm...100 elements are working. from about 1000 up, it doesn't work anymore
But I want to handle about 1000k elements. So you would suggest to try the iterative way?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.