Infinite recursion in python code for factorial using a dict.get() method

Question

I wrote a Python function to compute factorial of a number, like so;

def fact(n):
    return {0: 1}.get(n, n * fact(n-1))

I was surprised to see that it leads to infinite recursion, even for fact(0). Then I added an assertion, like so;

def fact(n):
    assert n >= 0
    return {0: 1}.get(n, n * fact(n-1))

But this time AssertionError is raised, meaning n becomes negative. I don't understand this. I looked this up on the internet. But, unfortunately couldn't find any answer. Please can someone explain to me what's happening here?

Answer 1

In Python, function calls use 'eager' evaluation -- values are computed before a function is called, as opposed to computing them when a function actually uses them.

Thus, in

    {0: 1}.get(n, n * fact(n-1))

The expression n * fact(n-1) is evaluated before even calling get(). I.e. the expression is evaluated even if get() doesn't need the value at all. This is what triggers the recursion.

Answer 2

dict.get(item, default=None) is just a function taking 1 or optionally two arguments. If you pass n * fact(n-1) as the default, that expression is evaluated before being passed. The whole

return {0: 1}.get(n, n * fact(n-1))

construct seems a little artificial. The simpler

return n * fact(n-1) if n else 1

is just as concise and will evaluate the respective expressions only when their logical branch is actually entered.