рекурсия с использованием только области кучи

Question

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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