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 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 <= 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 <= 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 <= 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]


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)

StackExchange Code Review Q#59342, answer score: 2