Обнаружено переполнение стека при реализации рекурсивной сортировки Bubble.
Эй, я преобразовал этот код C # на с ++ как
void bubbleSort(int *inputArray, int passStartIndex, int currentIndex,int length)
{
if(passStartIndex == length - 1) return;
if(currentIndex == length - 1) return bubbleSort(inputArray, passStartIndex+1, passStartIndex+1,length);
//compare items at current index and current index + 1 and swap if required
int nextIndex = currentIndex + 1;
if(inputArray[currentIndex]>inputArray[nextIndex])
{
int temp = inputArray[nextIndex];
inputArray[nextIndex] = inputArray[currentIndex];
inputArray[currentIndex] = temp;
}
return bubbleSort(inputArray, passStartIndex, currentIndex + 1,length);
}
но когда я выполняю его на входном массиве, имеющем длину 50100, он показывает мне исключение
System.StackOverflowException было необработанным. Сообщение: необработанное.
исключение типа «System.StackOverflowException» произошло в example.exe
Что я делаю неправильно? Как это исправить?
Решение
«Что я делаю неправильно?»
Каждый раз, когда рекурсивная функция вызывает себя, кадр вызова (запись активации) хранится в памяти стека. Поэтому, когда рекурсия становится слишком глубокой, то есть в тот момент, когда вы достигаете максимального размера стека, выполнение прекращается.
Также посмотрите на: Ограничивает ли C ++ глубину рекурсии?
«Как это исправить?»
Самый простой способ избежать этой проблемы — никогда не создавать свой алгоритм как рекурсию. Но если у вас уже есть рекурсивное решение, подобное этому, в большинстве случаев его можно переписать в виде цикла или (что обычно намного проще): a хвостовая рекурсия.
По сути, если вы можете переписать свою функцию так, чтобы она никогда напрямую не передавала аргументы следующему вызову, вы выиграли. Если вы посмотрите на свою рекурсию, есть 2 места, где она звонит сама и до того, как звонок сделан, только currentIndex а также passStartIndex меняются. Представьте, что вы будете хранить эти индексы где-то в стороне, и текущий вызов функции будет просто сигнализировать «Я закончил, это те ценности, с которыми кто-то должен продолжать: … Теперь вы можете продолжать!», Это означает, что состояние, в котором находится функция, не нужно хранить. Тем самым вы получите Хвостовой вызов (особенно программа первого примера).
Вот полный пример того, как это можно сделать с вашим кодом: Шаг 1, Шаг 2
Другие решения
Это не решит вашу проблему (см. Предел рекурсии), но в алгоритме, который вы использовали, есть ошибка. Вы должны заменить
if (currentIndex == length - 1)
return bubbleSort(inputArray, passStartIndex+1, passStartIndex+1, length);
от
if (currentIndex == length - 1)
return bubbleSort(inputArray, passStartIndex+1, 0,length - 1);
Сортировка пузырьков должна перезапуститься до 0, потому что первый элемент находится не в нужном месте, а последний.