Are there any cases when I would want to use an explicit stack over recursion?

Question

Are there any cases when I would want to use an explicit stack data-structure in my algorithms, as opposed to doing recursion (which uses the call stack)?

Is there any benefit to doing it one way over the other? I would think using the explicit data-structure would be more performant because it doesn't require the method calls but then again that is micro-optimization land.

Answer 1

Call stack is more limited depending on your runtime than a structure in memory. Many times I was forced to make a recursion into stack data structure because of StackOverflowExceptions in .NET.

Answer 2

Recursion call stack is usually limited while explicit stack is unlimited for most practical uses. So if you are expecting to have very deep recursion level (it varies depending your platform), its better to redesign your algorithm for explicit stack. E.g. many algorithms over graphs or trees come in two forms: with recursion and with explicit stack for this very reason.

Answer 3

One case I can think of where you could argue in favor of an explicit stack:

You might be on a system where entering and/or exiting stack frames is expensive, and your recursion depth is very deep. Imagine a depth-first in a tree.

In such a setup, if you found the requested tree node 100 levels deep, you need to destroy 100 stack frames one by one if you're using recursion.

Using an explicit stack, you can just return from your function, and the complete stack will be released at once.

Answer 4

Using an explicit structure allows you to trade more simple code for more performance.

Using the 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 save in a couple of places:

• You don't need to pay for a function/method invocation (very useful for scripted/dynamic languages)
• You can save only those bits you need. If you use recursion, you must save the whole stack frame (with all local variables, the return address, all parameters).
• You can look around in your explicit stack (i.e. you can see what happened "two recursions before") which is a bit hard with a normal stack
• While the real stack can be limited for many reasons, you can allocate as much memory as you need for your implicit stack (or even use a database).

Answer 5

An explicit stack may also give you a better referential locality, which in turn improves cache efficiency. Storing multiple copies of your functions address on the stack in between your real data is cache polution.