How to write a recursive Python function to calculate factorials?

The factorial of a number is the product of all the positive integers from 1 to that number. For example, the factorial of 4 is 4*3*2*1 = 24.

To use a recursive Python function to calculate the factorial of a number, we can define a function that calls itself with smaller inputs until it reaches the base case, where the factorial is 1.

Below is code that uses a recursive Python function to calculate the factorial of a number:

def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)

In this code, the function factorial(n) takes a number n as input and returns the factorial of that number. The first if statement checks whether the input number n is 1. If n is 1, the function returns 1 as the base case. If n is not 1, then the function returns the product of n and the factorial of n – 1. This is where the recursive function call occurs, where the function calls itself with the input n – 1.

To use this function, you can simply call it with the number you want to find the factorial of, for example:

Example

Find the factorial of 8

def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
print(factorial(8))

Output

40320

Example

The following code calculates the factorial of n=6 and n=15

def factorial(n):
if n == 1:
return 1
else:
res = n * factorial(n-1)
return res
print ("factorial(6) = %d" %factorial(6))
print ("factorial(15) = %d" %factorial(15))

Output

factorial(6) = 720
factorial(15) = 1307674368000

Here is an example of the code:

Example

def factorial(n):
if n==0 or n == 1:
return 1
else:
return n * factorial(n-1)
print(factorial(5))

Running this code will print 120, which is the factorial of 5.

Output

120

To understand how this function works, let’s see how it calculates the factorial of 5:

The function is called with the input 5.

Since 5 is not 1, the else block is executed.

The function returns 5 * factorial(4).

To find the factorial of 4, the function is called again with the input 4.

Since 4 is not 1, the else block is executed.

The function returns 4 * factorial(3).

To find the factorial of 3, the function is called again with the input 3.

Since 3 is not 1, the else block is executed.

The function returns 3 * factorial(2).

To find the factorial of 2, the function is called again with the input 2.

Since 2 is not 1, the else block is executed.

The function returns 2 * factorial(1).

To find the factorial of 1, the function is called again with the input 1.

Since 1 is equal to 1, the if block is executed.

The function returns 1 as the base case.

The previous function call continues to be resolved.

2 * factorial(1) resolves to 2 * 1 = 2.

3 * factorial(2) resolves to 3 * 2 = 6.

4 * factorial(3) resolves to 4 * 6 = 24.

5 * factorial(4) resolves to 5 * 24 = 120.

The final result, 120, is returned.

Output

120

This procedure demonstrates how the function uses recursion to repeatedly call itself with smaller inputs until it reaches the base case of 1, and then returns the factorial of each input by multiplying it by the factorial of the next smaller input.

Here are some more examples of using recursive functions to calculate factorials of different numbers:

Example

Find the factorial of 7

def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
print(factorial(7))

Output

5040

Example

Find the factorial of 10

def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
print(factorial(10))

Output

3628800

Example

Find the factorial of 1

def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
print(factorial(1))

Output

1

Example

Find the factorial of 0 (note that the factorial of 0 is defined as 1)

def factorial(n):
if n == 1 or n == 0:
return 1
else:
return n * factorial(n-1)
print(factorial(0))

Output

1

These examples show how to use the function to find the factorial of different numbers, including the edge cases of 0 and 1.

Here is another example that shows how the function can handle large inputs:

Example

Find the factorial of 20

def factorial(n): 
if n == 1:
return 1
else:
return n * factorial(n-1)

print(factorial(20))

Output

2432902008176640000

This example shows that the function can handle large inputs without encountering errors or performance issues. However, it’s worth noting that for very large inputs, recursive functions may experience stack overflows or take a long time to execute, so in these cases, it’s better to use an iterative implementation of the factorial function.

The following is an example of an iterative implementation of the factorial function in Python:

def factorial(n):
result = 1
for i in range(1, n+1):
result *= i
return result

In this implementation, the function iterates over all numbers from 1 to n, multiplying them together to calculate the factorial. The result is stored in the variable result, which is initialized to 1.

To use this function, call it with the number whose factorial you want to find, as follows:

Example

 def factorial(n):
result = 1
for i in range(1, n+1):
result *= i
return result
print(factorial(9))

This will output 362880, the factorial of 9.

Output

362880

For very large inputs, this iterative implementation has some advantages over the recursive implementation. First, it does not suffer from stack overflow problems because it does not use function calls to calculate the factorial. Second, it is generally faster than the recursive implementation because it does not have the overhead of function calls and stack operations. However, for smaller inputs, the recursive implementation may be more concise and easier to understand.