c++ - 实现递归冒泡排序时遇到栈溢出

Question

嘿，我转换了 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 的输入数组上执行它时，它显示了期望值

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

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

Answer 1

“我做错了什么？”

每次递归函数调用自身时，调用帧(激活记录)都会存储到堆栈内存中。因此，当递归变得太深时，即达到堆栈的最大大小时，执行将终止。

另请参阅:Does C++ limit recursion depth?

---

“如何解决？”

避免此问题的最简单方法是永远不要一开始就将算法设计为递归。但是一旦您已经有了这样的递归解决方案，在大多数情况下，可以将其重写为循环形式或(这通常更容易):尾递归。

基本上，如果您能以一种从不直接将任何参数传递给下一个调用的方式重写您的函数，您就赢了。如果你看看你的递归，有 2 个地方，它调用自己，在调用之前，只有 currentIndex 和 passStartIndex 被改变。想象一下，您将这些索引存储在某个地方，而当前的函数调用只会发出信号 “我完成了，这些是某人应该继续使用的值:……现在您可以继续了!”，这意味着不需要存储状态，即功能所在的状态。通过这样做，你最终会得到一个 Tail call (特别参见 first example program)。

这是如何使用您的代码完成此操作的完整示例: Step 1 , Step 2