I'd say: if you're using a stack to explicitly mimic the implicit
stack used by recursion, then you're just mimicing recursion.
Mimicking recursion still has real advantages over real recursion
in some contexts. Earlier I posted my list of points for and
against recursion in C. The following of those points still
apply to iteration that mimics recursion. None of these say
"recursion is (faster/slower) than iteration"; they are all
related to convenience and practicality (well, the third point
has a little to do with efficiency but a lot more to do with
convenience):
* There is no portable way to tell how deep recursion can
go without causing trouble (how much `stack space' the
machine has), and there is no way to recover from
too-deep recursion (a `stack overflow').
* In C you can't do some nice things recursively. For
instance, if I'm traversing a binary tree, I probably
want to do it using a for loop:
tree t;
item *i;
for (i = first (t); i != NULL; i = next (i)) {
...do something with i...
}
But you can't write the traversal recursively if you
want to do this. Factoring the traversal into
iteration or forcing the use of a callback function are
the only two choices. The former is the lesser of the
two evils, since you only have to do it once and then
can use many times in traversals.
* Suppose that you need to pass some data to the
recursive process. You might want to keep a count of
the number of nodes visited, or a set of parameters
that determine what to do at each node, or anything
else. In order to do this, you have to pass some data
to every recursive call. This is a waste of time and
space, unless your compiler is much smarter than mine.
Alternatively, you can use global variables, but that's
hardly a preferable solution.
Now, if you were to use an iterative solution instead,
you could just have a single set of local variables,
and there is no need to pass anything recursively.
This saves the time and memory that would be used for
passing these things in the recursive calls.
* Aborting a recursive process in midstream is a pain.
Suppose that you're using a function to enumerate all
the items in a binary search tree, and you discover
halfway through that you don't need to look at any more
items. Alternatively, consider the problem of aborting
after a syntax error while parsing an expression via
recursive descent. Trying to abort the process
involves the cooperation of the currently executing
instance with all of the instances in which it is
nested. This is slow and sometimes nasty. Use of
setjmp() and longjmp() is an alternative, but, like
goto, these constructs are best avoided when practical.
Even worse, suppose, in the context of the binary
search tree example, that halfway through you discover
that you need to change directions, move *backward*. I
don't even want to think about how to do that
recursively. It's simply impractical.
In short, I don't think that mimicking recursion should be
derided just because it's imitation; rather, it should be done
when it's the right thing to do, and avoided when it's done for
gratuitous reasons.
