CODEWITHSUNDEEP
pythonpython-3.x
ArthurDent
ArthurDent

Reputation: 179

Built-in functions vs recursive functions

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.

Upvotes: 4

Views: 265

Answers (3)

John Coleman
John Coleman

Reputation: 51998

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.

Upvotes: 3

Anthony Geoghegan
Anthony Geoghegan

Reputation: 11983

For a better comparison of the efficiency of the different functions, you would need to run your tests multiple times over a longer period while alternating between them and take the fastest time for each function being tested.

Execution times can vary wildly depending on current machine load due to the activity of processes running in the background. Taking the fastest time for each function being tested should minimise the effect of any interruptions due to other processes running at the same time. Input/output operations such as printing to the terminal are more time-consuming so I would advise just running factorial(x) instead of print (factorial(x)).

You also might want to look at the Python 3 profilers library which is specifically designed to report the execution times of various parts of a program. For bench-marking singles functions, the timeit module would be more appropriate.

Upvotes: 2

Mel
Mel

Reputation: 6065

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.

Upvotes: 6

Related Questions