Не могу понять, почему эта простая рекурсия работает и падает
Я задавал несколько каверзных вопросов о C++ и запускал аналогичный код, а затем модифицировал его, чтобы посмотреть, что произойдет.
Я не понимаю, почему сначала эта рекурсия работает (она печатает значения от 2 до 4764), а потом вдруг выдает исключение.
Я также не понимаю, почему я могу сказать «возврат» в функции void и на самом деле вернуть что-то, кроме «возврата»;
Кто-нибудь может объяснить эти две проблемы?
#include<iostream>
using namespace std;
void function(int& a){
a++;
cout << a << endl;
return function(a);
}
void main() {
int b = 2;
function(b);
system("pause>0");
}
С++ не использует хвостовую рекурсию, поэтому каждый вызов представляет собой совершенно новый кадр стека, помещаемый в стек, в конечном итоге который выйдет из строя после того, как стек вырастет до некоторой точки, где произойдет что-то плохое, зависящее от реализации.
Каждый раз, когда функция вызывается рекурсивно, она выделяет больше места в стеке вызовов, пока, в конце концов, вы не исчерпаете его, и приложение не выйдет из строя, что известно как переполнение стека.
system("pause>0"); выглядит ущербно
Вы не добавили условие остановки рекурсии. Вот почему стек будет переполняться.
По второму вопросу: en.cppreference.com/w/cpp/language/returnIn a function returning void, the return statement with expression can be used, if the expression type is void.
"Я также не понимаю, почему я могу сказать «возврат» в функции void и на самом деле вернуть что-то, кроме «возврата»;" См. этот вопрос: Могу ли я вернуться в недействительной функции?
Какое исключение выдает?
Если вы скомпилируете его с -O2 (или выше) на любом современном компиляторе, он, вероятно, выполнит оптимизацию хвостового вызова и превратит ваш рекурсивный вызов в цикл. Затем он должен работать вечно без переполнения стека.
@GradyPlayer решает компилятор, выполнять ли оптимизацию хвостовой рекурсии. Стандарт этого не запрещает.
Даже без переполнения стека программа вызывает неопределенное поведение из-за переполнения целого числа со знаком.
Ответы 2
В комментариях правильно указано, что ваша бесконечная рекурсия вызывает переполнение стека - каждый новый вызов одной и той же функции занимает больше оперативной памяти, пока вы не израсходуете объем, выделенный для программы (размер стека С++ по умолчанию сильно зависит от среды, и где-то от 10 кБ в старых системах до 10+ МБ на верхнем конце). В комментариях правильно указано, что ваша бесконечная рекурсия вызывает переполнение стека - объем пространства, выделенный для этой цели (размер стека С++ по умолчанию сильно зависит от среды, и где-то от 10 кБ на старых системах до 10+ МБ на верхнем конце). В то время как сама функция использует очень мало памяти, кадры стека (которые отслеживают, какая функция вызвала какую другую текущую функцию с какими параметрами) могут занимать довольно много.
Хотя это полезно для определенных структур данных, рекурсивные программы не должны углубляться в несколько тысяч слоев и обычно добавляют условие остановки (в данном случае даже проверку того, является ли a > some_limit), чтобы определить точку, в которой они ушли вглубь и нужно прекратить добавлять больше. вещи в стек (обычный return;).
В этом случае точно такой же результат можно получить с помощью простого цикла for, поэтому я думаю, что эти каверзные вопросы чисто экспериментальные.
На платформах x86-64, таких как ваш ноутбук или настольный компьютер, функции вызываются одним из двух способов:
- с
callинструкцией по сборке - с
jmpинструкцией по сборке
Какая разница? После ассемблерной инструкции call идут дополнительные инструкции: при вызове функции код вернется туда, откуда был вызван. Чтобы отслеживать, где он находится, функция использует память в стеке. Если рекурсивная функция вызывает себя с помощью call, то по мере рекурсии она будет использовать все больше и больше стека, что в конечном итоге приведет к переполнению стека.
С другой стороны, инструкция jmp просто говорит процессору перейти к разделу кода, где хранится другая функция. Если функция вызывает сама себя, то ЦП просто jmp вернется к началу функции и запустит ее заново с обновленными параметрами. Это называется оптимизация хвостового вызова, и во многих распространенных случаях он полностью предотвращает переполнение стека, поскольку стек не растет.
Если вы скомпилируете свой код на более высоком уровне оптимизации (скажем, -O2 в GCC), то компилятор будет использовать оптимизацию хвостового вызова, и в вашем коде не будет переполнения стека.
Переполнение стека;