阶乘递归中Python的可读性与效率

Question

当我注意到这一点时，我正在玩弄python中不同的递归方法：

[为方便起见简化]

import time

def fac(n):
    if n in [0, 1]:
        return 1
    else:
        return n * fac(n-1)


def fac2(n):
    total = 1
    if n == 0:
        return total
    else:
        return n * fac2(n-1)


t0 = time.time()
fac(997)
t1 = time.time()
print(t1-t0)

t3 = time.time()
fac2(997)
t4 = time.time()
print(t4-t3)

>>> 0.00124359130859375
>>> 0.00046324729919433594

我知道time实际上并不能测量速度，但这些函数之间有一个[可以忽略不计的]整个数量级的差异

我觉得fac2()看起来更漂亮，更容易阅读，但我是否应该避免它，因为声明一个新的var可能会非常昂贵

提前谢谢你

---

编辑： 谢谢你的回复！（是的，我在说fac()更快时犯了一个错误）我从回答中得到了建议，并拨打了专一性电话：

import time

def fac(n):
    if n in [0, 1]:
        return 1
    else:
        return n * fac(n-1)


def fac2(n):
    total = 1
    if n == 0:
        return total
    else:
        return n * fac2(n-1)


def fac3(n):
    if n < 2:
        return 1
    else:
        return n * fac(n-1)


def fac4(N, m=0):
    if m == N:
        return max(1, N)
    h = (N+m)//2
    return fac4(h, m)*fac4(N, h+1)


print('fac1: ', end='')
t0 = time.time()
for i in range(1000):
    fac(997)
t1 = time.time()
print(t1-t0)

print('fac2: ', end='')
t3 = time.time()
for i in range(1000):
    fac2(997)
t4 = time.time()
print(t4-t3)

print('fac3: ', end='')
t5 = time.time()
for i in range(1000):
    fac3(997)
t6 = time.time()
print(t6-t5)

print('fac4: ', end='')
t7 = time.time()
for i in range(1000):
    fac4(997)
t8 = time.time()
print(t8-t7)

这大约是我运行程序一段时间后得到的平均值（WSL2 Ubuntu 18.04）：

fac1: 0.4169285297393799
fac2: 0.46125292778015137
fac3: 0.36595988273620605
fac4: 0.3895738124847412
>>>
fac1: 0.42001867294311523
fac2: 0.454434871673584
fac3: 0.3698153495788574
fac4: 0.3903229236602783
>>>
fac1: 0.4169285297393799
fac2: 0.46125292778015137
fac3: 0.36595988273620605
fac4: 0.3895738124847412

现在，我非常想知道为什么fac3()看起来是这群人中“最快的”。有人能解释一下原因吗

再次感谢你，提前

Answer 1

更漂亮的方法是在{}中使用{}而不是{}，并避免在{}中使用不必要的变量（或者至少给它一个适当的名称，并仅在需要时分配）

如果你想玩递归，你应该尽量避开递归深度的限制。这将更具挑战性

例如：

def fact(N,m=0):
    if m==N: return max(1,N)
    h = (N+m)//2
    return fact(h,m)*fact(N,h+1)

Answer 2

您的测量方法具有误导性：

单个函数的执行并不能说明什么：分页、编译等的成本会对结果产生重大影响。当执行函数的次数较多时，这种一次性效果的影响可以减小

以以下方式包装对不同fac函数的调用时：

t0 = time.time()
for i in range(10000):
    fac(997)
t1 = time.time()
print(t1-t0)

然后差异在3%的范围内-至少在我的系统上。基于这些微小差异的设计更改是不可取的-这些差异很容易是由于不在代码中的原因造成的（跨越缓存页边界等）

结论:

• 通常最好是可读性
• 在性能重要的地方，进行相应的测量和优化是可以的。然而，正如您的示例所示，获得可靠且有意义的测量数据并非易事
• 不同解决方案之间的性能差异越小，您就越需要了解差异的真正原因并排除环境的影响