Menu
I was watching a video about CUDA and the Barnes-Hut algorithm where it was stated that it is necessary to place a depth limit on the tree for the GPU, and then the idea popped into my head about possibly doing recursion in the heap.
Basically, I am wondering just that: Is it possible to allocate memory from the heap and use that as a temporary "stack" in which to place function calls for the recursive function in question to somewhat delay a stack overflow?
If so, how could it be implemented, would we allocate space for a pointer to the function? I assume it would involve storing function address in the heap however I'm not too sure.
[edit] I just wanted to add that this is purely a theoretical question, and i would imagine that doing this would cause the program to slow down once using the heap.
[edit] As per request, the compiler I am using is GCC 4.8.4 on Ubuntu 14.04 (64-bit)
801
Memory Allocation in Recursion. When a function is called, its memory is allocated on a stack. Stacks in computing architectures are the regions of memory where data is added or removed in a last-in-first-out (LIFO) process. Each program has a reserved region of memory referred to as its stack.
When a function is called recursively, a stack frame is allocated for each of the recursive call of the function. E.g. if void f() is recursively called three times. C++ does NOT guarantee that the automatically managed memory will be allocated on a stack like structure.
4) Both heap and stack are essential to implement recursion. Heap is not needed for function calls. It is generally used for dynamic memory allocation by user (or programmer).
Explanation: Recursion uses more memory compared to iteration because every time the recursive function is called, the function call is stored in stack.
Sure. This is called continuation-passing style. The standard library supports it with setjmp() and longjmp(), and stores the information needed to restore control to an earlier point in a structure called jmp_buf. (There are several restrictions on where you can restore from.) You would store them in a stack, which is just a LIFO queue.
A more general approach is to run the program as a state machine and store the information needed to backtrack the program state, called a continuation, in a data structure called a trampoline. A common reason to want to do this is to get the equivalent of tail-recursion in an implementation that doesn’t optimize it and might chew up lots of stack space. One real-world application where someone I know is currently writing a trampoline is a GLL parser where the grammar is represented as a directed graph, the result of the parse is a shared packed parse forest, and the parser often needs to backtrack to try a different rule.
Continuation-passing and trampolines seem to be regarded as fancy style because they come from the world of functional programming, while longjmp() is regarded as an ugly low-level hack and even the Linux man page says not to use it.
143
You can simulate this by implementing your own heap-based stack as an array of structures, with each structure representing a stack frame that holds the equivalent of parameters and local variables. Instead of a function calling itself recursively, the function loops and each "call" explicitly pushes a new frame onto the stack.
I did exactly this years ago while attempting to solve a simple board game. The program was originally recursive, and it took forever to run. I changed it to the above structure, and this made it simple to make the app interruptible/restartable. When interrupted the app dumped its "stack" to a state file. When restarted, the app loaded the state file and continued where it left off.
This does required some care if the stack frame structure contains embedded pointers, but it's not insurmountable.
22
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
