使用dict的递归阶乘会导致RecursionError

Question

一个简单的递归因子方法非常有效:

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

这是为什么？

Answer 1

Python不会懒惰地评估参数.

dict.get在调用之前,还将评估传递给调用的默认值dict.get.

因此,在您的情况下,默认值具有递归调用,并且由于您的条件永远不会满足,因此它会执行无限递归.

您可以使用此程序进行确认

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

即使密钥0存在于字典中,因为getter在实际生成之前,也会调用传递给Python中的函数的所有参数,也会调用它们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]