173

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

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Nir Levy
  • 1,993
  • 3
  • 15
  • 13

10 Answers10

238

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.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
schnaader
  • 49,103
  • 10
  • 104
  • 136
  • 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 Nov 07 '14 at 02:32
  • 14
    @J82: The concept used here is called recursion ( http://en.wikipedia.org/wiki/Recursion_(computer_science) ) - a function calling itself is perfectly fine and often useful. – schnaader Nov 07 '14 at 10:06
  • 5
    The recursive function will raise a [`RecursionError`](https://docs.python.org/library/exceptions.html#RecursionError) for any number larger than 998 (try `factorial(999)`) unless you [increase Python's recursion limit](https://stackoverflow.com/a/3323008/3064538) – Boris Verkhovskiy Dec 15 '19 at 19:15
  • 2
    Raising CPython's recursion limit is dangerous -- you can kill the interpreter. Just [don't use recursion in Python](https://stackoverflow.com/questions/67988828/why-is-python-recursion-so-expensive-and-what-can-we-do-about-it) if it can be helped (it usually can, as this example illustrates). – ggorlen Oct 14 '21 at 18:40
  • factorial(999) ≈ 4.02 × 10^2564, so it's unlikely you would want to compute such a large number anyway. – snibbets Jun 22 '23 at 10:23
120

On Python 2.6 and up, try:

import math
math.factorial(n)
Arulx Z
  • 193
  • 1
  • 13
Joril
  • 19,961
  • 13
  • 71
  • 88
  • 1
    [Starting with Python 3.9](https://bugs.python.org/issue37315), 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()`](https://stackoverflow.com/questions/21583758/how-to-check-if-a-float-value-is-a-whole-number) – Boris Verkhovskiy Nov 22 '19 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)
Tadeck
  • 132,510
  • 28
  • 152
  • 198
  • `operator.mul` could be used instead of `long.__mul__` and it would work in both [Python 2](https://docs.python.org/2/library/operator.html#operator.mul) and [Python 3](https://docs.python.org/3/library/operator.html#operator.mul). – Cristian Ciupitu Nov 22 '21 at 00:55
8
def factorial(n):
    if n < 2:
        return 1
    return n * factorial(n - 1)
Dennis
  • 56,821
  • 26
  • 143
  • 139
Nishanth
  • 89
  • 1
  • 1
  • 3
    `factorial(999)` (and above) will raise a `RuntimeError` unless you [increase Python's recursion limit](https://stackoverflow.com/a/3323008/3064538) – Boris Verkhovskiy Nov 22 '19 at 11:43
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
Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
binbjz
  • 821
  • 11
  • 15
  • 1
    I think this while loop looks a little bit cleaner def fact(n): ret = 1 while n > 1: n, ret = n - 1, ret * n return ret – edilio May 18 '18 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 Nov 07 '21 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 Feb 19 '23 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.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
John La Rooy
  • 295,403
  • 53
  • 369
  • 502
6
def fact(n):
    f = 1
    for i in range(1, n + 1):
        f *= i
    return f
Boris Verkhovskiy
  • 14,854
  • 11
  • 100
  • 103
Jordan
  • 4,928
  • 4
  • 26
  • 39
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))
Sarah
  • 1,854
  • 17
  • 18
2

Non-recursive solution, no imports:

def factorial(x):
    return eval(' * '.join(map(str, range(1, x + 1))))
Michael Hodel
  • 2,845
  • 1
  • 5
  • 10
  • 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. – Mark Ransom Jul 10 '21 at 03: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)
    
NickS1
  • 496
  • 1
  • 6
  • 19