Lorenzo Villari said:
Ok but there's a way to "mechanically" eliminate recursion?
I mean something valid for all recursive functions,
expecially the ones with tail recursion...
For example... I've got a recursive function and I want to eliminate its
recursion but the code is too much and I can't post it...
automation (a formula) would be a solution...
(of course being a master of the language would be better...)
There's a mini-tutorial on eliminating recursion in my book on
binary search trees. You can read it at
http://adtinfo.org/libavl.html/Iterative-Traversal-of-a-BST.html
It's not always the right thing to do to eliminate recursion.
However, there are several reasons to avoid recursion in C:
* Recursion is more difficult to understand in some
algorithms (but see below). An algorithm that can
naturally be expressed iteratively may not be as easy
to understand if expressed recursively.
* 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.
(Now, if C had built-in support for co-routines, we
could do this recursively anyhow. Most procedural
languages do not support co-routines; I hear that Icon
is an exception. It's really too bad, but I don't see
this changing soon.)
* 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.
* Avoiding recursive calls often avoids other kinds of
overhead, such as the system's unavoidable function
call overhead. On some systems this can be
significant, so a transformation from recursion to
iteration can improve both speed and space
requirements.
There are reasons to avoid iteration, too:
* Iteration is more difficult to understand in some
algorithms (but see above). An algorithm that can
naturally be expressed recursively may not be as easy
to understand if expressed iteratively. It can also be
difficult to convert a recursive algorithm into an
iterative algorithm, and verifying that the algorithms
are equivalent can also be difficult.
* Recursion allows you to allocate additional automatic
objects at each function call. The iterative
alternative is to repeatedly dynamically allocate or
resize memory blocks. On many platforms automatic
allocation is much faster, to the point that its speed
bonus outweighs the speed penalty and storage cost of
recursive calls. (But some platforms don't support
allocation of large amounts of automatic data, as
mentioned above; it's a trade-off.)
