Fibonacci Function Memoization in Python [duplicate]

Question

I'm working on a problem in codewars that wants you to memoize The Fibonacci sequence. My solution so far has been:

def fibonacci(n):  
    return fibonacci_helper(n, dict())

def fibonacci_helper(n, fib_nums):
    if n in [0, 1]:
        return fib_nums.setdefault(n, n)

    fib1 = fib_nums.setdefault(n - 1, fibonacci_helper(n - 1, fib_nums))
    fib2 = fib_nums.setdefault(n - 2, fibonacci_helper(n - 2, fib_nums))

    return fib_nums.setdefault(n, fib1 + fib2)

It works reasonably well for small values of n, but slows down significantly beyond the 30 mark, which made me wonder — is this solution even memoized? How would I get this type of solution working fast enough for large values of n?

The code looks fine. The only problem I seem to understand from this code is the setdefault function as it looks for the key first and then puts it in the dictionary if its not found. Not sure but I guess the execution might have slowed down because of that searching. — VeryBhatti
– VeryBhatti, Commented May 5, 2020 at 2:26

Samwise · Accepted Answer · 2020-05-05 02:36:52Z

6

Your function isn't memoized (at least not effectively) because you call fibonacci_helper regardless of whether you already have a memoized value. This is because setdefault doesn't do any magic that would prevent the arguments from being evaluated before they're passed into the function -- you make the recursive call before the dict has checked to see whether it contains the value.

The point of memoization is to be careful to avoid doing the computation (in this case a lengthy recursive call) in cases where you already know the answer.

The way to fix this implementation would be something like:

def fibonacci(n):  
    return fibonacci_helper(n, {0: 0, 1: 1})

def fibonacci_helper(n, fib_nums):
    if n not in fib_nums:
        fib1 = fibonacci_helper(n-1, fib_nums)
        fib2 = fibonacci_helper(n-2, fib_nums)
        fib_nums[n] = fib1 + fib2
    return fib_nums[n]

If you're allowed to not reinvent the wheel, you could also just use functools.lru_cache, which adds memoization to any function through the magic of decorators:

from functools import lru_cache

@lru_cache
def fibonacci(n):
    if n in {0, 1}:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

You'll find that this is very fast for even very high values:

>>> fibonacci(300)
222232244629420445529739893461909967206666939096499764990979600

but if you define the exact same function without the @lru_cache it gets very slow because it's not benefitting from the cache.

>>> fibonacci(300)
(very very long wait)

answered May 5, 2020 at 2:36

Samwise

72.1k3 gold badges36 silver badges52 bronze badges

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

3 Comments

Tiddles Over a year ago

Thank you so much! I didn't realise that fibonacci_helper would still be called in setdefault each time. I'll start looking into decorators now too.

Samwise Over a year ago

To elaborate a little on the issue with setdefault and fibonacci_helper: when you say something like foo(bar()), then bar will be executed first in order to provide the input to foo. Nothing that happens inside foo can stop bar from being called, because it's already happened! :)

Samwise Over a year ago

Conversely, when you put something inside an if block, the thing inside the block is not executed if the condition is not met (basically the entire point of an if). That's why the "fixed" version of the function checks if n not in fib_nums before it does the computation that will add that value.

Coddy · Accepted Answer · 2023-08-16 23:26:00Z

You're close. The point of "a memo" is to save calls, but you're making recursive calls regardless of whether the result for an argument has already been memorized. So you're not actually saving the work of calling. Simplest is to define the cache outside the function, and simply return at once if the argument is in the cache:

fib_cache = {0 : 0, 1 : 1}

def fib(n):
    if n in fib_cache:
        return fib_cache[n]
    fib_cache[n] = result = fib(n-1) + fib(n-2)
    return result

Then the cache will persist across top-level calls too.

But now there's another problem ;-) If the argument is large enough (say, 30000), you're likely to get a RecursionError (too many levels of recursive calls). That's not due to using a cache, it's just inherent in very deep recursion.

You can work around that too, by exploiting the cache to call smaller arguments first, working your way up to the actual argument. For example, insert this after the if block:

    for i in range(100, n, 100):
        fib(i)

This ensures that the recursion never has to go more than 100 levels deep to find an argument already memorized in the cache. I thought I'd mention that because hardly anyone ever does when answering a "memoization" question. But memos are in fact a way not just to greatly speed some kinds of recursive algorithms, but also to apply them to some problems that "recurse too deep" without a memo constructed to limit the max call depth.

Collectives™ on Stack Overflow

Fibonacci Function Memoization in Python [duplicate]

2 Answers 2

3 Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Linked

Related