Monday, July 11, 2011

Factorial Speed -- Recursive vs Iterative



    A rough timing comparison shows that the recursive approach is much slower.
But the code is much prettier as well as the output. The first two functions are
quiet for timing. The next two functions are instrumented to illustrate all
recursive calls are made and then the stack is unrolled.

Python Code:

from time import time

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


def factorial(n):
    if n == 0:
        return 1
    else:
        accum = 1
        for i in range(n, 1, -1):
            accum *= i
        return accum


def factorialrp(n):
    if n == 0:
        print "n == 0\n"
        return 1
    else:
        print "return (%2d * factorial(%2d - 1))" % (n, n)
    rval = (n * factorialrp(n - 1))
        print "n: %2d rval: %d" % (n, rval)
        return rval


def factorialp(n):
    if n == 0:
        return 1
    else:
        accum = 1
        for i in range(n, 1, -1):
            accum *= i
            print "i: %2d accum: %d" % (i, accum)
        return accum

print factorialrp(25)
print "\n\nnon-recursive"
print factorialp(25)

t0 = time()

for i in range (10000):
    factorialr(500)
t1 = time()

for i in range (10000):
    factorial(500)
t2 = time()

print "\n\nrough timing comparison"
print "recursive:    %f" % (t1 - t0) 
print "non-recursive %f" % (t2 - t1)

Output:

return (25 * factorial(25 - 1))
return (24 * factorial(24 - 1))
return (23 * factorial(23 - 1))
return (22 * factorial(22 - 1))
return (21 * factorial(21 - 1))
return (20 * factorial(20 - 1))
return (19 * factorial(19 - 1))
return (18 * factorial(18 - 1))
return (17 * factorial(17 - 1))
return (16 * factorial(16 - 1))
return (15 * factorial(15 - 1))
return (14 * factorial(14 - 1))
return (13 * factorial(13 - 1))
return (12 * factorial(12 - 1))
return (11 * factorial(11 - 1))
return (10 * factorial(10 - 1))
return ( 9 * factorial( 9 - 1))
return ( 8 * factorial( 8 - 1))
return ( 7 * factorial( 7 - 1))
return ( 6 * factorial( 6 - 1))
return ( 5 * factorial( 5 - 1))
return ( 4 * factorial( 4 - 1))
return ( 3 * factorial( 3 - 1))
return ( 2 * factorial( 2 - 1))
return ( 1 * factorial( 1 - 1))
n == 0

n:  1 rval: 1
n:  2 rval: 2
n:  3 rval: 6
n:  4 rval: 24
n:  5 rval: 120
n:  6 rval: 720
n:  7 rval: 5040
n:  8 rval: 40320
n:  9 rval: 362880
n: 10 rval: 3628800
n: 11 rval: 39916800
n: 12 rval: 479001600
n: 13 rval: 6227020800
n: 14 rval: 87178291200
n: 15 rval: 1307674368000
n: 16 rval: 20922789888000
n: 17 rval: 355687428096000
n: 18 rval: 6402373705728000
n: 19 rval: 121645100408832000
n: 20 rval: 2432902008176640000
n: 21 rval: 51090942171709440000
n: 22 rval: 1124000727777607680000
n: 23 rval: 25852016738884976640000
n: 24 rval: 620448401733239439360000
n: 25 rval: 15511210043330985984000000
15511210043330985984000000


non-recursive
i: 25 accum: 25
i: 24 accum: 600
i: 23 accum: 13800
i: 22 accum: 303600
i: 21 accum: 6375600
i: 20 accum: 127512000
i: 19 accum: 2422728000
i: 18 accum: 43609104000
i: 17 accum: 741354768000
i: 16 accum: 11861676288000
i: 15 accum: 177925144320000
i: 14 accum: 2490952020480000
i: 13 accum: 32382376266240000
i: 12 accum: 388588515194880000
i: 11 accum: 4274473667143680000
i: 10 accum: 42744736671436800000
i:  9 accum: 384702630042931200000
i:  8 accum: 3077621040343449600000
i:  7 accum: 21543347282404147200000
i:  6 accum: 129260083694424883200000
i:  5 accum: 646300418472124416000000
i:  4 accum: 2585201673888497664000000
i:  3 accum: 7755605021665492992000000
i:  2 accum: 15511210043330985984000000
15511210043330985984000000


rough timing comparison
recursive:    3.803000
non-recursive 2.222000



1 comment:

  1. This comment has been removed by a blog administrator.

    ReplyDelete