2013-05-11 3 views
0

這段代碼我寫了很大的作品,直到一定的輸入大小。如果輸入變得太大,我得到一個「java.lang.StackOverflowError」。我已經閱讀了關於這個主題的一些其他關於計算器的條目,我想我的遞歸中有一個錯誤 - 但我找不到它。 下面是代碼:Java 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); 
    } 
} 
+2

輸入必須有多大來獲得一個計算器? – placeybordeaux 2013-05-11 15:52:58

+0

你是誰發佈這個問題的同一個人:http://stackoverflow.com/questions/16496233/recursive-parameters-for-quicksort#comment23678710_16496233 ..你不應該嘗試做你自己的作業嗎? – 2013-05-11 15:55:01

+1

當你在調試器中遍歷代碼時,你會看到什麼?如果你的代碼中有一個bug,你的調試器是你應該嘗試的第一件事。 – 2013-05-11 15:57:12

回答

1

如果輸入變得太大

究竟你「過大」是什麼意思? 每個足夠深的遞歸最終都會導致堆棧溢出,因爲堆棧用於在遞歸的所有級別上保留遞歸方法的所有局部變量。

這是遞歸的內在缺點,也是迭代實現通常優於遞歸的原因。

+0

嗯... 100個元素正在工作。從大約1000起,它不再起作用 – user1252280 2013-05-11 16:17:54

+0

但是我想處理大約1000k個元素。所以你會建議嘗試迭代的方式? – user1252280 2013-05-11 16:26:17