recursion vs iteration

[David Eppstein]

In article <7ihe1cn6of.fsf at enark.csis.hku.hk>,
 Isaac To <kkto at csis.hku.hk> wrote:

> Fibonacci can be computed in logarithmic time with repeated squaring of an
> appropriate 2x2 matrix.  And this, as Terry pointed out, can be done by
> either recursion or iteration.  Actually the phrase "can be done by either
> recursion or iteration" can be omitted, since every iteration can be turned
> into a tail recursion without losing efficiency (given the appropriate
> compiler optimization), and every recursion can be turned into an iteration
> using a stack; and the primary difference is how they looks (and people
> disagree even on whether a tail recursion is easier or harder to read than
> an iteration).

Perhaps, for Fibonacci, they are almost the same.  For the recursive vs 
iterative versions of 0-1 knapsack which I posted earlier in this 
thread, the same values are computed in the same places by the same 
formula, it's not tail-recursive because there are two subproblem values 
used in each instance of the formula (anyway we're in a Python group and 
Python doesn't optimize out tail recursions), and the recursive version 
computes them in a different order than the iterative one and doesn't 
compute as many of them.

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science