current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 0 down vote favorite

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);
    }
}
share|improve this question
2  
How big does the input have to be to get a stackoverflow? –  Peter Micheal Lacey-Bordeaux May 11 '13 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? –  mrhobo May 11 '13 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. –  Peter Lawrey May 11 '13 at 15:57
    
java.lang.StackOverflowError appears where you allocate too much into the memory 'stack' so you probably have an infinite loop somewhere. –  Mr D May 11 '13 at 15:59
    
@mrhobo They don't look like the same... it's just that week of the Java 101 semester :) –  Marko Topolnik May 11 '13 at 16:04

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
hmm...100 elements are working. from about 1000 up, it doesn't work anymore –  user1252280 May 11 '13 at 16:17
    
But I want to handle about 1000k elements. So you would suggest to try the iterative way? –  user1252280 May 11 '13 at 16:26

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.