Resolving StackOverFlowException in C++

Question

I am trying to write a program for selection sort of the elements an array in C++ (VS2010) using recursion. The program works without any issues for for smaller arrays where the size of the array is less than 10 when I increase the size of the array to 10000 I am facing stackoverflow exception. How do I go about resolving this?

Thank you for the answers so far. My idea is not to sort the array but to sort a large array using recursion and the hit a stackoverflow exception. My main idea behind this exercise is to learn ways to resolve the stackoverflow exception rather than sorting the array.

selectionSortRecursive(int a[], int startindex, int endindex)
{
    if (startindex<endindex)
    {
        int s = startindex;
        for (int index=startindex+1;index<endindex;index++)
        {
            if (a[s]>a[index])
                s=index;
        }
        if (s>startindex)
        {
            a[s]=a[startindex]+a[s];
            a[startindex]=a[s]-a[startindex];
            a[s]=a[s]-a[startindex];
        }
        selectionSortRecursive(a, startindex+1, endindex);
    }

}

The recursion is the reason for the stackoverflow. Show us some code, maybe something can be optimized. — Tom Knapen
– Tom Knapen, Commented Oct 4, 2011 at 23:40
You're best best is probably to rewrite your method using a loop instead of recursion. If you can rewrite your recursive method to be tail recursive, then it's easy to rewrite it again using a loop. Check out Turning a Recursive Function into a For Loop — Nate W.
– Nate W., Commented Oct 4, 2011 at 23:41
Why do you have recursion in such a simple sort? See en.wikipedia.org/wiki/Selection_sort. — Alexey Frunze
– Alexey Frunze, Commented Oct 4, 2011 at 23:41

Ernest Friedman-Hill · Accepted Answer · 2011-10-04 23:39:37Z

4

Either increase the size of the stack (which can be done with the STACK linker option) or -- and this is a much better option -- improve or replace your algorithm. It sounds like a recursive algorithm may not be suitable for the kind of data you need to process, but maybe you can improve things by using fewer local variables and/or parameters in each method invocation, to make the stack frames smaller.

answered Oct 4, 2011 at 23:39

Ernest Friedman-Hill

81.9k11 gold badges158 silver badges191 bronze badges

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

Comments

FailedDev · Accepted Answer · 2011-10-04 23:42:48Z

2

You are either using a great deal of local storage or your recursive algorithms explodes memory usage by subsequent calls. In either case probably an iterative solution would solve your problems.

answered Oct 4, 2011 at 23:42

FailedDev

27k9 gold badges56 silver badges74 bronze badges

Comments

Maxpm · Accepted Answer · 2011-10-04 23:41:42Z

1

Local variables, as you may know, are kept on the stack.

When a function recurses, local variables from each call remain on the stack for as long as their respective functions execute. If you recurse too much, the build-up will be too great and you will likely end up with a stack overflow exception, like you're getting, or a segmentation fault, where the stack overflows into protected memory.

This is fundamental, and there is no way around it other than to increase your available memory or to rewrite your function to be iterative.

answered Oct 4, 2011 at 23:41

Maxpm

26.1k35 gold badges122 silver badges179 bronze badges

Comments

Adrian Mole · Accepted Answer · 2023-12-05 13:32:51Z

0

The recursive approach will take lot of stack space; instead of it, we can use a for loop to implement it:

void sort_array(int a[], int n)
{
    for(int i=0; i<size-1; i++) 
    {
        int min=i;
        for(int j=i+1; j<size; j++)
        {
            if(a[j]<a[min])
                min=j;
        }
        if(min!=i)
        {
            int temp=a[i];
            a[i]=a[min];
            a[min]=temp;
        }
    }
}

This code might work for you.

edited Dec 5, 2023 at 13:32

Adrian Mole

52.1k193 gold badges61 silver badges101 bronze badges

answered Dec 5, 2023 at 12:46

Sandeep_agh

1

Collectives™ on Stack Overflow

Resolving StackOverFlowException in C++

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related