c++ - 当我在快速排序算法的递归调用中包含主元时，为什么会出现堆栈溢出？

Question

我正在尝试将 C++ 中的快速排序算法作为讲座中的一个项目来实现。当我从递归调用中排除枢轴时，程序运行良好，但当我在任一递归调用中包含枢轴时，有时会导致堆栈溢出错误。

程序仅针对特定的数组大小出现故障，但我无法弄清楚它们与错误有什么关系。例如，当我给 40 时程序出现故障，但给 50 时程序运行正常。

void quicksort(double* arr, int init, int fin) {
    if (init == fin) return;
    if (init == fin - 1) {
        if (arr[init] > arr[fin]) {
            double temp = arr[fin];
            arr[fin] = arr[init];
            arr[init] = temp;
        }
        return;
    }
    int smaller = init - 1;
    double pivot = arr[fin];
    for (int ind = init; ind < fin; ind++) {
        if (arr[ind] < pivot) {
            smaller++;
            double temp = arr[ind];
            arr[ind] = arr[smaller];
            arr[smaller] = temp;
        }
    }
    arr[fin] = arr[smaller + 1];
    arr[smaller + 1] = pivot;
    if(smaller>=init) quicksort(arr, init, smaller);
    if(smaller+2<=fin) quicksort(arr, smaller + 2, fin);
    return;
}

这是有问题的代码。当我这样写时它工作正常，但当我替换时会导致错误

if(smaller+2<=fin) quicksort(arr, smaller + 2, fin);

与

if(smaller+1<=fin) quicksort(arr, smaller + 1, fin);

Answer 1

if(smaller+1<=fin)相当于if(true) (因为 smaller+1 开始时是 init 并且最多递增 fin-init 次)，所以任何至少包含三个元素的调用都必然会在该行递归——递归调用可能不会完成任何事情，如果(例如) 所有三个元素都相等。