Algorithm for Factorial of a number in Python
What is a Factorial Number?
In mathematics, the factorial of a positive integer n, denoted by n!. It is the product of all positive integers less than or equal to n.
For example, the factorial of 5 is denoted by 5! and it is equal to the product of 5, 4, 3, 2, and 1 i.e. 5*4*3*2*1 which is equal to 120. The factorial of 0, denoted by 0! is defined to be 1.
The factorial is used in various areas of mathematics, science, and engineering. It has several important properties, such as being equal to the number of ways to arrange a set of n distinct objects (a permutation of n objects), or the number of ways to select k objects from a set of n distinct objects (a combination of n objects taken k at a time).
In Python, you can compute the factorial of a number using a for loop or a recursive function. Here is an example of a for loop that calculates the factorial of a number:
def factorial(n):
result = 1
fori in range(1, n + 1):
result *= i
return result
This function takes a single integer n as input and returns the factorial of n. The function first initializes a variable result to 1. It then iterates over a range object that starts at 1 and ends at n + 1, and for each iteration, it multiplies the value of result by the loop variable and assigns the result back to result. Finally, the function returns result. You can also implement the factorial function using recursion.
What is Recursion?
Recursion is a programming technique in which a function calls itself with a modified input until it reaches a base case. Here is an example of a recursive function that calculates the factorial of a number:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
This function takes a single integer n as input and returns the factorial of n. The function first checks if ‘n’ is 0. If it is, it returns 1. Otherwise, it returns the product of n and the factorial of n - 1. This function calls itself with a modified input (n - 1) until it reaches the base case (n == 0), at which point it returns 1.
Here is the simple algorithm for finding the factorial of a number in Python:
- Define a function factorial (n) that takes in a single integer n.
- If n is less than 0, return 0.
- If n is 0 or 1, return 1.
- Initialize a variable result to 1.
- Iterate over a range object that starts at 2 and ends at n + 1. For each iteration, multiply the value of result by the loop variable and assign the result back to result.
- Return result.
Here is the implementation of this algorithm in Python:
def factorial(n):
if n < 0:
return 0
elif n == 0 or n == 1:
return 1
else:
result = 1
fori in range(2, n + 1):
result *= i
return result
You can test this function by calling it with different values of n.
Example:
import math
print(math.factorial(1))
print(math.factorial(0))
print(math.factorial(1))
print(math.factorial(5))
print(math.factorial(10))
Output:
1
1
2
120
3628800
In addition to using a ‘for’ loop or a recursive function, you can also use Python's built-in math module to calculate the factorial of a number. The math module has a function called factorial that takes a single integer n as input and returns the factorial of n.
The math.factorial function raises a ValueError if you pass a negative integer to it. Otherwise, it returns the factorial of the given integer.
There are several ways to find the factorial of a number in Python. Here are a few of them:
1. Using a for loop:
def factorial(n):
result = 1
fori in range(1, n+1):
result *= i
return result
2. Using a while loop:
def factorial(n):
result = 1
i = 1
whilei<= n:
result *= i
i += 1
return result
3. Recursive function:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
4. Using math.factorial method:
import math
def factorial(n):
return math.factorial(n)
This method uses a closed-form expression to calculate the factorial in O(1) time.
5. Using reduce method from functools:
from functools import reduce
from operator import mul
def factorial(n):
return reduce(mul, range(1, n+1))
All of these methods give the correct factorial of a given number. Recursive method is easy to understand and implement, but a large input can cause a maximum recursion depth exceeded in comparison, while the last method (using reduce method) may be less readable but more performing on large inputs.