How do I go about computing a factorial of an integer in Python?
010 Answers
The easiest way is to use math.factorial (available in Python 2.6 and above):
import math math.factorial(1000) If you want/have to write it yourself, you can use an iterative approach:
def factorial(n): fact = 1 for num in range(2, n + 1): fact *= num return fact or a recursive approach:
def factorial(n): if n < 2: return 1 else: return n * factorial(n-1) Note that the factorial function is only defined for positive integers, so you should also check that n >= 0 and that isinstance(n, int). If it's not, raise a ValueError or a TypeError respectively. math.factorial will take care of this for you.
On Python 2.6 and up, try:
import math math.factorial(n) Existing solution
The shortest and probably the fastest solution is:
from math import factorial print factorial(1000) Building your own
You can also build your own solution. Generally you have two approaches. The one that suits me best is:
from itertools import imap def factorial(x): return reduce(long.__mul__, imap(long, xrange(1, x + 1))) print factorial(1000) (it works also for bigger numbers, when the result becomes long)
The second way of achieving the same is:
def factorial(x): result = 1 for i in xrange(2, x + 1): result *= i return result print factorial(1000) def factorial(n): if n < 2: return 1 return n * factorial(n - 1) For performance reasons, please do not use recursion. It would be disastrous.
def fact(n, total=1): while True: if n == 1: return total n, total = n - 1, total * n Check running results
cProfile.run('fact(126000)') 4 function calls in 5.164 seconds Using the stack is convenient (like recursive call), but it comes at a cost: storing detailed information can take up a lot of memory.
If the stack is high, it means that the computer stores a lot of information about function calls.
The method only takes up constant memory (like iteration).
Or using a 'for' loop
def fact(n): result = 1 for i in range(2, n + 1): result *= i return result Check running results
cProfile.run('fact(126000)') 4 function calls in 4.708 seconds Or using the built-in function math
def fact(n): return math.factorial(n) Check running results
cProfile.run('fact(126000)') 5 function calls in 0.272 seconds If you are using Python 2.5 or older, try
from operator import mul def factorial(n): return reduce(mul, range(1, n+1)) For newer versions of Python, there is factorial in the math module as given in other answers here.
3def fact(n): f = 1 for i in range(1, n + 1): f *= i return f Another way to do it is to use np.prod shown below:
def factorial(n): if n == 0: return 1 else: return np.prod(np.arange(1,n+1)) Non-recursive solution, no imports:
def factorial(x): return eval(' * '.join(map(str, range(1, x + 1)))) You can also make it in one line recursively if you like it. It is just a matter of personal choice. Here we are using inline if else in Python, which is similar to the ternary operator in Java:
Expression1 ? Expression2 : Expression3 One line
function callapproach:def factorial(n): return 1 if n == 0 else n * factorial(n-1)One line
lambdafunction approach:(although it is not recommended to assign lambda functions directly to a name, as it is considered a bad practice and may bring inconsistency to your code. It's always good to know. See PEP8.)
factorial = lambda n: 1 if n == 0 else n * factorial(n-1)
