CODEWITHSUNDEEP
c++recursionstack-overflow
Chiranth Bs
Chiranth Bs

Reputation: 53

stack overflow error in c++

I have this function which does recursive selection sort for an array:

void  SelectionSort::RecursiveSort(int ar[] , int flag, int first, int last){
    // first - index of first element and last - index of last element
    if (flag == 1)
    {
        if (first < last)               //ascending
        {
            for (int i = first; i <= last; i++) if (ar[i] < ar[first]) swap(ar[i], ar[first]);

            RecursiveSort(ar, flag, first + 1, last);
        }
        if (first == last) return;

    }
    else
    {
        if (first < last)                   //desc
        {
            for (int i = first; i <= last; i++) if (ar[i] > ar[first]) swap(ar[i], ar[first]);

            RecursiveSort(ar,flag, (first + 1), last);
        }
        if (first == last) return;

    }
}

It works fine if array size is 3000, but I am supposed to make this work for size>5000 and its crashing giving stack overflow.

I searched many threads and they all tell to use vectors and I have. This is an assignment problem, so I am supposed to do recursion sorting for both arrays and vectors. Its working for vectors, but not for arrays. Also I am not supposed to use pointers in this assignment.

Upvotes: 0

Views: 117

Answers (2)

Davislor
Davislor

Reputation: 15134

If your compiler does not optimize tail-recursion, that solution will not work and you will need to rewrite as a while loop that checks for the base case. Not posting a complete solution because this looks like homework.

Upvotes: 1

EvgeniyZh
EvgeniyZh

Reputation: 905

You can try to use tail recursion, so compiler will optimize it as loop for you:

void AscRecursiveSort(int ar[], int first, int last) {
    if (first >= last) return;
    for (int i = first; i <= last; i++) if (ar[i] < ar[first]) swap(ar[i], ar[first]);
    AscRecursiveSort(ar, first + 1, last);

}

void DescRecursiveSort(int ar[], int first, int last) {
    if (first >= last) return;
    for (int i = first; i <= last; i++) if (ar[i] > ar[first]) swap(ar[i], ar[first]);
    DescRecursiveSort(ar, first + 1, last);
}

void RecursiveSort(int ar[], int flag, int first, int last) {
    // first - index of first element and last - index of last element
    if (flag == 1)
        AscRecursiveSort(ar, first, last);              //ascending
    else
        DescRecursiveSort(ar, first, last);
}

Upvotes: 1

Related Questions