Бесконечная рекурсия без переполнения — возможно ли это?

Причина переполнения стека заключается в том, что пространство стека заканчивается, но что, если функции не имеют параметров, поэтому данные не нужно помещать в стек? При этом остается нажимать адрес «возврата», но в случае намеренной бесконечной рекурсии в этом нет необходимости.

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

Просто для уточнения, я имею в виду функцию, которая принимает один параметр и ничего не возвращает, поэтому технически fastcall будет достаточно, но она по-прежнему сохраняет адрес для возврата, что в конечном итоге приведет к переполнению. Можно ли это как-то предотвратить?

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


person Community    schedule 15.03.2014    source источник
comment
Насколько мне известно, не в С++. Вам нужна Хвостовая рекурсия, которая C++/C в настоящее время не поддерживаются (по крайней мере, как часть стандартов)   -  person Mgetz    schedule 15.03.2014
comment
Я не думаю, что существует соглашение о вызовах, которое ничего не помещает в стек. документы MSDN по соглашению о вызовах показывают множество различных соглашений о вызовах, но все в конечном итоге используют стек (некоторые сначала используют регистры).   -  person cf stands with Monica    schedule 15.03.2014
comment
Чтобы прояснить комментарий @Mgetz, ни стандарт C, ни стандарт C++ не требуют поддержки хвостовых вызовов, но оба они позволяют это, и текущие компиляторы на это способны.   -  person    schedule 15.03.2014
comment
который принимает один параметр, пожалуйста, где он должен храниться, если не в стеке?   -  person alk    schedule 15.03.2014
comment
@alk — в зарезервированном для этой цели регистре, который повторно используется каждой следующей функцией.   -  person    schedule 15.03.2014
comment
@alk, его можно хранить в стеке, смысл хвостовой рекурсии в том, что использование памяти остается постоянным, независимо от того, насколько глубока рекурсия.   -  person jbr    schedule 15.03.2014
comment
@jbr: Вы хотите сказать, что последние компиляторы достаточно умны, чтобы обнаружить, что текущий кадр стека больше не используется при выполнении хвостового вызова, и просто повторно использовать один и тот же кадр стека для каждого рекурсивного вызова?   -  person alk    schedule 15.03.2014
comment
@alk Это был бы один из способов реализовать это, но, скорее всего, компилятор просто превращает тело функции в цикл без рекурсивного вызова. Реализация хвостовой рекурсии не очень сложна, трудно обнаружить случаи, когда она применима.   -  person jbr    schedule 15.03.2014


Ответы (1)


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

Некоторые компиляторы C++ могут обнаруживать некоторые примитивные рекурсивные функции и переводить их в циклическую конструкцию вместо вызовов функций. Но это работает только до тех пор, пока компилятор может распознать, что происходит. Так что ответ, возможно. По сути, если программист делает что-то крайне неэффективное, то компилятор может помочь, а может и не помочь. Так что обычный процесс «код, профиль, оптимизация, повторение» продолжается.

person jbr    schedule 15.03.2014
comment
1+, Только что проверил, и вроде работает. :-) - person alk; 15.03.2014
comment
+1 за упоминание оптимизации хвостовых вызовов, поскольку это ответ и основная вещь, которую каждый язык функционального программирования имеет в учебниках. - person xmojmr; 24.04.2014