Почему эта рекурсивная функция для поиска элемента в списке вызывает переполнение стека?

Я определил базовую структуру списка и простой insert функция и search функция. Код ниже:

////////////////////////////////////////////////
typedef struct list
{
int item;
struct list *next;
}List;

////////////////////////////////////////////////
List * search_list(List * l, int i)
{
if(NULL == l)
return(NULL);

if(i == l->item)
return l;
else
return search_list(l->next, i);
}

////////////////////////////////////////////////
void insert_list(List ** l, int i)
{
List * p = new List();
p->item = i;
p->next = *l;
*l = p;
}

Мой основной цикл для его проверки выглядит так:

int main(int, char* argv[])
{
List * mylist = new List();

for(int i = 0; i < 8000; i++)
{
insert_list(&mylist,i);
}

int val = 2000;
List * s = search_list(mylist, val);
return 0;
}

когда val 4000, программа завершает нормально. Но когда val равно 2000, то есть 2000 индексов далее вниз по списку, Visual Studio завершается переполнением стека.

Количество рекурсивных вызовов в search_list() вызывая переполнение стека? Как я могу избавиться от этой ошибки?

2

Решение

Рекурсивные алгоритмы должны использоваться только в том случае, если глубина строго ограничена или алгоритм имеет не более O (logN) сложность. Если это не так, то вы всегда переполнение стека рисков. Ваш не соответствует требованию сложности, это O (N).

Visual Studio не помогает избежать сбоев при запуске вашей программы с настройками сборки Debug по умолчанию. Во-первых, оптимизация хвостовой рекурсии не включена, для этого требуются параметры сборки выпуска, чтобы оптимизатор был включен. Для другого, функция «Правка + Продолжить» выделяет кучу дополнительный пространство стека для функции. Это доступно, если вы добавляете локальную переменную в функцию во время отладки.

Вы можете легко отключить это. Project + Properties, C / C ++, General, измените настройку формата отладочной информации на «Program Database (/ Zi)». Ваша программа больше не будет зависать.

3

Другие решения

Ваш компилятор должен был сказать вам одну вещь: этот рекурсивный вызов search_list ничего не возвращает. Разве вы не получили предупреждение об этом? И использование рекурсии здесь действительно плохая идея, лучше замените ее каким-то циклом. Одна из причин, конечно, — чрезмерное использование стека, другая — отладка отстой с такой рекурсией.

1

Помимо вашей ошибки переполнения стека, вы должны проверить следующее. Вы не инициализируете значения первого выделенного List экземпляр в main()указал mylist,

List * mylist = new List();

То, что делает ваш текущий код, передает «пустой» List экземпляр при первом вызове, который может иметь недопустимый next значение. Это будет твой последний List экземпляр в связанном списке.

Вы должны сделать это вместо этого:

List * mylist = NULL;

Это заверит вас в прошлом List Экземпляр в списке имеет next с NULL значение.

0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector