超过最大递归深度.堆栈溢出异常 [英] Maximum recursion depth exceeded. Stack overflow exception

问题描述

我目前正在编写一种算法来分析排序算法.我有很多输入，从1000个数字到1000000个输入.目前，我在使用快速排序功能时遇到了一些问题.由于我输入了100万个相似的数字(1-10之间的数字)，因此此代码将引发错误(0xC00000FD)(似乎是堆栈溢出异常).现在，我不知道该如何减少递归调用的数量或如何增加堆栈，以便可能会有多个递归调用.我正在附上快速排序"的代码.

I am currently writing an algorithm to analyze the sorting algorithms. I have many inputs from 1000 numbers up to 1 000 000 inputs. Currently I'm having some problems with the Quick Sort function. As I have an input of 1 000 000 of similar numbers (numbers between 1-10) this code will throw me an error (0xC00000FD) (seems to be an stack overflow exception). Now, I don't know what to do to lower the numbers of recursion calls or how to increase the stack so there could be multiple recursion calls. I'm attaching the code for the Quick Sort.

void swap(int *xp, int *yp)
    {
        int temp = *xp;
        *xp = *yp;
        *yp = temp;
    }

int partition (int arr[], int low, int high)
{
    int pivot = arr[(low+high)/2];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
void quicksort(int A[], int l, int h)
{
    if (l < h) {
        int p = partition(A, l, h);
        quicksort(A, l, p - 1);
        quicksort(A, p + 1, h);
    }
}

推荐答案

如果在递归过程中出现堆栈溢出，则意味着递归被破坏了.通常应避免使用递归，因为它具有创建缓慢而危险的算法的巨大潜力.如果您是新手程序员，那么我强烈建议您不要忘记您曾经听说过递归并在这里停止阅读.

If you get stack overflows during recursion, it means that your recursion is broken. Recursion in general should be avoided since it has a huge potential for creating slow and dangerous algorithms. If you are a beginner programmer, then I would strongly advise to simply forget that you ever heard about recursion and stop reading here.

唯一合理的时间是将递归调用放在函数的末尾，即所谓的尾调用递归".这几乎是编译器可以实际优化并替换为内联循环的唯一形式的递归.

The only time it can be reasonably allowed is when the recursive call is placed at the end of the function, so-called "tail call recursion". This is pretty much the only form of recursion that the compiler can actually optimize and replace with an inlined loop.

如果它无法执行尾部调用优化，则意味着每次执行递归时实际上都会调用一个函数.这意味着堆栈不断堆积，并且您还会获得函数调用开销.这既不必要地缓慢又危险到令人无法接受的程度.因此，您曾经编写的所有递归函数都必须针对目标进行反汇编，以确保代码没有麻烦.

If it cannot perform tail-call optimization, then it means that a function is actually called each time you do recursion. Meaning that the stack keeps piling up and you also get function call overhead. This is both needlessly slow and unacceptably dangerous. All recursive functions you ever write must therefore be disassembled for the target, to see that the code has not gone haywire.

由于该代码似乎来自本网站 https://www.geeksforgeeks.org/iterative-quick-sort/，他们已经在这里为您的代码描述了其中的大多数问题.它们具有一个"quickSortIterative".底部的功能，这是一个更好的实现.

Since this code seems to be taken from this site https://www.geeksforgeeks.org/iterative-quick-sort/, they already described most of these problems with the code for you there. They have a "quickSortIterative" function at the bottom which is a much better implementation.

我认为本教程的目的是向您展示一些残破的代码(问题中的代码)，然后通过消除递归来演示如何正确编写代码.

My take is that the aim of the tutorial is to show you some broken code (the code in your question) then demonstrate how to write it correctly, by getting rid of the recursion.

这篇关于超过最大递归深度.堆栈溢出异常的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！