Recursive factorial using dict causes RecursionError

Question

A simple recursive factorial method works perfectly:

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

But I wanted to experiment a little and use a dict instead. Logically, this should work, but a bunch of print statements tell me that n, instead of stopping at 0, glides down across the negative numbers until the maximum recursion depth is reached:

def recursive_fact(n):
    lookup = {0: 1}
    return lookup.get(n, n*recursive_fact(n-1))

Why is that?

Answer 1

Python doesn't lazily evaluate parameters.

The default value passed to dict.get call will also be evaluated before calling the dict.get.

So, in your case, the default value has a recursive call and since your condition is never met, it does infinite recursion.

You can confirm this, with this program

>>> def getter():
...     print("getter called")
...     return 0
... 
>>> {0: 1}.get(0, getter())
getter called
1

Even though the key 0 exists in the dictionary, since all parameters passed to functions in Python will be evaluated, getter is also invoked, before the actual dict.get is made.

---

If all you want to do is to avoid multiple recursive evaluations when the values are already evaluated, then you use functools.lru_cache, if you are using Python 3.2+

>>> @functools.lru_cache()
... def fact(n):
...     print("fact called with {}".format(n))
...     if n == 0:
...         return 1
...     return n * fact(n-1)
... 
>>> fact(3)
fact called with 3
fact called with 2
fact called with 1
fact called with 0
6
>>> fact(4)
fact called with 4
24

This decorator simply caches the results for the parameters passed and if the same call is made again, it will simply return the value from the cache.

---

If you want to fix your custom caching function to work, then you need to define the look_up outside the function, so that it will not be created whenever the function is called.

>>> look_up = {0: 1}
>>> def fact(n):
...     if n not in look_up:
...         print("recursing when n is {}".format(n))
...         look_up[n] = n * fact(n - 1)
...     return look_up[n]
... 
>>> fact(3)
recursing when n is 3
recursing when n is 2
recursing when n is 1
6
>>> fact(4)
recursing when n is 4
24
>>> fact(4)
24

Otherwise you can use the default parameter, like this

>>> def fact(n, look_up={0: 1}):
...     if n not in look_up:
...         print("recursing when n is {}".format(n))
...         look_up[n] = n * fact(n - 1)
...     return look_up[n]