recursion vs iteration

[Isaac To]

>>>>> "David" == David Eppstein <eppstein at ics.uci.edu> writes:

    David> That sounds dishonest.  But Fibonacci can be a good example of
    David> both memoization and dynamic programming, and I would expect the
    David> iterative linear version to be faster (by a constant factor) than
    David> the memoized recursive one (also linear due to the memoization).

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).

Regards,
Isaac.