Как я могу решить эту ошибку переполнения стека?

Question

В любое время, когда я пытаюсь проверить этот код на более чем 250 пунктах, это приводит к ошибке переполнения стека, все 250 и более работает отлично. Любые идеи, как заставить его работать с большими числами?

public class Divide { 

    Point2D closest1; 
    Point2D closest2; 
    double Distance = Double.MAX_VALUE; 
    int CurrentPoint = 0; 
    int NextPoint = 0; 


    public Divide(Point2D[] RandArray){ 
     SortArray s = new SortArray(); 

     //Sort the array using SortArray class 
     RandArray = s.SortPointsX(RandArray); 

     SplitAndConquer(RandArray); 
    } 

    /** 
    * Recursively call itself to check the distance between the points 
    * sent in as parameters. 
    * @param a first point to be compared for distance. 
    * @param b second point to be compared for distance. 
    * @param s array of points that is being compared. 
    * @return The distance of the closest pair. 
    */ 
    private double ComparePoints(Point2D a, Point2D b, Point2D[] s){ 
       //Checks to make sure two points aren't the same 
       if (a.getX() != b.getX() || a.getY() != b.getY()){ 
        CheckDist(a, b); 
       } 

       // Increments the NextPoint if it's not the last point in the array 
       // and recursively calls the next point to compare current to. 
       if (b != s[s.length - 1]){ 
        NextPoint++; 
        ComparePoints(s[CurrentPoint], s[NextPoint], s); 
       } 

       /* Sets the NextPoint to whatever the Current point is to prevent 
       * wasting comparisons between two points that have already been 
       * checked. Also increments the current point, and recursively 
       * calls the next point to compare it to. 
       */ 
       if (b == s[s.length - 1]){ 
        if (a != s[s.length - 1]){ 
        NextPoint = s.length - ((s.length - 1) - CurrentPoint); 
        CurrentPoint++; 
        ComparePoints(s[CurrentPoint], s[NextPoint], s); 
        } 
       } 

       //if the current point is the point at the end of the array it 
       //counters and returns the distance, ending the recursive calls 
       if (a == s[s.length - 1]){ 
        CurrentPoint = 0; 
        NextPoint = 0; 
        return Distance; 
        } 
      return Distance; 

    } 

    /** 
    * Checks the distance between two points. 
    * @param a first point to be compared for distance. 
    * @param b second point to be compared for distance. 
    */ 
    private void CheckDist(Point2D a, Point2D b) { 
     //Checks the distance between two points 
     if (Distance > a.distance(b)){ 
      Distance = a.distance(b); 

      //save the coordinates of the closest pair 
      closest1 = new Point2D.Double(a.getX(), a.getY()); 
      closest2 = new Point2D.Double(b.getX(), b.getY()); 
     } 
    } 

    /** 
    * Splits the array into two subsets and finds the closest pair among them. 
    * @param RandArray the array to be divided and searched. 
    */ 
    private void SplitAndConquer(Point2D[] RandArray){ 
     //median of the array used to split the list into subsets 
     double median = RandArray[RandArray.length/2].getX(); 

     //count used for splitting the array into subsets 
     int countS1 = 0; 
     int countS2 = 0; 

     //checks to see if the median is the point being sorted 
     boolean exact = false; 

     //Array to hold all points with x coordinate < median 
     Point2D[] s1 = new Point2D[RandArray.length/2]; 

     //Array to hold all points with x coordinate > median 
     Point2D[] s2 = new Point2D[RandArray.length/2]; 

     //Split the array comparing x coordinates and median 
     for (int i = 0; i < RandArray.length; i++){ 

      if (RandArray[i].getX() < median){ 
       s1[countS1] = RandArray[i]; 
       countS1++; 
      } 
      else if (RandArray[i].getX() > median){ 
       s2[countS2] = RandArray[i]; 
       countS2++; 
      } 
      //alternates median value to ensure even subsets 
      else if (RandArray[i].getX() == median && exact == false){ 
       s2[countS2] = RandArray[i]; 
       exact = true; 
       countS2++; 
      } 
      else if (RandArray[i].getX() == median && exact == true) { 
       s1[countS1] = RandArray[i]; 
       exact = false; 
       countS2++; 
      } 
     } 

     //Compares points if there are more than 2 points 
     if (s1.length > 2){ 
      ComparePoints(s1[0], s1[1], s1); 
      ComparePoints(s2[0], s2[0], s2); 
      }else{ 
       System.out.println 
       ("One of the subsets does not contain enough points!"); 
      } 

     //Checks the points that lie on the median 
     CheckMid(RandArray, Distance, median, CurrentPoint, NextPoint); 

     //Prints the closest pair 
     PrintClosest(); 
     } 

    /** 
    * Prints the closest pairs found using Divide and Conquer 
    */ 
    private void PrintClosest() { 
     System.out.println("The closest pair found using Divide " 
       + "And Conquer is at (" 
       + closest1.getX() + " " + closest1.getY() + "), and (" 
       + closest2.getX() + " " + closest2.getY() + ")"); 
     System.out.println("The distance between the pairs is: " + Distance); 

    } 

    /** 
    * Checks the original array but only points located with the current 
    * distance from the median which was used to split for subsets. 
    * @param randArray Original array full of sorted points. 
    * @param d Current distance of the closest pair. 
    * @param m The median used to partition the array. 
    * @param current Current index of point being compared. 
    * @param next Index of the next point to be compared to current. 
    */ 
    private void CheckMid(Point2D[] randArray, double d, double m, 
      int current, int next) { 

     //temp array list to hold all the points within the median + distance 
     ArrayList<Point2D.Double> temp = new ArrayList<Point2D.Double>(); 
     for(int i = 0; i < randArray.length; i++){ 
      if(randArray[i].getX() > (m - d) && 
        randArray[i].getX() < (m + d)){ 
       temp.add((java.awt.geom.Point2D.Double) randArray[i]); 
      } 
     } 

     //Creates a new array to hold the values in the array list 
     Point2D[] MidArray = new Point2D[temp.size()]; 
     for(int i = 0; i < temp.size(); i++) 
     { 
      MidArray[i] = temp.get(i); 
     } 

     //Makes sure the array list has enough points to be compared 
     if (MidArray.length >= 2){ 
      if (MidArray[0] != null && MidArray[1] != null){ 
      ComparePoints(MidArray[0], MidArray[1], MidArray); 
      } 
     } 
    } 
} 

Answer 1

Когда вы рекурсивно вызываете функцию, вы создаете фрейм стека для каждого вызова. Эти кадры стека будут накапливаться и не освобождаться до тех пор, пока вы не достигнете дна рекурсии и не начнете оценивать функции в обратном порядке.

Стек имеет ограниченный объем памяти, поэтому в какой-то момент вы будете рекурсивно вызывать свою функцию слишком много раз и заканчивать память в стеке, переполнение стека.

Вы можете конвертировать решение, чтобы использовать итеративную реализацию вместо рекурсивной реализации, или вы можете увеличить объем памяти в стеке.

Следует иметь в виду, что если вы увеличите объем памяти в стеке, в какой-то момент вы снова столкнетесь с этой проблемой, если будете слишком глубоко заходить.