内置函数与递归函数

Question

我不是一个数学家，也不是一个计算机科学家-只是一个业余程序员，我试图通过做Euler项目问题自学Python。其中一个需要使用阶乘。我用递归函数编写了自己的计算，然后意识到可能有一个内置函数可以使用。找到它之后，我想我会发现它比递归函数快多了。令我惊讶的是，我发现它实际上是慢。在

这让人吃惊吗？我只是好奇。在

我附上了我的代码（为了更好的衡量，我还包括了一个循环方法，用于额外的比较）。在

import math
import time

x = 50

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

secs = time.clock()
print(math.factorial(x))
print ("The built-in function took {a:0.5f} seconds.".format(a = time.clock() - secs)) 

secs = time.clock()
print (factorial(x))
print ("The recursive function took {a:0.5f} seconds.".format(a = time.clock() - secs))

secs = time.clock()
factl = 1
for i in range (1,x+1):
    factl *= i
print (factl)
print ("The loop method took {a:0.5f} seconds.".format(a = time.clock() - secs))

输出：

304140932017133780436126081660647688443776415689605120000000000000

内置函数花费了0.00549秒。在

304140932017133780436126081660647688443776415689605120000000000000

递归函数花费了0.00299秒。在

304140932017133780436126081660647688443776415689605120000000000000

循环方法花费了0.00259秒。在

Answer 1

为了更好地比较不同函数的效率，您需要在较长的时间内多次运行测试，同时在它们之间交替运行，并为每个正在测试的函数花费最快的时间。在

由于在后台运行的进程的活动，执行时间可能因当前计算机负载的不同而变化很大。对每个被测试的功能采取最快的时间应尽量减少由于其他进程同时运行而造成的任何中断的影响。输入/输出操作（如打印到终端）更耗时，因此我建议只运行factorial(x)而不是{}。在

---

您可能还想看看python3profilers library，它是专门设计用来报告程序各个部分的执行时间的。对于基准单数函数，^{}模块将更合适。在

Answer 2

即使不使用分析库，也可以通过调整代码使其不计时打印来看到内置方法优于递归方法：

import math
import time

x = 50

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

secs = time.clock()
f = math.factorial(x)
elapsed = time.clock() - secs
print(f)
print ("The built-in function took {a:0.5f} seconds.".format(a = elapsed))

secs = time.clock()
f = factorial(x)
elapsed = time.clock() - secs
print (f)
print ("The recursive function took {a:0.5f} seconds.".format(a = elapsed))

secs = time.clock()
factl = 1
for i in range (1,x+1):
    factl *= i
elapsed = time.clock() - secs
print (factl)
print ("The loop method took {a:0.5f} seconds.".format(a = elapsed))

典型运行：

^{pr2}$

Answer 3

我取了你的代码，改变了三种方法的测试顺序，好几次。我注意到第一种测试方法的时间通常是第二种方法的两倍。在

我不能解释为什么，但我知道你不能用一次迭代来衡量函数的性能。你必须重复这个函数多次，然后计算平均时间。在

IPython提供了一个方便的“魔术方法”timeit，它可以做到：

print('math')
%timeit math.factorial(x)

print('factorial')
%timeit factorial(x)

print('loop')
%timeit loopmethod(x)

输出：

math
The slowest run took 33.62 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.25 µs per loop

factorial
100000 loops, best of 3: 19.4 µs per loop

loop
100000 loops, best of 3: 7.87 µs per loop

内置函数平均比递归函数快10倍。在