stack overflow error in c++

Question

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.

Google how to increase your stack with the compiler you use

Marged
– Marged

2015-10-18 17:41:10 +00:00
Commented Oct 18, 2015 at 17:41 — Marged
– Marged, Commented Oct 18, 2015 at 17:41

EvgeniyZh · Accepted Answer · 2015-10-18 19:40:48Z

1

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

answered Oct 18, 2015 at 19:40

EvgeniyZh

91510 silver badges23 bronze badges

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

2 Comments

Chiranth Bs Over a year ago

Thanks for the tail recursion..I solved the problem by increasing the stack size in visual studio.

EvgeniyZh Over a year ago

@ChiranthBs note of someone else will need to compile your program he'll need to do that too. That's why it's considered bad practice

Davislor · Accepted Answer · 2015-10-18 20:54:09Z

1

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.

answered Oct 18, 2015 at 20:54

Davislor

15.6k2 gold badges39 silver badges54 bronze badges

Collectives™ on Stack Overflow

stack overflow error in c++

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related