Dynamically changing the recursion limit for a fibonnacci program python

Question

I am trying to write a recursive multinacci (basically fibonacci numbers except the rabbits produce k pairs instead of 1 pair with each breeding cycle) function and I want it to work with all n. Here is my code so far:

from functools import lru_cache
from sys import getrecursionlimit, setrecursionlimit

def fibnum(n, k=1):
    """Returns the nth fibonacci number of order k"""
    # check if recursionlimit needs increasing
    return _fibnum(n, k)

@lru_cache(maxsize=None)
def _fibnum(n, k):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return _fibnum(n-1, k) + k * _fibnum(n-2, k)

A few notes about the code: the first function is a wrapper around the second so as to the description text look right. The second function is memoized, which increases performance drastically.

I've noticed that when I try to find increasing values of fibnum in order (100, 400, 1000 etc.) I can get around the recursion limit since the memoization shortcuts the recursion. I want to be able to run my function for any number right off the bat. I've tried testing the bounds of the recursion limit for n and then setting the recursion limit to that, but the only one that seemed to work was n², but that seems too high of a limit.

Any suggestions?

Note: at a later point, I would like to add a lifespan to the formula (which is basically subtract out fibnum(n- life_span, k)). How would this affect the recursion depth needed?

You could try, catch the RuntimeError and double the recursion limit then (up to some larger max - eventually you'll have to give in!) — jonrsharpe
– jonrsharpe, Commented Aug 6, 2014 at 17:13
IMHO, for Python the idiomatic way to write fib is converting the algorithm from recursive to iterative. — Paulo Scardine
– Paulo Scardine, Commented Aug 6, 2014 at 17:20
Also: isn't lru_cache in functools (not itertools), and doesn't it preserve documentation (although admittedly not signature)? — jonrsharpe
– jonrsharpe, Commented Aug 6, 2014 at 17:20
Also the main point I was making is that I don't have to give in. If I run my code with ever increasing n (100, 200, 300... 10000), it can go on forever because of the memoization. I've tried it myself and it works, despite retaining the default recursion depth. I want to be able to do this automatically. — mleyfman
– mleyfman, Commented Aug 6, 2014 at 17:31

pjs · Accepted Answer · 2014-08-06 23:56:22Z

2

One way of sidestepping the stack limitations is to set up the Fibonacci recurrence in matrix form and use the matrix version of multiplication by successive halving and squaring. With this approach the stack growth is O(log n), so you can go to gigantic values of fib(n) with no worries. Here's an implementation:

def __matrix_fib__(n):
    if n == 1:
        return [0, 1]
    else:
        f = __matrix_fib__(n / 2)
        c = f[0] * f[0] + f[1] * f[1]
        d = f[1] * (f[1] + 2 * f[0])
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]


def fib(n):
    assert (n >= 0)
    if n == 0:
        return n
    else:
        return __matrix_fib__(n)[1]

ADDENDUM

This version adds the k parameter as requested...

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]


def fib(n, k=1):
    assert (n >= 0)
    if n == 0:
        return n
    else:
        return __matrix_fib__(n, k)[1]

I won't swear this is correct because I dashed it off between classes, but my tests produced the same answers as your version when given the same inputs.

edited Aug 6, 2014 at 23:56

answered Aug 6, 2014 at 17:55

pjs

20k4 gold badges30 silver badges64 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

mleyfman Over a year ago

How would I modify this to add the k factor that is in my original code?

IceArdor Over a year ago

__matrix_fib__(n, k)[1] = [Fib(n-1, k), Fib(n, k)][1] = Fib(n, k) nayuki.eigenstate.org/page/fast-fibonacci-algorithms nayuki.eigenstate.org/res/fast-fibonacci-algorithms/…

Kirk Strauser · Accepted Answer · 2014-08-06 19:53:33Z

1

Alternatively, you could use a class as a namespace to store the cache, then calculate results iteratively:

class Fib(object):
    cache = [1, 1]

    @classmethod
    def get(cls, n):
        if n < 1:
            return 0

        for i in range(len(cls.cache), n):
            cls.cache.append(cls.cache[-1] + cls.cache[-2])

        return cls.cache[n - 1]

Usage:

a = Fib()
print a.get(1000)

answered Aug 6, 2014 at 19:53

Kirk Strauser

31.1k5 gold badges53 silver badges69 bronze badges

2 Comments

IceArdor Over a year ago

Or more generally, calculate values from the bottom up rather than from the top down. This doesn't require a class, but it sure makes it convenient.

Kirk Strauser Over a year ago

Yeah, it could be done other ways but that's a handy way to hold state without resorting to global variables.

IceArdor · Accepted Answer · 2014-08-06 20:14:57Z

1

If you change fibnum to limit the call stack to 100 items by computing the first 100 fibnums, then the next 100 fibnums, then the next 100 fibnums, you can avoid a recursion limit.

This produces very little wasted work since you'll need to compute the first 100 fibnums to compute the last 100 fibnums anyways.

The number 100 is arbitrary, but should be less than sys.recursionlimit.

def fibnum(n, k=1):
    """Returns the nth fibonacci number of order k"""
    # build up cache of fib values early in the sequence
    for intermediate_n in range(100, n, 100):
        _fibnum(intermediate_n, k)
    return _fibnum(n, k)

answered Aug 6, 2014 at 20:14

IceArdor

2,05122 silver badges20 bronze badges

7 Comments

mleyfman Over a year ago

I tried it with 500 and it didn't seem to work, even when recursion limit is 1000. This does work with up to somewhere around 300-400, and it definitely fails at 400. It does work with 100 though. Also, I think that it would be good to store the limit as a global variable so that we don't do useless computations every time.

IceArdor Over a year ago

Hmm.. It works on my system for 500 and 1500. My recursion limit is 1000. Check your lru_cache implementation. I'm using Jython 2.5 and this memoized decorator (since functools.lru_cache was added in Python 3): wiki.python.org/moin/PythonDecoratorLibrary#Memoize

mleyfman Over a year ago

I'm using Python 3.4 with python's native functools.lru_cache implementation, if I understand correctly.

IceArdor Over a year ago

What is lru_cache.cache_info() after you get a RuntimeError: maximum recursion depth exceeded?

mleyfman Over a year ago

It says function object lru_cache has no attribute cache_info

|

Collectives™ on Stack Overflow

Dynamically changing the recursion limit for a fibonnacci program python

3 Answers 3

2 Comments

2 Comments

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

2 Comments

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related