Recursive vs. non-recursive implementations of Fibonacci sequence

Question

I have 2 functions to get the n-th fibonacci number. The 1st one uses recursive calls to calculate the power(M, n), while the 2nd function uses iterative approach for power(M, n). Theoretically (at least what I think), they should have the same speed O(log n), but why when I run both, the 2nd one is much slower than the 1st one?

def fib_1(n):
    from numpy import matrix
    def power(F, n):
        if n == 0 or n == 1: return matrix('1 1; 1 0', object)

        F = power(F, n >> 1) # n // 2
        F = F * F
        if n % 2 == 0:
            return F
        if n % 2 != 0:
            return F * matrix('1 1; 1 0', object)

    F = matrix('1 1; 1 0', object)
    F = power(F, abs(n)-1)
    return F[0,0] if n > 0 else int((-1)**(n+1)) * F[0,0]

def fib_2(n):
    from numpy import matrix
    def power(F, n):
        M = matrix('1 1; 1 0', object)
        while n > 0:
            if n & 1 == 1:
                M = F * M
            n = n >> 1 # n = n // 2
            F = F * F
        return M

    F = matrix('1 1; 1 0', object)
    F = power(F, abs(n)-2)
    return F[0,0] if n > 0 else int((-1)**(n+1)) * F[0,0]

Answer 1

Before we got any further, a word of warning. The complexity is only valid in a particular computational model.

The complexity of these algorithms is \$O(\log n)\$ only if the addition takes constant time. For large \$n\$ it is not the case.

Fibonacci numbers grow exponentially with n. It means that the number of bits grows linearly. Now we are in the Turing machine realm. The last addition itself takes \$O(n)\$, which is way more than \$\log n\$.

The overall complexity should be \$O(n\log{n})\$ in both cases. Why the two exhibit different performance?

The likely reason is that there is a subtle difference between them. fib_1 maintains just one matrix, F. fib_2 maintains two of them, F, M, and must do roughly twice as many reallocations as fib_1 does. The matrices contain huge numbers, and I expect that the memory management time dominates. Yet another factor the computational model shall now consider.

Answer 2

Before some more detailed performance analysis, it's important to note some low-hanging fruit in terms of code quality.

Global imports

Unless you have a really good reason, from numpy import matrix should be at the top of the file in global scope.

Deprecated library classes

matrix is deprecated. Use ndarray instead.

Do not reconstruct constants

matrix('1 1; 1 0', object) should not be parsed and reconstructed every time. Save it outside of function scope. If you need it to be modified later, modify a copy. Copying will be cheaper than parsing.

Redundant branches

In this:

    if n % 2 == 0:
        return F
    if n % 2 != 0:
        return F * matrix('1 1; 1 0', object)

The second if is not necessary because its condition is guaranteed to be True.

Expression simplification

int((-1)**(n+1))

It's probable that n is already an integer based on how your function is set up (though documentation and/or type hints would help to clarify this). The fact that a float is produced when the exponent is negative is probably due to Python assuming that it effectively needs to do a division, which is reasonable. All things considered, rather than doing the exponentiation - which is common in pure math, because of simplicity of analysis - you should consider doing the "piece-wise" thing instead. Rather than

return F[0,0] if n > 0 else int((-1)**(n+1)) * F[0,0]

consider

y = F[0,0]
if n <= 0 and n%2 == 0:
    y = -y
return y