You can implement the matrix exponentiation via repeated squaring recursively even in a language like Python that doesn't do tail call optimization, and it will still be fast: your recursion only goes to a logarithmic depth.
In any case, recursion vs iteration is an implementation detail. Especially if your language supports tail call optimization. Have a look at this example:
f(0) := (0, 1)
f(n) := let (a, b) = f(n-1) in (b, a + b)
f is recursive function over tuples of integers. And f is basically equivalent to the typically iterative algorithm for computing Fibonacci numbers.
If you can do arbitrary precision arithmetic (including powers and square roots) in unit time, this one is fastest.
In practice, this algorithm is not the fastest, because handling arbitrary precision floating point numbers is a pain.
Have a look at the matrix exponentiation algorithm for Fibonacci numbers in http://pages.cs.wisc.edu/~mhock/SSL/fibcalc.pdf
You can implement the matrix exponentiation via repeated squaring recursively even in a language like Python that doesn't do tail call optimization, and it will still be fast: your recursion only goes to a logarithmic depth.
In any case, recursion vs iteration is an implementation detail. Especially if your language supports tail call optimization. Have a look at this example:
f is recursive function over tuples of integers. And f is basically equivalent to the typically iterative algorithm for computing Fibonacci numbers.