Почему глубина рекурсии недетерминирована (С++)?

Повторные запуски следующей программы C++ дают другое максимальное количество вызовов рекурсии (варьируется примерно на 100 вызовов функций) перед ошибкой сегментации.

#include <iostream>

void recursion(int i)
{
    std::cout << "iteration: " << ++i  << std::endl;
    recursion(i);
}

int main()
{
    recursion(0);
};

Я скомпилировал файл main.cpp с

g++ -O0 main.cpp -o main

Здесь и здесь та же проблема, что и выше, обсуждается для java. В обоих случаях ответы основаны на концепциях, связанных с java, JIT, сборке мусора, оптимизаторе HotSpot и т. д.

Почему максимальное количество рекурсий различается для C++?

Неопределенное поведение не определено. Нет ничего необычного в том, что разные прогоны дают разные результаты. Иного вам никто не обещал.

n. m. 13.12.2020 00:13

Я не знал, что бесконечные рекурсии - это неопределенное поведение в C++, которое объясняет аспект вопроса C++. Но есть некоторые различия в количестве операций, которые ОС «разрешает» перед завершением / уничтожением процесса - по крайней мере, когда стек заполнен?

dgruending 13.12.2020 00:20

Это может быть связано с ASLR, попробуйте отключить его и посмотреть, что произойдет.

n. m. 13.12.2020 08:57

Отключение ASLR приводит к постоянному числу рекурсий. Это отвечает на вопрос об ОС. Спасибо! Я задокументировал то, что я сделал ниже.

dgruending 13.12.2020 13:24
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
4
141
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

Ваша рекурсия никогда не заканчивается логически. Он завершается только тогда, когда ваша программа падает из-за нехватки места в стеке.

Определенный объем пространства стека используется для каждого рекурсивного вызова, но в C++ точно не определено, сколько пространства стека доступно и сколько используется для каждого рекурсивного вызова.

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

Итог: вы закодировали ошибку, и вы столкнулись с неопределенным поведением в вашем компиляторе и платформе. Если вы хотите точно определить, сколько места в стеке занимает ваша программа в текущем потоке, ваша платформа будет иметь API-интерфейсы, которые вы можете вызывать для получения этого значения.

но я компилирую его один раз. доступное пространство стека также всегда одинаково. разве выполнение не должно быть независимым от настроек оптимизации и компоновщика для повторного запуска одного и того же двоичного файла? может быть, это не столько вопрос C++, сколько вопрос о том, как операционная система завершает работу программы?

dgruending 12.12.2020 23:32

@dgruending • Поддерживает ли ваша платформа ASLR?

Eljay 12.12.2020 23:38

@Eljay Eljay Я использую Ubuntu 20.04, поэтому я предполагаю, что ответ на ваш вопрос «да».

dgruending 12.12.2020 23:39

«Он завершается только тогда, когда ваша программа дает сбой из-за нехватки места в стеке». Также может достигать UB с переполнением int (и это не только теоретическое, здесь можно легко оптимизировать хвостовую рекурсию).

Jarod42 12.12.2020 23:42
Ответ принят как подходящий

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

То, что находится в этой памяти, может зависеть от того, какие выделения памяти произошли, сколько непрерывной памяти передала вам ОС, когда вы запросили что-то, ASLR или что-то еще.

Неопределенное поведение в C++ непредсказуемо.

Я не знал, что бесконечные циклы являются неопределенным поведением в C++. Связанные N1528

dgruending 13.12.2020 00:02

@dgru это не бесконечный цикл. Это неограниченная рекурсия. Реализации C++ могут накладывать ограничения на рекурсию, после чего поведение становится неопределенным (т. е. разрыв стека).

Yakk - Adam Nevraumont 13.12.2020 00:04

Каким будет процесс, который приведет к «выбрасыванию случайного бита вашей памяти»? Разве ОС не должна это проверять?

dgruending 13.12.2020 00:05

@dgruending Пространство памяти процессов. Многие ОС (попытки) защитить систему от процесса, но редко защищают процесс от самого себя. Сбой процесса — пример того, как ОС защищает систему от процесса. Процесс, записывающий свою собственную кучу и приводящий к резкому сбою операций создания/удаления, является примером процесса, наносящего ущерб самому себе. То, как работает эта защита, зависит от системы; размещает ли он стек с огромным набором страниц защиты памяти, или стек переполняется прямо в кучу?

Yakk - Adam Nevraumont 13.12.2020 05:22

Помимо аспекта C++: после комментариев Eljay и n.'pronouns'.m я отказался от ASLR. Этот пост описывает, как это сделать. Короче говоря, ASLR можно отключить через

echo 0 | sudo tee /proc/sys/kernel/randomize_va_space

и включено через

echo 2 | sudo tee /proc/sys/kernel/randomize_va_space

После отключения ASLR количество рекурсий до ошибки сегментации системы остается постоянным для повторного выполнения описанной программы.

Другие вопросы по теме