c++ - 我的递归函数中的堆栈溢出，是由于逻辑还是大数导致的？

Question

当我在一个小数组上运行我的函数时，它工作得很好。但是，当我使用大数组时，我不断出现堆栈溢出。 是因为我的代码逻辑不正确吗？或者只是需要很长时间？

void RecursiveSort(T data[], int first, B last)
{

    // Sorts the array elements a[first] through a[last] recursively.

    // base case is if first and last are the same, which means we 
    // have no subarrays left to do



    if (first < last)
    {
        int minIndex = first;
        // replace first index of array with smallest of values in  the array 

        for (int index = first+1; index < last; index++)
        {
            if (data[index] < data[minIndex])
                // swap values
                minIndex = index;
        }   


        int temp = data[first];
        data[first] = data[minIndex];
        data[minIndex] = temp;



        RecursiveSort(data, first + 1, last);

    }


}

Answer 1

您看到堆栈溢出错误只是因为您的堆栈大小有限。每次调用递归函数时，您都会使用一定量的内存来存储一些值，例如要返回的地址、函数参数的值等 - 请参阅 this Wikipedia article了解更多信息。

根据经验，如果您的递归深度超过 1000 级，您可能会遇到麻烦。

好消息是您的代码是 tail recursion 的示例，其中递归调用是函数中的最后一条语句。此类函数可以轻松转换为循环:

for (first = 0; first < last; ++first) {
     ...
}

或者，如果您确实需要创建递归排序，请不要尝试实现选择排序，而是查看 Quicksort或merge sort ，两者都可以使用递归来实现。