Что произойдет со стеком при бесконечном выполнении рекурсии
Что такое StackOverflow ошибка: раскрываем тайну
Ошибка «stack overflow» связана с переполнением стека. Она появляется в том случае, когда в стеке должно сохранит ь ся больше информации, чем он может уместить. Объем памяти стека задает программист при запуске программы. Если в процессе выполнения программы стек переполняется, тогда возникает ошибка « stack overflow » и программа аварийно завершает работу. Причин возникновения подобной ошибки может быть несколько.
Ошибка « stack overflow »
Нужно отметить, что ошибка « stack overflow » не связана с конкретным языком программирования, то есть она может возникнуть в программах на Java, C++, C, C# и других компилируемых языках.
Причин ее возникновения может быт ь несколько. К самым распространенным причинам относ я тся:
проблемы с переменными в стеке.
Бесконечная рекурсия и ошибка «stack overflow»
Бесконечная рекурсия редко возникает самостоятельно и по неизвестным причинам. Обычно программист:
забывает прописывать условие для выхода из рекурсии;
пишет неосознанную косвенную рекурсию.
Самая частая причина из категории «бесконечной рекурсии» — программист забывает прописывать условия выхода или же прописывает, но условия выхода не срабатывают.
Вот как это выглядит на С:
int factorial (int number)
Неосознанная бесконечная рекурсия возникает в том случае, если программист по невнимательности распределяет один и тот же функционал программы между разными нагруженными функциями, а потом делает так, что они друг друга вызывают.
В коде это выглядит так:
int Object::getNumber(int index, bool& isChangeable)
int Object::getNumber(int index)
return getNumber(index, noValue);
Глубокая рекурсия и ошибка «stack overflow»
отыскать другой программный алгоритм для решения поставленной задачи, чтобы избежать применени я рекурсии;
«вынести» рекурсию за пределы аппаратного стека в динамический;
Глубокая рекурсия выглядит так:
void eliminateList(struct Item* that)
Проблемы с переменными в стеке и ошибка «stack overflow»
Если взглянуть на популярность возникновения «stack overflow error», то причина с проблемными переменными в стеке стоит на первом месте. Кроется она в том, что программист изначально выделяет слишком много памяти локальной переменной.
Заключение
Мы будем очень благодарны
если под понравившемся материалом Вы нажмёте одну из кнопок социальных сетей и поделитесь с друзьями.
Как происходит «переполнение стека» и как его предотвратить?
Как происходит переполнение стека и как лучше всего этого избежать или как предотвратить его, особенно на веб-серверах, но были бы интересны и другие примеры?
Когда вы вызываете функцию в своем коде, следующая инструкция после вызова функции сохраняется в стеке и любое пространство памяти, которое может быть перезаписано вызовом функции. Вызываемая функция может использовать больше стека для собственных локальных переменных. Когда это будет сделано, он освобождает используемое пространство стека локальной переменной, а затем возвращается к предыдущей функции.
Переполнение стека
Многие программисты делают эту ошибку, вызывая функцию A, которая затем вызывает функцию B, которая затем вызывает функцию C, которая затем вызывает функцию A. Она может работать большую часть времени, но только один раз неправильный ввод заставит ее навсегда войти в этот круг. пока компьютер не обнаружит, что стек слишком раздут.
Рекурсивные функции также являются причиной этого, но если вы пишете рекурсивно (т. Е. Ваша функция вызывает сама себя), вам необходимо знать об этом и использовать статические / глобальные переменные для предотвращения бесконечной рекурсии.
Обычно операционная система и язык программирования, который вы используете, управляют стеком, и это вне ваших рук. Вы должны посмотреть на свой граф вызовов (древовидную структуру, которая показывает из вашего main, что вызывает каждая функция), чтобы увидеть, насколько глубоко заходят ваши вызовы функций, и чтобы обнаружить циклы и рекурсию, которые не предназначены. Преднамеренные циклы и рекурсия необходимо искусственно проверять, чтобы исключить ошибки, если они вызывают друг друга слишком много раз.
Помимо хороших практик программирования, статического и динамического тестирования, на этих высокоуровневых системах мало что можно сделать.
Встроенные системы
Во встраиваемом мире, особенно в коде высокой надежности (автомобильный, авиационный, космический), вы выполняете обширный анализ и проверку кода, но вы также делаете следующее:
Языки и системы высокого уровня
Но на языках высокого уровня, работающих в операционных системах:
Веб-серверы
СОДЕРЖАНИЕ
Причины
Бесконечная рекурсия
Наиболее частой причиной переполнения стека является чрезмерно глубокая или бесконечная рекурсия, при которой функция вызывает себя так много раз, что места, необходимого для хранения переменных и информации, связанной с каждым вызовом, больше, чем может поместиться в стеке.
Очень глубокая рекурсия
Рекурсивная функция, которая завершается теоретически, но вызывает переполнение буфера стека вызовов на практике, может быть исправлена путем преобразования рекурсии в цикл и сохранения аргументов функции в явном стеке (вместо неявного использования стека вызовов). Это всегда возможно, потому что класс примитивных рекурсивных функций эквивалентен классу вычислимых функций LOOP. Рассмотрим этот пример в псевдокоде, подобном C ++ :
Примитивная рекурсивная функция, подобная той, что находится слева, всегда может быть преобразована в цикл, как на правой стороне.
Функция, подобная приведенному выше примеру слева, не будет проблемой в среде, поддерживающей оптимизацию хвостового вызова ; однако все еще можно создать рекурсивную функцию, которая может привести к переполнению стека на этих языках. Рассмотрим приведенный ниже пример двух простых целочисленных функций возведения в степень.
Обе pow(base, exp) функции, указанные выше, вычисляют эквивалентный результат, однако функция слева может вызвать переполнение стека, поскольку оптимизация хвостового вызова для этой функции невозможна. Во время выполнения стек для этих функций будет выглядеть так:
Обратите внимание, что функция слева должна хранить в своем стеке exp количество целых чисел, которые будут умножены, когда рекурсия завершится и функция вернет 1. Напротив, функция справа должна хранить только 3 целых числа в любой момент и вычисляет промежуточный результат, который передается его следующему вызову. Поскольку никакая другая информация, кроме текущего вызова функции, не должна храниться, оптимизатор хвостовой рекурсии может «отбрасывать» предыдущие кадры стека, исключая возможность переполнения стека.
Переменные очень большого стека
Другая основная причина переполнения стека возникает из-за попытки выделить в стеке больше памяти, чем может поместиться, например, путем создания слишком больших переменных локального массива. По этой причине некоторые авторы рекомендуют выделять массивы размером более нескольких килобайт динамически, а не в качестве локальной переменной.
Пример очень большой переменной стека в C :
В реализации C с 8-байтовыми числами с плавающей запятой двойной точности объявленный массив потребляет 8 мегабайт данных; если это больше памяти, чем доступно в стеке (как установлено параметрами создания потока или ограничениями операционной системы), произойдет переполнение стека.
Переполнение стека усугубляется всем, что уменьшает эффективный размер стека данной программы. Например, одна и та же программа, запущенная без нескольких потоков, может работать нормально, но как только будет включена многопоточность, программа выйдет из строя. Это связано с тем, что большинство программ с потоками имеют меньше места в стеке на поток, чем программа без поддержки потоков. Поскольку ядра обычно многопоточны, новичкам в разработке ядра обычно не рекомендуется использовать рекурсивные алгоритмы или большие стековые буферы.
Рекурсивный алгоритм. Переполнение стека
Во время выполнения моего алгоритма, много раз вызывается рекурсивный dfs, после чего я получаю
RuntimeError: maximum recursion depth exceeded in instancecheck
Такое ощущение, что происходит накопление рекурсивных вызовов за всё время работы программы. После превышения порога в сумме
программа падает. Как с этим бороться?
Я приведу псевдокод моего алгоритма:
Таким образом, в некоторый момент возникает вышеуказанная ошибка. Замечу, что данная ошибка возникает у меня уже не первый раз. Возникает она в любом месте, где есть достаточное количество вызовов рекурсивных алгоритмов с большой глубиной рекурсии.
Замечу, что в коде нет терминального условия, но это не означает, что код будет выполняться бесконечно. Прокомментирую. Мы рассматриваем граф G(V, E). Будем перебирать вершины, начиная с любой. Каждую вершину мы будем помечать, если мы в ней были. Это делается следующей командой:
Для каждой вершины мы перебираем всех её соседей:
Если в вершине-соседе мы были, то в неё заходить не следует. Если же нет, то перейдём в нее. Проверка были мы там или нет осуществляется так:
Далее переходим в вершину:
О конкретном алгоритме можно прочесть здесь. Но спешу заметить, что вопрос заключается не в алгоритме, а в принципах устройства python. Подробное описание кода я привёл лишь для того, чтобы снять сомнения в его работоспособности. Код взят лишь как пример и не более того.
Бесконечная рекурсия в C
учитывая программу C с бесконечной рекурсией:
Почему это приведет к переполнению стека. Я знаю, что это приводит к неопределенному поведению в C++ из следующих нити это бесконечная рекурсия UB? (и как боковой узел нельзя вызвать main() В C++). Однако, Valgrind говорит мне, что это приводит к переполнению стека:
и, наконец, программа заканчивается из-за ошибки сегментации:
это также неопределенное поведение в C, или это действительно должно привести к переполнению стека, а затем почему это приводит к переполнению стека?
1 я хотел бы знать, разрешена ли бесконечная рекурсия в C?
2 должно ли это привести к переполнению стека? (получил достаточный ответ)
13 ответов
всякий раз, когда вы вызываете функцию, аргументы помещаются в стек, что означает, что данные в сегменте стека «распределены». Когда функция вызывается, обратный адрес также выталкивается в стек процессором, поэтому он знает, куда возвращаться.
из этого следует, что, как только сегмент стека исчерпан, функция не может быть вызвана aynmore и исключение вызывается в ОС. Теперь могут произойти две вещи. Либо ОС перенаправляет исключение обратно в ваше приложение, которое вы увидите как переполнение стека. Или ОС может попытаться выделить дополнительное пространство для стека segemnt, до определенного предела, после чего приложение увидит стек переполнение.
поэтому этот код (я переименовал его в infinite_recursion () как main () не может быть вызван).
обновление
Что касается стандарта C99 для определения рекурсии, лучшее, что я нашел до сих пор, находится в разделе 6.5.2.2 пункт 11:
рекурсивные вызовы функций должны быть разрешены, как прямо, так и косвенно через любую цепочку других функций.
конечно, это не отвечает, определено ли, что происходит, когда стек переполняется. Однако, по крайней мере, это позволяет main вызывается рекурсивно, хотя это явно запрещено в C++ (раздел 3.6.1 пункт 3 и раздел 5.2.2 пункт 9).
будет ли программа повторяется бесконечно неразрешима. Ни один разумный стандарт никогда не потребует свойства, которое может быть невозможно проверить даже для соответствующих программ, поэтому ни один стандарт C, текущий или будущий, никогда не будет иметь ничего сказать о бесконечный рекурсия (так же, как никакой стандарт C никогда не потребует, чтобы соответствующие программы в конечном итоге остановились).
итерация становится бесконечной, если условие остановки ( if проверьте return из функции) удаляется. Из рекурсии возврата нет. Таким образом, информация, которая запоминается для каждого последующего вызова функции (local x и адрес вызывающего абонента) продолжает накапливаться, пока в ОС не закончится память для хранения этой информации.
это возможно реализовать бесконечно рекурсивную функцию, которая не переполняет «стек». На достаточных уровнях оптимизации многие компиляторы могут применить оптимизацию для удаления памяти, необходимой для запоминания чего-либо для хвост рекурсивный вызов. Например, рассмотрим программу:
в результатом этой бесконечной рекурсии является простой бесконечный цикл, и не будет переполнения «стека». Таким образом, бесконечная рекурсия разрешена, поскольку разрешены бесконечные циклы.
ваша программа, однако, не является кандидатом на оптимизацию хвостового вызова, поскольку рекурсивный вызов-это не последнее, что делает ваша функция. Ваша функция все еще имеет return оператор, который следует за рекурсивным вызовом. Поскольку есть еще код, который необходимо выполнить после возвращения рекурсивного вызова, оптимизатор не может удалить накладные расходы рекурсивного вызова. Он должен позволить вызову вернуться нормально, чтобы код после него мог выполняться. Таким образом, ваша программа всегда будет платить штраф за хранение обратного адреса вызывающего кода.
стандарт не говорит о «бесконечной рекурсии» в каких-либо конкретных терминах. Я собрал все, что, на мой взгляд, имеет отношение к вашему вопросу.
рекурсивные вызовы функций должны быть разрешены как прямо, так и косвенно через любую цепочку других функций.
для такого объекта, который имеет переменную тип массива длины, своя продолжительность жизни удлиняет от объявление объекта до выполнения программы объем декларация. Если область вводится рекурсивно, создается новый экземпляр объекта каждый раз.
стандарт говорит о сбоях выделения памяти во многих местах, но никогда в контексте объекта с автоматической продолжительностью хранения. Все, что явно не определено в стандарте, не определено, поэтому программа, которая не выделение объекта с автоматической продолжительностью хранения имеет неопределенное поведение. Это будет применяться одинаково между программой, которая просто имела очень длинную цепочку вызовов функций или слишком много рекурсивных вызовов.
всякий раз, когда вы делаете вызов функции (включая main ()), вызов функции «info» (например, аргументы) нажимается поверх стека. Эта информация выводится из стека при возврате функции. Но, как вы можете видеть в своем коде, вы делаете рекурсивный вызов main до вы вернетесь, поэтому стек продолжает расти, пока не достигнет своего предела и, следовательно, ошибка сегментации.
размер стека часто ограничен и определяется до выполнения (например, вашей операционной система.)
Это означает, что переполнение стека не ограничивается main (), а любыми другими рекурсивными функциями без надлежащего способа завершения его дерева (т. е. базовых случаев).
на достаточно высоких уровнях оптимизации компилятор может перезаписать рекурсию в цикл, если оптимизация хвостового вызова in применимо, что позволит избежать переполнения стека.
я хотел бы знать, разрешена ли бесконечная рекурсия в C?
в этой статье Compilers and Termination Revisited by John Regehr является ответом на вопрос C standard позволяет бесконечную рекурсию или нет, и после прочесывания стандарта меня не слишком удивляет, что выводы являются неоднозначными. Основная тяга статьи о бесконечных петлях и поддерживается ли она стандартом различных языки (включая C и C++ ), чтобы иметь не прекращающиеся исполнения. Насколько я могу судить, обсуждение относится и к бесконечной рекурсии, конечно, если мы можем избежать переполнения стека.
в отличие от C++ который говорит в разделе 1.10 Multi-threaded executions and data races абзац 24 :
рекурсивные вызовы функций разрешаются как прямо, так и косвенно через любую цепочку других функций.
который не ставит никаких ограничений на рекурсию и говорит об этом в разделе 5.1.2.3 Program execution абзац 5 :
как говорится в статье, Первое условие должно быть прямо вперед, чтобы удовлетворить, третье условие в соответствии со статьей на самом деле не охватывает прекращение. Таким образом, мы остаемся со вторым условием. Согласно статье неоднозначно, цитата из статьи выглядит следующим образом:
если речь идет о завершении программы, запущенной на абстрактной машине, то она бессмысленно выполняется, потому что наша программа не завершается. Если речь идет о завершении фактической программы, сгенерированной компилятором, то реализация C глючит, потому что данные, записанные в файлы (stdout-это файл), отличаются от данных, записанных абстрактной машиной. (Это чтение принадлежит Гансу Бему; мне не удалось вывести эту тонкость из стандарта.)
Итак, у вас есть это: поставщики компиляторов читают стандарт в одну сторону, а другие (например, я) читают его в другую сторону. Совершенно ясно, что стандарт ошибочен: он должен, как C++ или Java, быть однозначным относительно того, разрешено ли это поведение.
поскольку кажется, что есть две разумные, но противоречивые интерпретации второго условие стандарт является недостаточным и должен явно определять, разрешено ли такое поведение.
раздел стека основной памяти не бесконечен, поэтому, если вы вызываете функцию рекурсивно неопределенное количество раз, стек будет заполнен информацией о каждом вызове одной функции. Это приводит к Переполнение Стека, когда больше нет места для использования для любого другого вызова функции.
важно понять, как выглядит вызывающий стек функций в C:
бесконечная рекурсия разрешено в C? Простой ответ: да. Компилятор позволит вам вызывать функцию бесконечно, пока у вас не закончится пространство стека; это не помешает вам сделать это.
бесконечная рекурсия возможно? Нет. Как уже указывалось, каждый вызов функции требует, чтобы обратный адрес был помещен в стек программы вместе с любыми параметрами, необходимыми для работы функции. Ваша программа имеет только ограниченный стек размер, и как только вы используете свой стек, ваше приложение потерпит неудачу.
возможна ли поддельная бесконечная рекурсия? Да. Можно создать функцию, которая вызывает себя 1000 раз, а затем позволяет выйти из 1000 вызовов функций, так что стек имеет только исходный вызов функции в стеке. а затем повторите весь процесс снова и снова в бесконечном цикле. Однако я не считаю эту реальную бесконечную рекурсию.
бесконечная рекурсия разрешена в C. Во время компиляции компилятор разрешит это, но при этом вы можете получить ошибку времени выполнения.
рекурсивные вызовы функций должны быть разрешены, как прямо, так и косвенно через какие-то цепи других функций.
и Stackoverflow происходит просто, потому что каждое состояние вызывающей области должно быть сохранено, поэтому, если бесконечные состояния области должны быть сохранены, ваш anywhen заканчивается память, так как у вас нет бесконечного пространства памяти. И это определенное поведение, потому что это происходит во время выполнения, и компилятору не нужно проверять в отношении стандарта, если рекурсия когда-либо будет нарушена.
причина стека ограничена, и всякий раз, когда вы вызываете функцию, она сохраняет вызываемого (путем нажатия базового указателя на стек и копирования текущего указателя стека в качестве нового значения базового указателя), поэтому потребляет стек будет переполняться бесконечным количеством вызовов. См. соглашение о вызовах и как стек реагирует здесь (http://www.csee.umbc.edu /
Я просто посмотрел на копию недавней проект стандартов C doc и ни одна из ссылок рекурсии не говорит о бесконечной рекурсии.
Если стандартный документ не требует от компилятора поддержки чего-либо и не запрещает его, то разработчики компилятора рассмотрят это неопределенное поведение.