рекурсия, использующая только кучную область

Question

Есть примеры рекурсии, использующей только область кучи?

Answer 1

В C функция call-based recursion всегда использует стек почти по определению.

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

Некоторые проблемы могут использовать tail recursion, что неоднократно перезаписывает одну и ту же область стека.

Answer 2

Вы можете сделать что-то сумасшедшее, как malloc в новой области, отключить прерывания и почти все остальное (что невозможно во многих системах) и установить указатель стека на эту область malloc. Вы по-прежнему играете со стеком, но местоположение этого стека теперь находится в куче. Не очень хорошая идея, но она может работать на некоторых системах с встроенным типом, где у вас есть этот уровень контроля.

Answer 3

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

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

Answer 4

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

(по крайней мере, не в C. Функциональные языки оптимизированы для повторного использования пространства стека, а не выделять указатели для возврата вызовов)

Answer 5

Да, можно реализовать рекурсию, используя только кучу, а в некоторых случаев это очень желательно. Например, см. Stackless Python. Одним из главных преимуществ этого является то, что весь поток может стать сериализуемым, и вы можете буквально отправить поток с одного узла на другой (даже с другой архитектурой & операционной системы!).