c++ - 合并排序导致堆栈溢出？

Question

我用 C++ 为链表编写了 mergesort()。问题是我的教授提供了一个非常大的列表(长度为 575,000)的测试代码。这会导致我的函数发生堆栈溢出错误，因为它是递归编写的。

所以我的教授可能希望我们使用迭代而不是递归来编写它。我想问下是不是我的代码有什么问题导致栈溢出？

我的代码:

typedef struct listnode {
    struct listnode * next;
    long value; 
} LNode;

LNode* mergesort(LNode* data) {
    if(data == NULL || data->next == NULL) {
        return data;
    }else {
        LNode* s = split(data);

        LNode* firstSortedHalf = mergesort(data);
        LNode* secondSortedHalf = mergesort(s);

        LNode* r = merge(firstSortedHalf, secondSortedHalf);
        return r;
    }
}

LNode* split(LNode* list) {
    if(list) {
        LNode* out = list->next;

        if(out) {
            list->next = out->next;
            out->next = split(out->next);
        }
        return out;
    }else {
        return NULL;
    }
}

LNode* merge(LNode* a, LNode* b) {
    if(a == NULL)
        return b;
    else if(b == NULL)
        return a;

    if(a->value < b->value) {
        a->next = merge(a->next,b);
        return a;
    }else {
        b->next = merge(a, b->next);
        return b;
    }
}

Answer 1

所以你有三个递归函数。让我们看一下每个元素的最大深度，其中包含 575000 个元素的列表的最坏情况:

• merge():这看起来会遍历整个列表。所以 575000 个堆栈帧。
• split():这看起来是成对迭代整个列表。所以 ~250000 个堆栈帧。
• mergesort():这看起来以拆分方式进行迭代。所以 log_2(575000) 或大约 20 个堆栈帧。

因此，当我们运行我们的程序时，我们会获得有限的堆栈空间来容纳我们所有的堆栈帧。在我的计算机上，默认限制约为 10 兆字节。

粗略估计每个堆栈帧占用 32 个字节。对于 merge() 的情况，这意味着它将占用大约 18 MB 的空间，这远远超出了我们的限制。

虽然 mergesort() 调用自身，但只有 20 次迭代。这应该符合任何合理的限制。

因此，我的结论是，merge() 和 split() 不应以递归方式实现(除非该方式是尾递归且已开启优化) .