Nelu wrote On 03/30/07 11:43,:
Well, yes and no. In your example (iteration vs. tail recursion) there
is a recursive call but the algorithm does not need to save the state
of its objects. I mean you can make an iteration into a recursive call
but a recursive call may need something extra to be transformed into
an iteration, i.e. tail recursion solution <-> iterative solution;
recursion ->iterative + state stack solution.
I guess my question was whether an iteration that needs to save the
state of it's objects at every step (or in a number of steps
proportional to the number of iteration steps) is a recursion or not.
Somehow I *knew* somebody would mention the magic mantra
of "tail recursion." As if it made a difference ...
All right, if tail recursion bothers you as being somehow
non-recursive, here's the recursion example I hate the most
(because nobody in his right mind would write this code):
long double fib(unsigned int n) {
return n > 1 ? fib(n-1) + fib(n-2) : n > 0;
}
.... which I think you'll agree is recursive, and not tail-
recursive. And here's an iterative expression of the exact
same idea, just done differently (and far more efficiently):
long double fib(unsigned int n) {
long double g = 0, h = 1;
while (n-- > 0) {
long double s = g + h;
g = h;
h = s;
}
return g;
}
Both implementations rely on forming a Fibonacci number as
the sum of the two that precede it; the crux of the method
is the same in both cases even though the implementations
are vastly different. So: Is the computation of Fibonacci
numbers recursive or iterative? My claim is that you can't
assign either label to the algorithm and have the claim
stand beyond debate. It make sense to label implementations
as recursive or iterative, but one is on shaky ground when
saying that a non-recursive implementation is "recursion
in disguise." It can be a false dichotomy.
(There is, of course, a way to compute Fibonacci numbers
without recursion and without iteration, if you grant yourself
the ability to compute powers. Difficult to do accurately
for large n, though.)
(The theory of automata uses "recursively computable"
to cover some of the things we're discussing here, but it's
really not the same notion. It covers a lot of things that
programmers wouldn't think of as recursive: `++i', for
example, is a recursively computable function.)
