Encountering stack overflow while implementing recursive Bubble sort

Question

Hey I converted this C# code to c++ as

void bubbleSort(int *inputArray, int passStartIndex, int currentIndex,int length)
{
    if(passStartIndex == length - 1) return;
    if(currentIndex == length - 1) return bubbleSort(inputArray, passStartIndex+1, passStartIndex+1,length);

    //compare items at current index and current index + 1 and swap if required
    int nextIndex = currentIndex + 1;
    if(inputArray[currentIndex]>inputArray[nextIndex])
    {
        int temp = inputArray[nextIndex];
        inputArray[nextIndex] = inputArray[currentIndex];
        inputArray[currentIndex] = temp;
    }

    return bubbleSort(inputArray, passStartIndex, currentIndex + 1,length);
}

but when I execute it on input array of having length 50100, it shows me expcetion

System.StackOverflowException was unhandled Message: An unhandled exception of type 'System.StackOverflowException' occurred in example.exe

What am I doing wrong? How to fix it?

I saw the bug that @Benoit found, too, but I still can't see why the recursion does not terminate. The test of `passStartIndex` seems pretty solid. BTW, I ran this code on my Linux box and got a segmentation fault, not a stack overflow, though that might mean the same thing. However, the failure happened for me when length was 510, not 50100. I am thinking that the stack is getting clobbered somehow, not infinite recursion. Unfortunately, I don't have any more time for this. Good luck. — Randall Cook, Feb 12 '13 at 19:43

score 3 · Accepted Answer · edited Jun 20 '20 at 09:12

"What am I doing wrong?"

Each time recursive function calls itself, the call frame (activation record) is stored into the stack memory. So when the recursion gets too deep, which is the moment when you reach the maximum size of stack, the execution is terminated.

Also have a look at: Does C++ limit recursion depth?

"How to fix it?"

The easiest way how to avoid this problem is to never design your algorithm as a recursion at first place. But once you already have a recursive solution like this, in most cases it's possible to rewrite it into the loop form or (which is usually much easier): a tail recursion.

Basically if you can rewrite your function in a way that it never directly passes any arguments to the next call, you won. If you look at your recursion, there are 2 spots, where it calls itself and before the call is made, only currentIndex and passStartIndex are being changed. Imagine that you would store these indexes somewhere aside and the current function call would just signal "I'm done, these are values that someone should continue with: ... Now you may continue!", which means that state, the function is at, is not needed to be stored. By doing so you'll end up with a Tail call (see especially first example program).

Here's the full example of how it could be done with your code: Step 1, Step 2

Benoît Guédas · Answer 2 · 2013-02-13T13:33:19.687

It will not solve your problem (see recursion limit), but there is a mistake in the algorithm that you used. You should replace

if (currentIndex == length - 1)
    return bubbleSort(inputArray, passStartIndex+1, passStartIndex+1, length);

by

if (currentIndex == length - 1)
    return bubbleSort(inputArray, passStartIndex+1, 0,length - 1);

The bubble sort should restart to 0, because the first item is not at the right place, but the last one is.

Encountering stack overflow while implementing recursive Bubble sort

2 Answers2

"What am I doing wrong?"

"How to fix it?"