Рекурсивный факториал с использованием dict вызывает RecursionError

Простой рекурсивный факторный метод отлично работает:

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

Но мне хотелось немного поэкспериментировать и вместо этого использовать dict. Логически это должно сработать, но куча операторов печати говорит мне, что n вместо остановки в 0 скользит вниз по отрицательным числам до достижения максимальной глубины рекурсии:

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

Почему это?

Ответы

Ответ 1

Python не ленительно оценивает параметры.

Значение по умолчанию, переданное на вызов dict.get, также будет оценено перед вызовом dict.get.

Итак, в вашем случае значение по умолчанию имеет рекурсивный вызов, и поскольку ваше условие никогда не выполняется, оно делает бесконечную рекурсию.

Вы можете подтвердить это, с помощью этой программы

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

Несмотря на то, что ключ 0 существует в словаре, поскольку все параметры, переданные в функции в Python, будут вычисляться, getter также вызывается перед тем, как будет выполнен фактический dict.get.

Если все, что вы хотите сделать, - это избежать нескольких рекурсивных оценок, когда значения уже оцениваются, вы используете functools.lru_cache, если используете 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

Этот декоратор просто кэширует результаты для переданных параметров, и если один и тот же вызов выполняется снова, он просто возвращает значение из кеша.

Если вы хотите, чтобы ваша пользовательская функция кеширования работала, вам нужно определить look_up вне функции, чтобы она не создавалась всякий раз, когда вызывается функция.

>>> 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

В противном случае вы можете использовать параметр по умолчанию, например

>>> 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]