Any examples of code for this approach? From what I guess, you are implementing some kind of assembly like approach with explicit saving of stack frame, but I am having a hard time imagining it as being easier.
struct BinTree {
long value;
BinTree *left;
BinTree *right;
};
long long RecursiveDFSSum(BinTree *node) {
if (NULL == node) {
return 0;
}
return (long long)value + RecursiveDFSSum(node->left) + RecursiveDFSSum(node->right);
}
long long IterativeDFSSum(BinTree *tree) {
std::vector<BinTree *> custom_stack;
custom_stack.push_back(tree);
long long value = 0;
while (!custom_stack.empty()) {
BinTree *node = *custom_stack.rbegin();
custom_stack.pop_back();
if (NULL != node) {
value += node->value;
custom_stack.push_back(node->left);
custom_stack.push_back(node->right);
}
}
return value;
}
If you were coding a DP problem, then custom_stack might have a fixed size you can pre-allocate, and it might also be 2 or 3-dimensional.
For some image-based recursion, your backtracking doesn’t even need to store real pointers in the stack frame. For example when I’ve written a flood fill, I can store the return pointer as a one pixel offset in as little as 2 or 3 bits, depending on whether I include diagonal pixels (4-surround vs 8-surround).
Python memory management is automatic though, discussing stack vs heap doesn't make sense in the context of Python,well for CPython at least. I'm not sure about other Python implementations.
I'm not sure I know what you mean about stack vs heap not making sense because of Python's memory manager. Will you elaborate?
The primary issue is that the default stack limit in Python is too small for some applications of recursion, which the comment before mine illustrates. This is true not just in Python, but any language, since the stack size is generally a function of the process or OS, not a limit of the language. Heap allocated stacks are a reasonable thing to do in any language.
You're right you can solve that in Python by using a list. Python's memory management doesn't really affect one's ability to do so, right?
A secondary issue is that native recursion sometimes uses more memory than a manually heap-allocated "stack". If I make my own stack, I have complete control and complete understand of what's in memory and how much I use. With the native stack, it can be very opaque, and it's easy to chew up the already-too-small stack very quickly by accidentally having a large stack frame.
In Python everything is an object. Python gives you a reference to that object when you create it. There is no way to tell Python(CPython anyway) in which memory space you would it to create that object.
Ah right, that's because all objects are heap-allocated.
You choose heap by using an object for the stack, and rewriting your recursion to use (superficially) iterative code.
You can choose stack allocation instead by using regular recursion: native function calls with local variables.
What you bring up is an interesting issue that can make recursion harder to understand in Python. Having local objects in the stack frame can cause both stack and heap allocation - pointers for the objects on the stack, and the object contents on the heap. Or, you might have global objects that aren't local to the recursive function call or the stack, in which case it's important to understand you're sharing data across function calls.
Generally speaking, you probably don't want individual heap allocations in a recursive function, so it's best not to have local objects. At least performance-wise.
You can choose stack allocation instead by using regular recursion: native function calls with local variables."
I'm not following you.
I believe these would both result in the same thing in Python. Python gives you a reference to an object. That object is stored in a private heap "somewhere." That reference to the object that Python gave you is stored on the stack. The object that it points to lives in the heap. This should be the same for both of your examples. I'm not sure what you mean by "native function calls." I am not familiar this this term.
What we’re talking about is the difference between calling a function recursively (a function that calls itself) and instead simulating recursion using a data structure posing as a stack and an iterative function that doesn’t call itself but instead pushes and pops into your fake stack data structure.
You can either use the system’s built-in stack (by calling functions), or create your own fake stack (by pushing/popping, writing/reading an array, etc.).
Using sys.setrecursionlimit() as mentioned at the very top of this thread only affects the system stack. By “native function calls”, I just mean regular function calls. These are subject to the system’s stack limit.
When you allocate an object and use it as a fake stack to replace the system stack, the size of the object is not subject to the system’s stack limit (which is small — on PCs often a megabyte or two), it’s only limited by the available size of the heap (which is normally large relative to the system stack limit, often gigabytes).
When you make your own fake stack and use an iterative function, you can achieve a much greater recursion depth because your fake stack size is on the heap and not actually in the system stack.
Does that make more sense? The two cases are very different in Python, and using a fake heap-allocated stack, i.e. a Python object, is super useful.