Also, you could have shown a method which is O(log n), namely [[F(n+1) F(n)], [F(n) F(n-1)]] equals [[1, 1] [1, 0]] raised to the power of n.
Indeed you can compute Fibonacci numbers (and other linear recurrences) with matrix exponentiation, or with a closed-form equation like the Binet Formula - but I limited the scope of this article to tail recursion.
Binet Formula: http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...
And tail recursively, and – going full circle – you can convert that tail recursion into iteration (see [1] for example, using techniques described in [2]).
[1] Iterative fast-power implementation in Python https://github.com/tmoertel/practice/blob/master/libraries/t...
[2] Recursion to Iteration, Part 1: The Simple Method, secret features, and accumulators http://blog.moertel.com/posts/2013-05-11-recursive-to-iterat...