A dreadful problem for recursive function: SLOW !

[GaryBAYLOR]

The function "fac" uses recursive method in defining function to calculate the factorial of an integer. The function "Fac" uses a for loop in doing the same thing. We want to compare the time these two methods and another function "math.factorial" need to spend for doing the same thing. Here is the code.

import math
def fac(n):
    n = round(n)
    if n == 0:
        return 1
    else:
        return n*fac(n-1)

def Fac(n):
    n = round(n)
    if n == 0:
        return 1
    else:
        sum = 1
        for i in range(1,n+1):
            sum *= i
        return sum


def runtime(s):
    import time
    time1 = time.clock()
    fac(s)
    time2 = time.clock()
    Fac(s)
    time3 = time.clock()
    math.factorial(s)
    time4 = time.clock()   

    x1 = time2 - time1
    x2 = time3 - time2
    x3 = time4 - time3
    print('The time function "fac" spent was: ', x1, 'seconds.')
    print('The time function "Fac" spent was: ', x2, 'seconds.')
    print('The time function "math.factorial" spent was: ', x3, 'seconds.')

Now we can run the function "runtime" with arbitrary positive integer we want to test.

>>> runtime(5)
The time function "fac" spent was:  1.1999999999900979e-05 seconds.
The time function "Fac" spent was:  8.000000000230045e-06 seconds.
The time function "math.factorial" spent was:  3.000000000419334e-06 seconds.
>>> runtime(10)

The time function "fac" spent was:  1.4000000000180535e-05 seconds.
The time function "Fac" spent was:  9.000000000369823e-06 seconds.
The time function "math.factorial" spent was:  2.9999999995311555e-06 seconds.
>>> runtime(20)

The time function "fac" spent was:  2.3000000000550358e-05 seconds.
The time function "Fac" spent was:  9.999999999621423e-06 seconds.
The time function "math.factorial" spent was:  3.000000000419334e-06 seconds.
>>> runtime(50)

The time function "fac" spent was:  4.2000000000541604e-05 seconds.
The time function "Fac" spent was:  1.4999999999432134e-05 seconds.
The time function "math.factorial" spent was:  5.999999999950489e-06 seconds.

We can see that the recursive method is even much slower than even the notorious looping for its slowness. The function "math.factorial" provided by Python itself is quickest. So recursive method should be avoided if we have better ways of coding.