Built-in functions vs recursive functions

Question

I am not a mathematician, nor a computer scientist - just a hobbyist programmer and I am trying to teach myself Python by doing the Euler Project problems. One of them requires the use of a factorial. I wrote my own calculation using a recursive function and then realised that there was probably a built-in function which I could use. Having found it I thought I would see how much quicker it was than my recursive function. To my surprise I find that it is actually slower.

Does this surprise anyone? I am just curious.

I enclose my code (and for good measure I have also included a loop method for an extra comparison).

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

Output:

30414093201713378043612608166064768844377641568960512000000000000

The built-in function took 0.00549 seconds.

30414093201713378043612608166064768844377641568960512000000000000

The recursive function took 0.00299 seconds.

30414093201713378043612608166064768844377641568960512000000000000

The loop method took 0.00259 seconds.

Answer 1

I took your code and changed the order in which the three methods are tested, several times. I noticed the first method tested often takes twice as much time as the second one.

I can't really explain why, but I do know you can't measure a function's performance with one iteration. You have to repeat the function multiple time and compute the average time.

IPython comes with a handy 'magic method' timeit that does just that:

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

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

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

Output:

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

The built-in function is in average 10 times faster than the recursive function.

Answer 2

Even without using profiling libraries, you can see that the built-in method is better than your recursive one by tweaking your code so that it doesn't time the printing:

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

Typical run:

30414093201713378043612608166064768844377641568960512000000000000
The built-in function took 0.00001 seconds.
30414093201713378043612608166064768844377641568960512000000000000
The recursive function took 0.00011 seconds.
30414093201713378043612608166064768844377641568960512000000000000
The loop method took 0.00004 seconds.