2013-05-11 119 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