How Are Recursive Function Calls In Python Able To Find Keys In An Empty Dictionary?

So was playing around with memory_profiler module and noticed something weird. I was working on a function used to find nCr combinations using recursion. I made 2 version of of my

Solution 1:

Your assumption that

Each function call results in a new empty memo dict for that function.

is incorrect. Unlike in JavaScript, in Python default parameter values are evaluated at definition time, once. If the c function is called without a value for the memo parameter, the instance of the dict constructed at definition time will be used as its value each time. At construction time it is empty, but subsequent invocations may mutate it. Observe the following:

defaccumulate(a, b=[]):
    b.append(a)
    print(b)

accumulate(1)
accumulate('foo')
accumulate(None)

The above will print [1], then [1, 'foo'], then [1, 'foo', None].

Using default parameter values for memoisation is a pretty bad idea. Not only is it rather obscure and confusing, it also allows the caller to break the function by actually providing a value for the memo parameter. A better idea would be to use a global/non-local binding, or a decorator such as functools.cache or functools.lru_cache.