Stack overflow on recursive call of a function

Question

I am trying to make a strand sort algorithm and when I try to recursive call it again it gives me stack overflow error

The recursive call is where I want to sort array a into two sorted arrays(preme, NoNpreme). And after that I merge these to back into a. I have tried to mess around with conditions and I figured out that array is sorted when there is only 1 element and that is my exit for recursion. But it doesn't work and I do not know why.

My algorithm:

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;
}

I call function like this:

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");

Where drek is unsorted and urejenoZap is pointer to sorted array drek.

NoNpreme = urediSPrameni(NoNpreme, k); should be return urediSPrameni(NoNpreme, k); — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Mar 16, 2019 at 16:40
And it leaks a lot of memory because you don't delete[] the memory you allocate with new[]. — 1201ProgramAlarm
– 1201ProgramAlarm, Commented Mar 16, 2019 at 16:45
O.K. so I deleted the arrays 1 line before return and put return NoNpreme = urediSPrameni(NoNpreme, k) but it still over flows. — AverageProgrammer
– AverageProgrammer, Commented Mar 16, 2019 at 17:00
@πάνταῥεῖ I think that the merge part is the continuation of the same function. THe return at this place would cause the rest of the function to never be reached. — Christophe
– Christophe, Commented Mar 16, 2019 at 17:15

1201ProgramAlarm · Accepted Answer · 2019-03-16 17:34:55Z

1

You assign the first element of a to pe, and store a copy of that element into preme. When sorting the elements of a into separate arrays based on which side of pe they fall on, you start with element 0 again (which you've already placed into preme), which, because if (a[i] > pe) will be false, will place this element into NoNpreme. Once the array reaches the point where there is more than one element, and the first element is the smallest, all of the elements will be copied into NoNpreme. Each recursive call after that will do the same, so the recursion will never end and you'll eventually run out of stack space.

The solution is to start your for loop with the second element:

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

answered Mar 16, 2019 at 17:34

1201ProgramAlarm

32.8k7 gold badges47 silver badges60 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Stack overflow on recursive call of a function

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related