再帰的な階乗はRecursionError

Question

は単純な再帰階乗方法は完璧に動作します原因：

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

しかし、私は少しを試して、代わりにdictを使用していました。

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

はなぜそれである：最大再帰の深さに達するまで、論理的には、これは動作するはずですが、print文の束ではなく0で停止するので、nことを教え、負の数を越えダウン滑りますか？

Answer 1

Pythonはパラメータを遅延評価しません。

dict.getコールに渡されるデフォルト値は、dict.getを呼び出す前に評価されます。

したがって、デフォルト値は再帰呼び出しを持ち、条件が決して満たされないため、無限再帰を行います。

あなたは、Pythonの関数に渡されるすべてのパラメータが評価されますので、キー0は、辞書に存在しているにもかかわらず、getterが実際dict.get前に、また呼び出され、このプログラム

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

で、これを確認することができます作成されます。

---

あなたがしたいすべてが値がすでに評価されたときに、複数の再帰的な評価を避けるためであれば、あなたは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]