Слишком глубокий уровень рекурсии стек переполнен

В программном обеспечении переполнение стека (англ. stack overflow ) возникает, когда в стеке вызовов хранится больше информации, чем он может вместить. Обычно ёмкость стека задаётся при старте программы/потока. Когда указатель стека выходит за границы, программа аварийно завершает работу. [1]

Эта ошибка случается по трём причинам. [2]

Содержание

Бесконечная рекурсия [ править | править код ]

Простейший пример бесконечной рекурсии на Си:

Функция будет вызывать сама себя, расходуя пространство в стеке, пока стек не переполнится и не случится ошибка сегментации. [3]

Это рафинированный пример, и в реальном коде бесконечная рекурсия может появиться по двум причинам:

Не сработало условие выхода из рекурсии [ править | править код ]

Частая причина бесконечной рекурсии — когда при каких-то крайних непроверенных обстоятельствах условие окончания рекурсии вообще не сработает.

Программа уйдёт в бесконечную рекурсию при отрицательном n.

Многие языки делают оптимизацию, именуемую «хвостовая рекурсия». Рекурсия, находящаяся в конце функции, превращается в цикл и не расходует стека [4] . Если такая оптимизация сработает, вместо переполнения стека будет зацикливание.

Программист написал рекурсию, не осознавая того [ править | править код ]

Программист может написать рекурсию и ненамеренно — например, когда одну и ту же функциональность выполняют несколько перегруженных функций, и одна вызывает другую.

В интерфейсных фреймворках наподобие Qt и VCL рекурсия может случиться, если в обработчике, например, изменения поля программист сам же это поле и изменит.

Очень глубокая рекурсия [ править | править код ]

Уничтожить односвязный список можно таким кодом:

Этот алгоритм, если список не испорчен, теоретически выполнится за конечное время, затребовав при этом O(n) стека. Разумеется, при длинном списке программа откажет. Возможные решения:

  • Найти нерекурсивный алгоритм (работает в данном примере).
  • Перенести рекурсию из аппаратного стека в динамически выделяемый (например, при обходе разного рода сетей [5] ).
  • Если рекурсия зашла глубоко, применять другой метод. Например, быстрая сортировка — чрезвычайно эффективный метод сортировки, который в крайних случаях может задействовать немалый объём стека. Поэтому реализации сортировки в языках программирования ограничивают глубину рекурсии, а если «упёрлись» в предел, используют более медленные методы наподобие пирамидальной. Так работает, например, Introsort.

Большие переменные в стеке [ править | править код ]

Третья большая причина переполнения стека — одноразовое выделение огромного количества памяти крупными локальными переменными. Многие авторы рекомендуют выделять память, превышающую несколько килобайт, в «куче», а не на стеке. [6]

Массив занимает 8 мегабайт памяти; если в стеке нет такого количества памяти, случится переполнение.

Всё, что уменьшает эффективный размер стека, увеличивает риск переполнения. Например, потоки обычно берут стека меньше, чем основная программа — поэтому программа может работать в однопоточном режиме и отказывать в многопоточном. Работающие в режиме ядра подпрограммы часто пользуются чужим стеком, поэтому при программировании в режиме ядра стараются не применять рекурсию и большие локальные переменные. [7] [8]

Читайте также:  Расширение без рекламы яндекс

"Ошибка установки" Слишком глубокая рекурсия; стек переполнен 0x800703E9.

У меня Windows 10 и новейшая версия Visual Studio. Я попытался перезагрузиться, чтобы убедиться, что у меня есть как можно больше ресурсов. У меня есть 4 г оперативной памяти.

3 ответа

Видимо, существует несоответствие установщика между последними версиями SSDT и Visual Studio. Предлагаемое исправление состоит в том, чтобы начать с предыдущей установки Visual Studio 2017, установить поверх этого последнюю версию SSDT, а затем обновить Visual Studio. Это очень трудоемкое исправление. Похоже, что это необходимо только для компонентов SSIS – компоненты SSAS и SSRS доступны как расширения в VS, и я считаю, что они все еще успешно устанавливаются оттуда.

Пожалуйста, перезапустите установщик VS community 2017 или перейдите в Панель управления – Программы и компоненты, удалите предыдущую версию SSDT для VS 2017, а затем переустановите ее, вы можете посмотреть на эту похожую проблему .

Если проблема не устранена, используйте http://aka.ms/vscollect для сбора журналов установки и найдите vslogs.zip в папке% temp%, затем загрузите файл в Onedrive и поделитесь ссылкой здесь.

Если установщик SSDT предоставляет вам несколько экземпляров Visual Studio, попробуйте «новый» вариант.

Я столкнулся с этой проблемой, пытаясь установить SSDT 15.8.1 на Windows Server 2012 R2 с уже установленной последней версией Visual Studio 2017 (v15.8.6). Установщик SSDT дал мне 2 варианта в выпадающем списке.

Установите инструменты для этого экземпляра Visual Studio 2017:

  • Visual Studio 2017
  • Установите новые инструменты данных SQL Server для Visual Studio 2017

Когда я выбрал первый вариант: Visual Studio 2017 (предположительно существующий экземпляр), я столкнулся с загадочной ошибкой «слишком глубокая рекурсия». Я установил расширение SSRS для VS (как это было предложено другими при переполнении стека) и снова попытался запустить установщик SSDT для существующего экземпляра Visual Studio 2017. Я получил ту же ошибку "рекурсии".

Я попробовал еще раз, но на этот раз выбрал «Установить новые инструменты данных SQL Server для Visual Studio 2017». На этот раз процесс установки завершен!

Определение

Переполнение стека – программная ошибка времени выполнения, при которой программа захватывает всю память, выделенную ей под стек, что обычно приводит к аварийному завершению её работы.

Стек программы

Стек программы – это специальная области памяти, организованная по принципу очереди LIFO (Last in, first out – последним пришел, первым ушел). Название "стек" произошло из-за аналогии принципа его построения со стопкой (англ. stack) тарелок – можно класть тарелки друг на друга (метод добавления в стек, "заталкивание", "push"), а затем забирать их, начиная с верхней (метод получения значения из стека, "выталкивание", "pop"). Стек программы также называют стек вызовов, стек выполнения, машинным стеком (чтобы не путать его со "стеком" – абстрактной структурой данных).

Читайте также:  Саундбар sharp ht sb140mt отзывы

Для чего нужен стек? Он позволяет удобно организовать вызов подпрограмм. При вызове функция получает некоторые аргументы; также она должна где-то хранить свои локальные переменные. Кроме того, надо учесть, что одна функция может вызвать другую функцию, которой тоже надо передавать параметры и хранить свои переменные. Используя стек, при передаче параметров нужно просто положить их в стек, тогда вызываемая функция сможет их оттуда "вытолкнуть" и использовать. Локальные переменные тоже можно хранить там же – в начале своего кода функция выделяет часть памяти стека, при возврате управления – очищает и освобождает. Программисты на высокоуровневых языках обычно не задумываются о таких вещах – весь необходимый рутинный код за них генерирует компилятор.

Последствия ошибки

Теперь мы подошли почти вплотную к проблеме. В абстрактном виде стек представляет собой бесконечное хранилище, в которое можно бесконечно добавлять новые элементы. К сожалению, в нашем мире все конечно – и память под стек не исключение. Что будет, если она закончится, когда в стек заталкиваются аргументы функции? Или функция выделяет память под свои переменные?

Произойдет ошибка, называемая переполнением стека. Поскольку стек необходим для организации вызова пользовательских функций (а практически все программы на современных языках, в том числе объектно-ориентированных, так или иначе строятся на основе функций), больше они вызываться не смогут. Поэтому операционная система забирает управление, очищает стек и завершает программу. Здесь можно подчеркнуть различие между переполнением буфера и переполнением стека – в первом случае ошибка происходит при обращении к неверной области памяти, и если защита на этом этапе отсутствует, в этот момент не проявляет себя – при удачном стечении обстоятельств программа может отработать нормально. Если только память, к которой шло обращение, была защищена, происходит ошибка сегментации. В случае со стеком программа непременно завершается.

Чтобы быть совсем точным, следует отметить, что подобное описание событий верно лишь для компиляторов, компилирующих в "родной" (native) код. В управляемых языках у виртуальной машины есть свой стек для управляемых программ, за состоянием которого гораздо проще следить, и можно даже позволить себе при возникновении переполнения передать программе исключение. В языках Си и Си++ на подобную "роскошь" рассчитывать не приходится.

Причины ошибки

Что же может привести к такой неприятной ситуации? Исходя из описанного выше механизма, один из вариантов – слишком большое число вложенных вызовов функций. Особенно вероятен такой вариант развития событий при использовании рекурсии. Бесконечная рекурсия (при отсутствии механизма "ленивых" вычислений) прерывается именно таким образом, в отличие от бесконечного цикла, который иногда имеет полезное применение. Впрочем, при небольшом объеме памяти, отведенной под стек (что, например, характерно для микроконтроллеров), достаточно может быть и простой последовательности вызовов.

Другой вариант – локальные переменные, требующие большого количества памяти. Заводить локальный массив из миллиона элементов, или миллион локальных переменных (мало ли что бывает) – не самая лучшая идея. Даже один вызов такой "жадной" функции легко может вызвать переполнение стека. Для получения больших объемов данных лучше воспользоваться механизмами динамической памяти, которая позволит обработать ошибку её нехватки.

Читайте также:  Сервис поиска по лицам

Однако динамическая память является довольно медленной в плане выделения и освобождения (поскольку этим занимается операционная система), кроме того, при прямом доступе приходится вручную выделять её и освобождать. Память же в стеке выделяется очень быстро (по сути, надо лишь изменить значение одного регистра), кроме того, у объектов, выделенных в стеке, автоматически вызываются деструкторы при возврате управления функцией и очистке стека. Разумеется, тут же возникает желание получить память из стека. Поэтому третий путь к переполнению – самостоятельное выделение в стеке памяти программистом. Специально для этой цели библиотека языка Си предоставляет функцию alloca. Интересно заметить, что если у функции для выделения динамической памяти malloc есть свой "близнец" для её освобождения free, то у функции alloca его нет – память освобождается автоматически после возврата управления функцией. Возможно, это только осложняет ситуацию – ведь до выхода из функции освободить память не получится. Даже несмотря на то, что согласно man-странице "функция alloca зависит от машины и компилятора; во многих системах ее реализация проблематична и содержит много ошибок; ее использование очень несерьезно и не одобряется" – она все равно используется.

Примеры

В качестве примера рассмотрим код для рекурсивного поиска файлов, расположенный на MSDN:

Эта функция получает список файлов указанной директории, а затем вызывает себя же для тех элементов списка, которые оказались директориями. Соответственно, при достаточно глубоком дереве файловой системы, мы получим закономерный результат.

Пример второго подхода, взятый из вопроса "Почему происходит переполнение стека?" с сайта под названием Stack Overflow (сайт является сборником вопросов и ответов на любые программистские темы, а не только по переполнению стека, как может показаться):

Как видно, в функции main выделяется память в стеке под массивы типов int и float по миллиону элементов каждый, что в сумме дает чуть менее 8 мегабайт. Если учесть, что по умолчанию Visual C++ резервирует под стек лишь 1 мегабайт, то ответ становится очевидным.

А вот пример, взятый из GitHub-репозитория проекта Flash-плеера Lightspark:

Можно надеятся, что h.getLength()-7 не будет слишком большим числом, чтобы на следующей строчке не произошло переполнения. Но стоит ли сэкономленное на выделении памяти время "потенциального" вылета программы?

Переполнение стека – фатальная ошибка, которой наиболее часто страдают программы, содержащие рекурсивные функции. Однако даже если программа не содержит таких функций, переполнение все равно возможно из-за большого объема локальных переменных или ошибки в ручном выделении памяти в стеке. Все классические правила остаются в силе: если есть возможность выбора, вместо рекурсии лучше предпочесть итерацию, а также не заниматься ручной работой вместо компилятора.

Leave a Reply

Ваш адрес email не будет опубликован. Обязательные поля помечены *

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>