函数递归调用时堆栈溢出

Question

我正在尝试制作一个链排序算法，当我尝试再次递归调用它时，它给我堆栈溢出错误

递归调用是我想将数组 a 排序为两个排序数组（preme、NoNpreme）的地方。之后我将它们合并回一个。我试图弄乱条件，我发现当只有 1 个元素时数组被排序，这是我的递归出口。但它不起作用，我不知道为什么。

我的算法：

int* urediSPrameni(int* a, int n)
{
    if (n <= 1)
        return a;

    int pe=a[0];
    int* preme = new int[n];
    preme[0] = a[0];
    int j = 1;
    int k = 0;
    int* NoNpreme = new int[n];
    for(int i=0;i<n;i++)
    {
        if (a[i] > pe)
        {
            pe = a[i];
            preme[j] = a[i];
            j++;
        }
        else
        {
            NoNpreme[k] = a[i];
            k++;
        }
    }
    NoNpreme = urediSPrameni(NoNpreme, k);


    // My merge algorithm:

    //Zlivanje
    int h = 0;//NoNpreme
    int s = 0;//Preme
    int i = 0;
    while (h < k && s < j)
    {
            if (preme[h] <= NoNpreme[s])
            {
                a[i] = preme[h];
                s++;
            }
            else
            {
                a[i] = NoNpreme[s];
                h++;
            }
            i++;
    }
    if (h > k)
    {
        for (int b = s;b < j;b++)
        {
            a[i] = NoNpreme[b];
            i++;
        }
    }
    else
    {
        for (int b = h;b < k;b++)
        {
            a[i] = preme[b];
            i++;
        }
    }
    return a;
}

我这样调用函数：

int n = 7;
int drek[] = { 5,1,2,20,5,28,7 };
int* urejenoZap = urediSPrameni(drek, n);
for (int i = 0;i < n;i++)
    cout << urejenoZap[i] << " ";
system("PAUSE");

其中 drek 未排序，urejenoZap 是指向已排序数组的指针 drek。

Answer 1

您将 a 的第一个元素分配给 pe，并将该元素的副本存储到 preme。当根据它们落在 pe 的哪一侧将 a 的元素排序到单独的数组中时，您再次从元素 0 开始（您已经将其放入 preme），其中，因为 if (a[i] > pe) 将是 false，所以会将此元素放入 NoNpreme。一旦数组到达有多个元素的点，并且第一个元素是最小的，所有个元素将被复制到NoNpreme中。此后的每个递归调用都会执行相同的操作，因此递归将永远不会结束，您最终会运行出栈 space.

解决方案是用第二个元素开始你的 for 循环：

for (int i = 1; i < n; i++)

函数递归调用时堆栈溢出

Stack overflow on recursive call of a function

c++

stack-overflow

recursion

function