How python decorator works with recursion?

Question

I have the below code

def memo(fn):
    cache = {}
    miss = object()
    print 'MEMO'
    def wrapper(*args):
        result = cache.get(args, miss)
        print 'IT CALLS'
        if result is miss:
            print 'IT MISSES'
            result = fn(*args)
            cache[args] = result
        return result
    return wrapper

@memo
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

when I call fib(4) it prints MEMO only once. Following is the output.

MEMO
IT CALLS
IT MISSES
IT CALLS
IT MISSES
IT CALLS
IT MISSES
IT CALLS
IT MISSES
IT CALLS
IT MISSES
IT CALLS
IT CALLS

What is causing this behaviour ??

that might be non_relevant, but you might want to use linear computation of fib using tuple of (fib(n), fib(n-1)) as return value for your fib function. — DainDwarf, Dec 02 '15 at 11:38
You really want to read *all* of [this excellent answer](https://stackoverflow.com/a/1594484/100297). — Martijn Pieters, Dec 02 '15 at 11:38

score 3 · Accepted Answer · answered Dec 02 '15 at 11:36

3

This is the correct behaviour and has nothing to do with recursion.

MEMO is printed when the decorator is called, which happens when it is applied to a function; ie, at definition time. If you never called fib() at all, MEMO would still be printed.

answered Dec 02 '15 at 11:36

Daniel Roseman

588,541
66
880
895

score 2 · Answer 2 · answered Dec 02 '15 at 11:37

2

You only print MEMO when applying the decorator. It is not part of the wrapper function, which is what the decorator produces to replace the original function.

answered Dec 02 '15 at 11:37

Martijn Pieters

1,048,767
296
4,058
3,343

How python decorator works with recursion?

2 Answers2