recursion using only heap area

Question

Are there examples of recursion using only heap area?

Answer 1

In C, function call-based recursion always uses the stack, almost by definition.

If you are willing to convert your recursion to iteration, then it is possible to use only heap space, but that isn't really recursion. You would do so by implementing a stack in the heap.

Certain problems can use tail recursion, which repeatedly overwrites the same area of the stack.

Answer 2

You could do something crazy like malloc a new area, turn off interrupts and just about everything else (not possible on many systems) and set your stack pointer to that malloc area. You are technically still playing with a stack, but that stack location is now on the heap. Not a good idea to do, but it can work on some embedded type systems where you have this level of control.

Answer 3

In many implementations, arguments to a function call are stored on the stack. Information such as the address to return to may also be stored on the stack. Thus having a recursive function without using the stack may not be feasible.

Check your compiler documentation to see if a function can be called without using any room on the stack. If so, you are on your way.

Answer 4

In order for a function to be recursive, it must call itself at least once. When it calls itself, it places a pointer to itself on the stack for the recursive call's return. The stack, of course, is not the heap, and therefore a recursive function which uses only the heap is not possible.

(At least, not in C. Functional languages are optimized to re-use stack space and not allocate pointers for return calls)

Answer 5

Yes, it is possible to implement recursion using only the heap, and in some cases it's very desirable. For instance, see Stackless Python. One of the prime benefits of this is that an entire thread can become serializable and you can literally ship a thread from one host to another (even of a different architecture & operating system!).