How to write recursive Python Function to find factorial?

We can write a recursive function in Python to find the factorial of a number. Recursion means that a function calls itself repeatedly to work through different stages of the same task.

This technique is useful for tasks that follow a repetitive pattern or have a step-by-step structure like calculating factorials, generating the Fibonacci series, or navigating tree structures (tree traversal).

The factorial of a number is the product of all positive integers from 1 to that number. It is represented using the symbol n! and defined as -

n! = n X (n - 1) X (n - 2) X ... X 1

For example, 5! = 5 X 4 X 3 X 2 X 1 = 120. The given task is to write a recursive function to find the factorial of a given number.

Understanding the Recursive Approach

To write a recursive function, we need two important parts -

• Base Case: The condition that stops the recursion (when n is 0 or 1).
• Recursive Case: The part where the function calls itself with a smaller input.

Without a base case, the function would keep calling itself forever and cause a stack overflow error.

Recursive Function to Find Factorial

To write a recursive function in Python, you define a base case (which stops the recursion) and then write the recursive step (where the function calls itself).

For factorial, the base case is when n==0. In all other cases, the function calls itself with n-1 and multiplies the result by n.

Example

In the example below, the factorial() function calculates factorial recursively -

# Recursive function to find factorial
def factorial(n):
   if n == 0:
      return 1
   else:
      return n * factorial(n - 1)

# Test the function
print(factorial(5))  
print(factorial(0))  
print(factorial(3))  

The output will be as follows -

120
1
6

Understanding How Factorial Works

Let us see how the function works when we call factorial(5) -

• factorial(5) returns 5 * factorial(4)
• factorial(4) returns 4 * factorial(3)
• factorial(3) returns 3 * factorial(2)
• factorial(2) returns 2 * factorial(1)
• factorial(1) returns 1 * factorial(0)
• factorial(0) returns 1 (base case)

After reaching the base case, the function starts returning values step-by-step in reverse order -

• factorial(1) becomes 1 X 1 = 1
• factorial(2) becomes 2 X 1 = 2
• factorial(3) becomes 3 X 2 = 6
• factorial(4) becomes 4 X 6 = 24
• factorial(5) becomes 5 X 24 = 120

Handling Invalid Input

Factorials are not defined for negative numbers or non-integers. We can improve the function by checking if the input is a non-negative integer.

Example

In the example below, we define a recursive function to calculate the factorial of a number and check that the input is a valid non-negative integer -

# Improved recursive factorial with input check
def factorial(n):
   if not isinstance(n, int) or n < 0:
      return "Factorial is only defined for non-negative integers"
   if n == 0:
      return 1
   return n*factorial(n-1)

# Test with valid and invalid inputs
print(factorial(5))    
print(factorial(-3))    
print(factorial(2.5))  

Following is the output of the above code -

120
Factorial is only defined for non-negative integers
Factorial is only defined for non-negative integers