How do I go about computing a factorial of an integer in Python?
10 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.
-
2I'm not understanding how you can use
factorial
within thefactorial
function. How can you use the same function within the function you're currently defining? I'm new to Python so I'm just trying to understand.– J82Commented Nov 7, 2014 at 2:32 -
14@J82: The concept used here is called recursion ( en.wikipedia.org/wiki/Recursion_(computer_science) ) - a function calling itself is perfectly fine and often useful. Commented Nov 7, 2014 at 10:06
-
5The recursive function will raise a
RecursionError
for any number larger than 998 (tryfactorial(999)
) unless you increase Python's recursion limit– user3064538Commented Dec 15, 2019 at 19:15 -
2Raising CPython's recursion limit is dangerous -- you can kill the interpreter. Just don't use recursion in Python if it can be helped (it usually can, as this example illustrates).– ggorlenCommented Oct 14, 2021 at 18:40
-
factorial(999) ≈ 4.02 × 10^2564, so it's unlikely you would want to compute such a large number anyway.– snibbetsCommented Jun 22, 2023 at 10:23
On Python 2.6 and up, try:
import math
math.factorial(n)
-
1Starting with Python 3.9, passing a
float
to this function will raise aDeprecationWarning
. If you want to do that, you need to convertn
to anint
explicitly:math.factorial(int(n))
, which will discard anything after the decimal, so you might want to check thatn.is_integer()
– user3064538Commented Nov 22, 2019 at 11:47
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)
-
3
factorial(999)
(and above) will raise aRuntimeError
unless you increase Python's recursion limit– user3064538Commented Nov 22, 2019 at 11:43
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
-
1I think this while loop looks a little bit cleaner <!-- language: python --> def fact(n): ret = 1 while n > 1: n, ret = n - 1, ret * n return ret– edilioCommented May 18, 2018 at 15:13
-
1Looks great, shouting (large font) that recursion is disastrous, but can you back this up? Yes, you need a lot of stack, but only for a very short time. And yesterday's "a lot" is today's "just a little", especially in computing. We write high level code in order to not waste our time, and recursion helps with that. You don't need low level code a lot for performance reasons, today– RolandCommented Nov 7, 2021 at 13:11
-
It also depends on the context you're using the factorial in -- recursive functions have the benefit of being cache-able, this can be particularly helpful with factorials– SchaltonCommented Feb 19, 2023 at 16:43
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.
-
2This is a Python 2-only answer,
reduce
was removed from Python 3.– user3064538Commented Nov 22, 2019 at 11:37 -
@Boris, in Python3 you just need to add
from functools import reduce
Commented Nov 24, 2019 at 22:55 -
It was removed for a reason, you shouldn't use it artima.com/weblogs/viewpost.jsp?thread=98196– user3064538Commented Nov 24, 2019 at 23:43
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))))
-
3It would be interesting to compare this to some of the other methods presented here. My guess is it's off-the-charts inefficient. Commented Jul 10, 2021 at 3:16
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 call
approach:def factorial(n): return 1 if n == 0 else n * factorial(n-1)
One line
lambda
function 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)