2

When I run my function on a small array, it works fine. However when I use a large array, I keep getting stack overflow. Is it due to my incorrect logic in my code? or is it just taking a long time? 

void RecursiveSort(T data[], int first, B last)
{

    // Sorts the array elements a[first] through a[last] recursively.

    // base case is if first and last are the same, which means we 
    // have no subarrays left to do



    if (first < last)
    {
        int minIndex = first;
        // replace first index of array with smallest of values in  the array 

        for (int index = first+1; index < last; index++)
        {
            if (data[index] < data[minIndex])
                // swap values
                minIndex = index;
        }   


        int temp = data[first];
        data[first] = data[minIndex];
        data[minIndex] = temp;



        RecursiveSort(data, first + 1, last);

    }


}
Improve this question
1
  • I dont think sorter is benefiting anything from recursive function call. Commented Oct 18, 2014 at 21:23

3 Answers 3

Reset to default
3

You see stack overflow error just because your stack has a limited size. Each time you call your recursive function you use some amount of memory for storing some values, such as an address to return to, values of the function parameters, etc.—see this Wikipedia article for more information.

As a rule of thumb, if your recursion goes more than 1000 levels deep, you may be in trouble.

The good news is that your code is an example of a tail recursion, where the recursive call is the last statement in the function. Such functions can be easily converted to a loop:

for (first = 0; first < last; ++first) {
     ...
}

Or, if you really need to create a recursive sort, don't try to implement a selection sort, but look at the Quicksort or merge sort, both can be implemented using recursion.

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

Comments

0

Your program has a limited stack memory. How big this memory is might depend on your compiler or your OS.

For each call to your recursuve function all arguments to the function are placed on the stack. This means that each call will take another chunk of size (last - first)*sizeof(T).

With a large array (last - first) will be bigger, but it also means that your recursive function will be called more times.

In total you will need approximately (last - first)*(last - first)*sizeof(T)/2 + (last - first)*2*sizeof(int) of stack size. Looking at that formula you can see how your stack gets in trouble when the size of the array increases.

Improve this answer

4 Comments

It won't copy the whole array for each call, it will just pass the pointer each time (as I understand the author is using regular C++ array here, not an STL container, so it is passed by pointer).
Whoops, yes you are right, the array is copied as a pointer so the total stack size will be (last - first)*(sizeof(void *) + 2*sizeof(int))
... plus some amount of memory for an address to return to, and for local variables such as minIndex, index, and temp, which should be also saved in the stack frame. I would just say that it will use O(N) of memory.
Yes, O(N) is the right relation of stack usage. In my reply I wrongly got O(N^2) as I assumed the entire array was put on the stack.
0

Yes, I also agree that you will be having limited stack memory, but you can reduce Recursion calls by putting a SWAP flag as mentioned below.

void recursive_bubble_sort(int *array, int size)
{
   bool swap = false;   // to avoid recursion call when no swapping is required
   for(int i=0; i+1 < size; ++i)
   {
      if(array[i] < array[i+1])
      {
         int tmp = array[i];
         array[i] = array[i+1];
         array[i+1] = tmp;

         swap = true;
      }
   }

   if(swap)
      recursive_bubble_sort(array, size);
}

Or implement Quicksort or Merge sort with recursion to cut down your stack.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.