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
This comment has been removed by a blog administrator.
ReplyDelete