Recursive silnia przy użyciu dict powoduje RecursionError

Question

Prosta metoda rekurencyjna silnia działa perfekcyjnie:

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

Ale chciałem poeksperymentować trochę i zamiast używać dict. Logicznie rzecz biorąc, powinno to działać, ale banda sprawozdania drukowania powiedzieć, że n, zamiast zatrzymywać się na 0, sunie w dół w poprzek liczb ujemnych aż maksymalna głębokość rekurencji zostanie osiągnięty:

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

Dlaczego tak jest?

Answer 1

Python nie leniwie ocenia parametry.

Domyślna wartość przekazana do połączenia dict.get również zostanie oceniona przed wywołaniem dict.get.

W twoim przypadku wartość domyślna ma wywołanie rekurencyjne, a ponieważ twój warunek nigdy nie jest spełniony, robi nieskończoną rekursję.

Można to potwierdzić, z tym programem

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

Choć klucz 0 istnieje w słowniku, ponieważ wszystkie parametry przekazywane do funkcji w Pythonie będą oceniane, getter jest również wywoływany, przed faktycznym dict.get jest zrobione.

---

Jeśli wszystko, co chcesz zrobić, to uniknąć wielokrotnych ocen rekurencyjnych, gdy wartości są już ocenione, a następnie użyć functools.lru_cache, jeśli używasz Python 3.2 lub nowszym

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

ten dekorator prostu buforuje wyniki dla parametrów przekazanych i jeśli to samo połączenie zostanie wykonane ponownie, po prostu zwróci wartość z pamięci podręcznej.

---

Jeśli chcesz naprawić swój niestandardową funkcję buforowania do pracy, to trzeba zdefiniować look_up poza funkcją, tak, że nie będą tworzone, gdy funkcja jest wywoływana.

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

W przeciwnym wypadku można użyć parametru domyślnego, jak to

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