Простой рекурсивный факторный метод отлично работает:
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))
Почему это?
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]