CODEWITHSUNDEEP
c++recursionstack-overflow
user2577345
user2577345

Reputation:

Stack overflow in my recursive function, is it due to logic or large number?

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

    }


}

Upvotes: 2

Views: 143

Answers (3)

Guru
Guru

Reputation: 41

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.

Upvotes: 0

Henrik Carlqvist
Henrik Carlqvist

Reputation: 1168

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.

Upvotes: 0

afenster
afenster

Reputation: 3608

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.

Upvotes: 3

Related Questions