Recursions in closures

Question

# -*- coding: utf-8 -*-

def memoize(limit, *, message = 'Limit exceded'):
    count = 0
    def inner(func):
        cache = {}
        def wrapped(number):
            nonlocal count
            if count < limit:
                if number not in cache:
                    cache[number] = func(number)
                count += 1
                return cache[number]
            print(message)
        return wrapped
    return inner

@memoize(5)
def fat(x):
    if x < 2:
        return 1
    return x * fat(x - 1)

---

In theory the algorithm should receive a number that would define a storage limit of the results in a cache, instead of raising an exception I simply show the message that was passed or the default ("Limit exceeds") if the limit number in the cache is reached. The problem is that it only runs the program once and shows the message, but where is the error ???

Answer 1

The code is right (with the only detail that makes no sense to keep the variable count alone in memoize - she should or should be inside the inner, or the cache should be out, along with her, but this is aesthetic).

What happens is that its decorated function is itself recursive, that is, a single call to fat will call the wrapper of the decorator n times: hence it already exceeds its limit of 5 calls. Increase the call limit, or make the call to fat with a smaller number and you will see that this is it.

If you want re-entrants to fat calls not to contain to the limit, you can place a counter to detect recursion, and not increase the count internal in this case (and then, beware that the thing starts to complicate if the program is multi-thread, this recursion counter has to be a thread-local variable)

def memoize(limit, *, message = 'Limit exceded'):
    def inner(func):
        count = 0
        cache = {}
        recursing = 0
        def wrapped(number):
            nonlocal count, recursing

            if count < limit:
                recursing += 1
                if number not in cache:
                    cache[number] = func(number)
                recursing -= 1
                if not recursing:
                    count += 1
                return cache[number]
            print(message)
        return wrapped
    return inner