Comparison of Fibonacci (Multinacci) Functions in Python3 After coming up with a formula on this Stack Overflow question, defeating recursion limits and finding a few new ways of calculating these numbers (as per this Stack Overflow question), I decided that it was time to write up the solutions and submit them for a proper review.

For those that are not familiar with Fibonacci and more generally, Multinacci numbers, here are the rules:


The numbers correspond to the number of pairs of rabbits at year n
Rabbits take 1 year to mature
Rabbits reproduce after they mature, to produce 1 (or k in the case of Multinacci) pairs of rabbits
There is 1 pair at year 1, and none at year 0




from functools import lru_cache

limit = 100

# Classic recursive
def fibnum1(n, k=1):
    """Returns the multinacci number of order k at generation n"""
    if n &lt;= 0:
        return 0
    if n == 1 or n == 2:
        return 1
    # build up the cache as needed to defeat recursion bounds
    global limit
    if n &gt; limit:
        for temp_n in range(limit, n, 100):
            _fibnum(temp_n, k)
        limit = n + 100
    return _fibnum(n, k)

# Recursive with matrix multiplication
def fibnum2(n, k=1):
    """Returns the multinacci number of order k at generation n"""
    if n &lt;= 0:
        return 0
    if n == 1 or n == 2:
        return 1
    return _matrix_fib(n, k)[1]

# Iterative
def fibnum3(n, k=1):
    """Returns the multinacci number of order k at generation n"""
    if n &lt;= 0:
        return 0
    fibnums = [0, 1, 1]
    for i in range(3, n+1):
        fibnums.append(fibnums[i-1] + k * fibnums[i-2])
    return fibnums[n]

# Helper for fibnum1, memoized of course
@lru_cache(maxsize=None)
def _fibnum(n, k=1):
    if n &lt;= 0:
        return 0
    if n == 1 or n == 2:
        return 1
    return _fibnum(n-1, k) + k * _fibnum(n-2, k)

# Helper for fibnum2, memoized of course
@lru_cache(maxsize=None)
def _matrix_fib(n, k):
    if n == 1:
        return [0, 1]
    else:
        f = _matrix_fib(n // 2, k)
        c = k * f[0] * f[0] + f[1] * f[1]
        d = f[1] * (f[1] + 2 * k * f[0])
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, k * c + d]


As you can see, there are three distinct functions here for calculating these numbers: fibnum1, fibnum2, and fibnum3. They are nearly functionally identical, as all 3 are super fast (memoization for the win!) and work for relatively big numbers quite well. fibnum2 will fail eventually (dumb recursion limit...), but it is at too large of a number to be practically reached. I would like a comparative review, along with any other comments on any aspect of the code.
Everything looks fine to me. Just some small suggestion:

Don't define limit as a global. You can make it an attribute of the function itself: fibnum1.limit

In the matrix version I would return a tuple instead of a list. Also I would define two variables for f[0] and f[1] as follows:

@lru_cache(maxsize=None)
def _matrix_fib(n, k):
    if n == 1:
        return (0, 1)
    else:
        f0, f1 = _matrix_fib(n // 2, k)
        c = k * f0 * f0 + f1 * f1
        d = f1 * (f1 + 2 * k * f0)
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, k * c + d)