Java Stackoverflow 错误递归

Question

我编写的这段代码在达到一定的输入大小之前效果很好。如果输入太大，我会收到“java.lang.StackOverflowError”。我已经阅读了 stackoverflow 上有关此主题的其他一些条目，我认为我的递归出现了错误 - 但我找不到它。这是代码:

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

Answer 1

If the input gets too large

“太大”到底是什么意思？每个足够深的递归都可能导致堆栈溢出，因为堆栈用于在所有递归级别上保留递归方法的所有局部变量。

这是递归的固有缺点，也是迭代实现通常优于递归的原因。