Переполнение стека при рекурсивном вызове функции - PullRequest
Новая
       7

Переполнение стека при рекурсивном вызове функции

0 голосов
/ 16 марта 2019

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

В рекурсивном вызове я хочу отсортировать массив a в два отсортированных массива (premeNoNpreme).И после этого я объединяю их, чтобы вернуться в.Я попытался возиться с условиями, и я понял, что массив сортируется, когда есть только 1 элемент, и это мой выход для рекурсии.Но это не работает, и я не знаю почему.

Мой алгоритм: 

int* urediSPrameni(int* a, int n)
{
    if (n <= 1)
        return a;

    int pe=a[0];
    int* preme = new int[n];
    preme[0] = a[0];
    int j = 1;
    int k = 0;
    int* NoNpreme = new int[n];
    for(int i=0;i<n;i++)
    {
        if (a[i] > pe)
        {
            pe = a[i];
            preme[j] = a[i];
            j++;
        }
        else
        {
            NoNpreme[k] = a[i];
            k++;
        }
    }
    NoNpreme = urediSPrameni(NoNpreme, k);


    // My merge algorithm:

    //Zlivanje
    int h = 0;//NoNpreme
    int s = 0;//Preme
    int i = 0;
    while (h < k && s < j)
    {
            if (preme[h] <= NoNpreme[s])
            {
                a[i] = preme[h];
                s++;
            }
            else
            {
                a[i] = NoNpreme[s];
                h++;
            }
            i++;
    }
    if (h > k)
    {
        for (int b = s;b < j;b++)
        {
            a[i] = NoNpreme[b];
            i++;
        }
    }
    else
    {
        for (int b = h;b < k;b++)
        {
            a[i] = preme[b];
            i++;
        }
    }
    return a;
}

Я вызываю функцию так: 

int n = 7;
int drek[] = { 5,1,2,20,5,28,7 };
int* urejenoZap = urediSPrameni(drek, n);
for (int i = 0;i < n;i++)
    cout << urejenoZap[i] << " ";
system("PAUSE");

Где drekне отсортирован и urejenoZap является указателем на отсортированный массив drek.

1 Ответ

0 голосов
/ 16 марта 2019

Вы присваиваете первый элемент a для pe и сохраняете копию этого элемента в preme. При сортировке элементов a в отдельные массивы в зависимости от того, на какую сторону pe они попадают, вы снова начинаете с элемента 0 (который вы уже поместили в preme), что, поскольку if (a[i] > pe) будет false , поместит этот элемент в NoNpreme. Как только массив достигнет точки, в которой имеется более одного элемента, а первый элемент наименьший, все элементов будут скопированы в NoNpreme. Каждый рекурсивный вызов после этого будет делать то же самое, поэтому рекурсия никогда не закончится, и вы в конечном итоге исчерпаете пространство стека.

Решение состоит в том, чтобы запустить цикл for со вторым элементом: 

for (int i = 1; i < n; i++)
...