c++ - 在实现递归Bubble排序时遇到堆栈溢出

嘿，我将this C# code转换为c++

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

但是当我在长度为50100的输入数组上执行它时，它显示了期望



我究竟做错了什么？如何解决？

最佳答案

“我做错了什么？”
每次递归函数调用自身时，调用帧(激活记录)都会存储到堆栈存储器中。因此，当递归变得太深时(即达到最大堆栈大小的那一刻)，执行将终止。
还可以看看:Does C++ limit recursion depth?

“如何解决？”
避免此问题的最简单方法是一开始就永远不要将算法设计为递归。但是一旦有了这样的递归解决方案，在大多数情况下，就可以将其重写为循环形式，或者(通常更容易):尾递归。
基本上，如果您可以通过不将任何参数直接传递给下一个调用的方式来重写函数，那么您就赢了。如果您查看递归，则有2个地方，它在其中进行自我调用，并且在进行调用之前，仅currentIndex和passStartIndex被更改。想象一下，您会将这些索引存储在旁边，并且当前函数调用将仅发出信号:“我已经完成了，这些值是某些人应该继续的:...现在您可以继续!”，这意味着状态为处，无需存储。这样，您最终会得到 Tail call (尤其是first example program)。
这是如何使用您的代码完成操作的完整示例:Step 1，Step 2

关于c++ - 在实现递归Bubble排序时遇到堆栈溢出，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14839315/