177

How do I go about computing a factorial of an integer in Python?

0

10 Answers 10

244

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.

5
  • 2
    I'm not understanding how you can use factorial within the factorial 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.
    – J82
    Commented 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.
    – schnaader
    Commented Nov 7, 2014 at 10:06
  • 5
    The recursive function will raise a RecursionError for any number larger than 998 (try factorial(999)) unless you increase Python's recursion limit
    – user3064538
    Commented Dec 15, 2019 at 19:15
  • 2
    Raising 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).
    – ggorlen
    Commented 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.
    – snibbets
    Commented Jun 22, 2023 at 10:23
120

On Python 2.6 and up, try:

import math
math.factorial(n)
1
  • 1
    Starting with Python 3.9, passing a float to this function will raise a DeprecationWarning. If you want to do that, you need to convert n to an int explicitly: math.factorial(int(n)), which will discard anything after the decimal, so you might want to check that n.is_integer()
    – user3064538
    Commented Nov 22, 2019 at 11:47
24

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)
1
8
def factorial(n):
    if n < 2:
        return 1
    return n * factorial(n - 1)
1
7

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
3
  • 1
    I 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
    – edilio
    Commented May 18, 2018 at 15:13
  • 1
    Looks 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
    – Roland
    Commented 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
    – Schalton
    Commented Feb 19, 2023 at 16:43
7

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.

3
  • 2
    This is a Python 2-only answer, reduce was removed from Python 3.
    – user3064538
    Commented 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
    – user3064538
    Commented Nov 24, 2019 at 23:43
6
def fact(n):
    f = 1
    for i in range(1, n + 1):
        f *= i
    return f
3

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))
2

Non-recursive solution, no imports:

def factorial(x):
    return eval(' * '.join(map(str, range(1, x + 1))))
1
  • 3
    It 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
0

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)
    

Not the answer you're looking for? Browse other questions tagged or ask your own question.