Почему я получаю переполнение стека для этого алгоритма рекурсии? - PullRequest
Новая
       69

Почему я получаю переполнение стека для этого алгоритма рекурсии?

0 голосов
/ 06 ноября 2019

Мой код вызывает переполнение стека, но я не знаю почему. Я реализовал своего рода «сортировку слиянием» для создания силуэта. Ошибка в строках 116 и 117. Рекурсия должна прекратиться, когда мой алгоритм достигнет базового случая, где l + 3

Я попытался закомментировать несколько методов, чтобы добраться до корня проблемы, но, к сожалению, я не былсмог найти его. 

public class Main {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] array = {0, 10, 3, 0, 0, 10, 3, 0, 4, 12, 5, 0, 2, 11, 5, 0, 4, 13, 7, 0};

    for (int i=0; i <array.length; i++) {
        System.out.println(array[i]);
    }

    int left = 0;
    int right = array.length-1;

    // initializing variables
    buildSilhouette(array, left, right);

    System.out.println(array.length);
}

private static int maxHeight (int h1, int h2) {
    int max = 0;

    if (h1>h2) {
        max = h1;
    }
    else max = h2;

    return max;
}


private static int findMiddleIndex (int l, int r) {
    int nrQ = (r+1)/4;
    int middleIndex = (nrQ/2)*4-1;

    return middleIndex;
}

private static  void mergeSilhouette (int[] array, int l, int m, int r) {

    // Hilfs-Silhouette
    int[] result = new int[r-l];

    // heights
    int h1 = 0;
    int h2 = 0;
    int currentHeight = 0;

    // Zeiger zum Durchlaufen
    int i = l;
    int j = m + 1;
    int k = 0;

    while (i <= m && j <= r) {
        if (array[i]<array[j]) {
            result[k]=array[i];
            h1 = array[i+1];
            currentHeight = maxHeight(h1, h2);
            result[k+1]=array[currentHeight];
            i+=2;
        }
        else if (array[i]>array[j]) {
            result[k]=array[j];
            h2 = array[j+1];
            currentHeight = maxHeight(h1, h2);
            result[k+1]=array[currentHeight];
            i+=2;
        }

        else if (array[i]==array[j]) {
            result[k]=array[i];
            result[k]=array[i+1];
            result[k]=array[j];
            result[k]=array[j+1];
            i+=2;
            j+=2;
            k+=2;
        }
        k+=2;
    }


    // falls die erste Teilfolge noch nicht erschöpft ist (noch Elemente enthält), hänge Sie hinten an B
    while (i <= m) {
        result[k]=array[i];
        result[k+1]=array[i+1];
        i+=2;
        k+=2;
    }

    // falls die zweite Teilfolge noch nicht erschöpft ist (noch Elemente enthält), hänge Sie hinten an B
    while (j <= r) {
        result[k]=array[j];
        result[k+1]=array[j+1];
        j+=2;
        k+=2;
    }

    // kopiere Inhalte nach B zurück
    for (k=l; k<r; k++) {
        array[k]=result[k-l];
    }


}

private static void buildSilhouette (int[] array, int l, int r) {

    if (l+3 < r) 

    { 
        // Find the middle point such that there are 4... 
        int m = findMiddleIndex(l, r); 

        // Sort first and second halves 
        buildSilhouette(array, l, m);      //116 
        buildSilhouette(array , m+1, r);   //117  

        // Merge the sorted halves 
        mergeSilhouette(array, l, m, r); 
    }
}


}

Мой ожидаемый результат - силуэт / горизонт для проблемы, описанной здесь: https://www.geeksforgeeks.org/the-skyline-problem-using-divide-and-conquer-algorithm/

Мой массив содержит отсортированные полосы из четырех, например одна отсортированная полосаиз 4 целых чиселВот почему рекурсия должна прекратиться, когда она достигнет случая l + 3

...