import math
print("The factorial of 5 is: ", math.factorial(5))The factorial of 5 is: 120Factorial in Python
Factorial is the product of all positive integers less than or equal to.. For example, factorial of 5 is calculated by the equation below:
\[5! = 5 * 4 * 3 * 2 * 1 = 120\]
In Python, there is the easiest way to compute factorial. The built-in-function math provide a direct factorial number.
To implement the factorial, there are several way.
For Loop
Due to its definition, the naivest way to compute it is using for loop. Set the first value as 1, and multiply number 1 to N.
Time Complexity
With for loop, the factorial will be computed after \(N\) times of multiplications. Therefore its time complexity is \(O(N)\).
def factorial(n):
fac = 1
for i in range(n, 1, -1):
fac *= i
return fac
factorial(5)120
source code of math.factorial
static PyObject *
math_factorial(PyObject *module, PyObject *arg)
/*[clinic end generated code: output=6686f26fae00e9ca input=713fb771677e8c31]*/
{
long x, two_valuation;
int overflow;
PyObject *result, *odd_part;
x = PyLong_AsLongAndOverflow(arg, &overflow);
if (x == -1 && PyErr_Occurred()) {
return NULL;
}
else if (overflow == 1) {
PyErr_Format(PyExc_OverflowError,
"factorial() argument should not exceed %ld",
LONG_MAX);
return NULL;
}
else if (overflow == -1 || x < 0) {
PyErr_SetString(PyExc_ValueError,
"factorial() not defined for negative values");
return NULL;
}
/* use lookup table if x is small */
if (x < (long)Py_ARRAY_LENGTH(SmallFactorials))
return PyLong_FromUnsignedLong(SmallFactorials[x]);
/* else express in the form odd_part * 2**two_valuation, and compute as
odd_part << two_valuation. */
odd_part = factorial_odd_part(x);
if (odd_part == NULL)
return NULL;
two_valuation = x - count_set_bits(x);
result = _PyLong_Lshift(odd_part, two_valuation);
Py_DECREF(odd_part);
return result;
}Recursive
If loop can be a solution, recursive can be the solution either. Recursive function is a function that calls itself, like a fractal. By calling itself, the function can be computed by smaller value of the function. Therefore, ‘base case’ is required, which is the smallest value of the function. In case of factorial, factorial should be positive value. Therefore the smallest value of factorial is 1, so does base case. If the function reaches 1, the function will return 1, and the function will be computed by the previous value of the function.
Factorial can be rewritten by smaller factorial, such as:
\[5! = 5 * 4 * (4 -1) * ((4 -1) -1) * (((4 -1) -1) -1) = 5 * 4!\]
In this case, \(5!\) can be replaced with \(5 * 4!\). Similarly, \(4!\) can be replaced with \(4 * 3!\), and so on until the base case, 1. Therefore, \(5!\) is the same as \(5 * 4 * 3* 2 * 1!\).
To implement recursive function, define the function that calls itself with the smaller value of the function. like below:
def factorial(n):
# ...
return n * factorial(n - 1)The function will return \(n * (n - 1)!\), and \((n - 1)!\) will return \(n - 1 * (n - 2)!\), and so on. Yet if there is no base case, the function will be computed infinitely. Therefore, the base case have to be defined to stop the function.
This can be implemented by recursive function.
def factorial(n):
if n == 1: # the last value of the function
return 1
else:
return n * factorial(n - 1)
factorial(5)120The equation above follows the direction below:
# put n as an input of the function
n = 5
factorial_5 = factorial(5)
# since n is not 1, the factorial function will return n * (n - 1)!
factorial_5 = 5 * factorial(4)
# put n as 4, and repeat the function
factorial_4 = 5 * 4 * factorial(3)
factorial_3 = 5 * 4 * 3 * factorial(2)
factorial_2 = 5 * 4 * 3 * 2 * factorial(1)
# since n is 1, the function will return 1
factorial_1 = factorial(1)
= 1
# compute the whole function
factorial_5 = 5 * factorial_4
= 5 * 4 * factorial_3
= 5 * 4 * 3 * factorial_2
= 5 * 4 * 3 * 2 * factorial_1
= 5 * 4 * 3 * 2 * 1
= 120
Recursive Function in One Line
Furthermore, this recursive function can be written in one line.
factorial = lambda n: n * factorial(n - 1) if n > 1 else 1
factorial(5)120
Time Complexity
The factorial function computes 1 time of multiplication for each call of the function. To compute the whole factorial, the function will be called \(N\) times. Therefore, the time complexity of the recursive function is \(O(N)\).
Reduce Function
reducereduces ‘iterable’ to a single value by applying the function passed as an argument.
from functools import reduce
# reduce(function, iterable[, initial]) -> value
reduce(lambda x, y: x * y, range(1, 6), 1)120Python provides a built-in function reduce in functools module. It is a function that applies a function of the two arguments cumulatively to the items of an iterable.
In case of the example above, the lambda function lambda x, y: x * y takes two arguments x, y and multiply them. The function reduce applies the lambda function to the range of 1 to 6. Since the initial value is 1, this lambda function will multiply 1 to 1, 2, 3, 4, 5 and return 120.
# x will take 1 and computed result of the lambda function
# y will take value from 1 to 5, which came from the range
"""
x = 1, y = 1 -> 1
x = 1, y = 2 -> 2
x = 2, y = 3 -> 6
x = 6, y = 4 -> 24
x = 24, y = 5 -> 120
"""
print(reduce(lambda x, y: x * y, range(1, 2), 1))
print(reduce(lambda x, y: x * y, range(1, 3), 1))
print(reduce(lambda x, y: x * y, range(1, 4), 1))
print(reduce(lambda x, y: x * y, range(1, 5), 1))
print(reduce(lambda x, y: x * y, range(1, 6), 1))1
2
6
24
120
Fold and Reduce
reduce also termed as ‘fold’ or ‘accumulate’, ‘compress’ in functional programming. Fold recursively breaks that structure down, replacing it with the results of applying a combining function at each node on its terminal values and the recursive results. (wikipedia
Time Complexity
The reduce function applies the function to the iterable. Therefore, if the time complexity of the function is \(O(N)\) and the number of elements in the iterable is \(N\), the time complexity of the reduce function is \(O(N)\).
Time Comparison of each method
# math.factorial
import math
%timeit math.factorial(5)17.2 ns ± 0.101 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)# for loop
def fac_for(n):
fac = 1
for i in range(n, 1, -1):
fac *= i
return fac
%timeit fac_for(5)155 ns ± 14.2 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)# recursive
def fac_recursive(n):
return n * fac_recursive(n - 1) if n > 1 else 1
%timeit fac_recursive(5)176 ns ± 4.13 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)# reduce
from functools import reduce
def fac_reduce(n):
return reduce(lambda x, y: x * y, range(1, n + 1), 1)
%timeit fac_reduce(5)315 ns ± 6.19 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)