I have the following code for calculating the factorial of a number in python. but I couldnt understand why I am getting the answer as 1. can some one correct my code. I want to calculate the factorial without using recursion.
def factorial (n):
result =1
num = n
while n<1:
result = result * num
num = num -1
return result
factorial(5)
1
while n < 1:
should instead be
while num > 1:
Others pointed out what's wrong with your code, but I wanted to point out that a factorial function really lends itself to a more functional (as in: functional programming) solution; this avoids the issue with getting the condition for the while loop altogether because you don't have any loop at all. The insight is that the factorial of n is the product of 1..n, and the product can be defind very easily using Python's reduce function. To avoid losing performance out of sight, here's what my Python 2.7 interpreter gives for your (fixed) code:
python -m timeit -s "import original" "original.factorial(10)"
1000000 loops, best of 3: 1.22 usec per loop
A shorter version (a one-liner) which is more declarative is possible:
def factorial(n):
return reduce(lambda x,y: x*y, range(1, n+1))
...alas, it's slower:
python -m timeit -s "import func1" "func1.factorial(10)"
1000000 loops, best of 3: 1.98 usec per loop
However, this can be solved by using xrange instead of range and operator.mul instead of a custom lambda:
import operator
def factorial(n):
return reduce(operator.mul, xrange(1, n+1))
And for me, this is even faster than the original code:
python -m timeit -s "import func2" "func2.factorial(10)"
1000000 loops, best of 3: 1.14 usec per loop
Personally, I'd factor out the reduce call to make the code even clearer (at the expense of a tiny little bit of performance):
import operator
def product(it):
return reduce(operator.mul, it)
def factorial(n):
return product(xrange(1, n+1))
I like this version for being fast, and for being explicit: the factorial is defined to be the product of the range [1..n+1[ (i.e. n+1 is excluded). The performance difference becomes more apparent if you try to compute the factorial of larger numbers:
python -m timeit -s "import original" "original.factorial(30)"
100000 loops, best of 3: 5.25 usec per loop
vs.
python -m timeit -s "import func3" "func3.factorial(30)"
100000 loops, best of 3: 3.96 usec per loop
for loop is needed).n<1 to num>1." ;-)
while 5 < 1 is always false, so result = 1 is returned. That's wrong.
Let's see:
n=5 when you call the function.n < 1 do things.n is already bigger than 1, it won't execute the while code .result, set to 1 in the first line of the definition.As Simon Gibbons explained, your code has
while n < 1:
instead of
while num > 1:
So you have less than instead of greater than, thus the test in your while statement will fail immediately. However, if you changed it to while n > 1: it would loop forever, since you never change the value of n inside the while loop.
Haresh Shyara posted a corrected version of your code, reproduced here:
def factorial(n):
result = 1
while n > 1:
result = result * n
n = n - 1
return result
Note that this code doesn't bother with copying n to num - it just uses n directly. This will not affect the argument that you call the function with because
n = n - 1 actually creates a new local object named n.I was inspired by Frerich Raabe's answer to write a program to do the timings of the various solutions offered here in a more systematic fashion. I've also included the math.factorial() and a simple for loop based function I just threw together.
I've optimized the functions that call operator.mul slightly by defining mul = operator.mul, but I had to supply an initial parameter of 1 to those functions that use reduce() so that they don't fail on factorial(0) (which should return 1).
I've approximately ordered the functions from fastest to slowest.
I've just enhanced this program to make it a little easier to run multiple tests and to add new functions to test. Also, it now prints a brief description of each function, using the function's docstring. And before running the timing tests it verifies that each function calculates correct values.
#!/usr/bin/env python
''' Test and time various implementations of the factorial function
From https://stackoverflow.com/q/28475637/4014959
Written by PM 2Ring 2015.02.13
'''
import operator
import math
from timeit import Timer
factorial0 = math.factorial
def factorial0a(n):
''' call math.factorial '''
return math.factorial(n)
def factorial1(n):
''' for loop'''
p = 1
for i in xrange(2, n+1):
p *= i
return p
mul = operator.mul
def product(it):
return reduce(mul, it, 1)
def factorial2(n):
''' reduce with op.mul '''
return reduce(mul, xrange(1, n+1), 1)
def factorial3(n):
''' call product() '''
return product(xrange(1, n+1))
def factorial4(n):
''' while loop '''
result = 1
while n > 1:
result = result * n
n = n - 1
return result
def factorial4a(n):
''' while loop with assignment operators '''
result = 1
while n > 1:
result *= n
n -= 1
return result
def factorial5(n):
''' recursive '''
if n <= 1:
return 1;
else:
return n*factorial5(n-1)
def factorial6(n):
''' reduce with lambda '''
return reduce(lambda res, val: res*val, xrange(n, 0, -1), 1)
funcs = (
factorial0,
factorial0a,
factorial1,
factorial2,
factorial3,
factorial4,
factorial4a,
factorial5,
factorial6,
)
def verify(n):
''' Check that each function calculates the same result as math.factorial '''
r = xrange(n)
fac = [factorial0(i) for i in r]
rc = True
for func in funcs[1:]:
for i in r:
v = func(i)
if v != fac[i]:
print 'Error: %s(%d) returns %d instead of %d' % (func.func_name, i, v, fac[i])
rc = False
return rc
def time_test(arg=10, loops=100000, reps=3):
''' Print timing stats for all the factorial functions '''
print 'Arg = %d, Loops = %d, Repetitions = %d' % (arg, loops, reps)
for func in funcs:
#Get function name and docstring
try:
fname = func.func_name
fdoc = func.__doc__
except AttributeError:
#Math.factorial has no name, and we can't modify its docstring
fname = 'factorial0'
fdoc = ' math.factorial itself '
print '\n%s:%s' % (fname, fdoc)
t = Timer('%s(%d)' % (fname, arg), 'from __main__ import %s' % fname)
r = t.repeat(reps, loops)
r.sort()
print r
print '\n'
def main():
if not verify(100): exit(1)
time_test(arg=5, loops=500000, reps=4)
time_test(arg=10, loops=200000, reps=4)
time_test(arg=50, loops=100000, reps=4)
if __name__ == '__main__':
main()
output
Arg = 5, Loops = 500000, Repetitions = 4
factorial0: math.factorial itself
[0.30838108062744141, 0.3119349479675293, 0.31210899353027344, 0.32166290283203125]
factorial0a: call math.factorial
[0.62141299247741699, 0.62747406959533691, 0.63309717178344727, 0.66500306129455566]
factorial1: for loop
[1.4656128883361816, 1.476855993270874, 1.4897668361663818, 1.5052030086517334]
factorial2: reduce with op.mul
[1.5841941833496094, 1.5868480205535889, 1.6007061004638672, 1.6253509521484375]
factorial3: call product()
[1.8745129108428955, 1.8750350475311279, 1.8822829723358154, 1.9097139835357666]
factorial4: while loop
[1.1264691352844238, 1.1348199844360352, 1.1348659992218018, 1.178135871887207]
factorial4a: while loop with assignment operators
[1.1867551803588867, 1.1881229877471924, 1.1893219947814941, 1.2020411491394043]
factorial5: recursive
[1.9756920337677002, 1.9862890243530273, 1.9910380840301514, 2.0284240245819092]
factorial6: reduce with lambda
[2.8342490196228027, 2.8369259834289551, 2.8390510082244873, 2.8969988822937012]
Arg = 10, Loops = 200000, Repetitions = 4
factorial0: math.factorial itself
[0.24756813049316406, 0.24919605255126953, 0.26395106315612793, 0.28582406044006348]
factorial0a: call math.factorial
[0.3732609748840332, 0.37482404708862305, 0.37592387199401855, 0.38288402557373047]
factorial1: for loop
[0.88677501678466797, 0.89632201194763184, 0.89948821067810059, 0.90272784233093262]
factorial2: reduce with op.mul
[0.89040708541870117, 0.89259791374206543, 0.89863204956054688, 0.90652203559875488]
factorial3: call product()
[1.0093960762023926, 1.031667947769165, 1.2325050830841064, 1.7492170333862305]
factorial4: while loop
[0.93423891067504883, 0.93978404998779297, 0.94000387191772461, 0.95153117179870605]
factorial4a: while loop with assignment operators
[0.97296595573425293, 0.97462797164916992, 0.98288702964782715, 1.0095341205596924]
factorial5: recursive
[1.6726200580596924, 1.6786048412322998, 1.691572904586792, 1.6946439743041992]
factorial6: reduce with lambda
[1.8484599590301514, 1.8502249717712402, 1.8615908622741699, 1.9228360652923584]
Arg = 50, Loops = 100000, Repetitions = 4
factorial0: math.factorial itself
[1.6450450420379639, 1.6641650199890137, 1.6790158748626709, 1.7192811965942383]
factorial0a: call math.factorial
[1.7563199996948242, 2.0039281845092773, 2.1530590057373047, 2.3621060848236084]
factorial1: for loop
[2.7895750999450684, 2.8117640018463135, 2.8381040096282959, 3.0019519329071045]
factorial2: reduce with op.mul
[2.4697721004486084, 2.4750289916992188, 2.4813871383666992, 2.5051541328430176]
factorial3: call product()
[2.4983038902282715, 2.4994339942932129, 2.5271379947662354, 2.5356400012969971]
factorial4: while loop
[3.6446011066436768, 3.650169849395752, 3.6579680442810059, 3.7304909229278564]
factorial4a: while loop with assignment operators
[3.7421870231628418, 3.7477319240570068, 3.7655398845672607, 3.7749569416046143]
factorial5: recursive
[5.523845911026001, 5.5555410385131836, 5.5760359764099121, 6.2132260799407959]
factorial6: reduce with lambda
[4.9984982013702393, 5.0106558799743652, 5.0363597869873047, 5.0808289051055908]
As with all timeit results, the fastest entries in each list are the significant ones, the slower ones should be ignored.
From the timeit docs (courtesy of Ffisegydd):
... the lowest value gives a lower bound for how fast your machine can run the given code snippet; higher values in the result vector are typically not caused by variability in Python’s speed, but by other processes interfering with your timing accuracy. So the
min()of the result is probably the only number you should be interested in...
xrange() is a bit silly, but it just iterates over the integers from n down to 1.reduce passes the function two values, one is the current result (res), the other is the current element from the iterable (val), the result of the function is saved by reduce so it can pass it back to the function on the next step. The example code in the docs for reduce that I linked earlier illustrates that process. I'll post some code that uses a for loop which is equivalent to volcano's code, but I'll edit it into volcano's question, since it is his code I'm explaining.Your code will not enter in the while loop itself. Change it from n<1 to n>1. If for example, finding factorial of 5, n<1 will be treated as 5<1 which is false.
def factorial(n):
result = 1
while n > 1:
result = result * n
n = n - 1
return result
print factorial(5)
120
Try this, it's cleaner:
def factorial( n ):
if n <= 1:
return 1;
else:
return n*factorial(n-1)
This is a recursive way to solve the problem.
Speaking of short Pythonic code
def factorial(n):
return reduce(lambda res, val: res*val, xrange(n, 0, -1), 1)
For those that don't understand how volcano's code works, here is a close approximation:
''' Equivalent code by PM 2Ring '''
def f(res, val):
return res * val
def factorial(n):
res = 1
for val in xrange(n, 0, -1):
res = f(res, val)
return res
factorial(0).
n, but you change onlyresultandnumin the loop. The loop will run 0 or infinite times.math.factorialis much faster.