Are there any cases where I would like to use an explicit stack over recursion?
Are there cases where I would like to use an explicit stack data structure in my algorithms, as opposed to performing recursion (which uses the call stack)?
Is there any benefit for this? I would have thought that using an explicit data structure would be more efficient because it doesn't require method calls and then again, which is a micro-optimized object.
source to share
In one case, I can think of where you could argue in favor of an explicit stack:
You may be on a system where entering and / or exiting stack frames is expensive and the recursion depth is very deep. Imagine the depth in a tree.
In such a setup, if you find the right node tree of 100 levels, you need to destroy 100 stack frames one by one if you are using recursion.
Using an explicit stack, you can simply return from your function and the full stack will be released immediately.
source to share
Using an explicit structure allows you to use simpler code for better performance.
Using a stack for recursion often allows for very elegant and short code.
Using an explicit stack usually makes the code (much) more complex, but you can store it in several places:
- You don't have to pay for a function / method call (very useful for scripting / dynamic languages)
- You can only store the bits that you need. If you are using recursion, you must keep the entire stack (with all local variables, return address, all parameters).
- You can look around in your explicit stack (for example you can see what happened "two recursions before") which is a little tricky with a normal stack
- While the real stack can be limited for many reasons, you can allocate as much memory as your implicit stack needs (or even use a database).
source to share
The recursion call stack is usually limited, and the explicit stack is unlimited for most practical uses. Therefore, if you expect to have a very deep level of recursion (it depends on your platform), it is better to redo your algorithm for an explicit stack. For example. many algorithms on graphs or trees come in two forms: recursive and explicit stack for this very reason.
source to share