Editor

Python Program to Find the Factorial Using Recursion

Beginner · Recursion

The factorial of n, written n!, is the product of all whole numbers from 1 to n, so 5! = 5 x 4 x 3 x 2 x 1 = 120. It can also be defined in terms of itself: n! = n x (n - 1)!, with 0! = 1. That self-reference makes factorial the classic first example of recursion.

Program

factorial_using_recursion.py
def factorial(n):
# Base case: 0! and 1! are both 1, so stop here
if n <= 1:
return 1
# Recursive step: n! = n x (n - 1)!
return n * factorial(n - 1)
num = 5 # or: num = int(input("Enter a number: "))
if num < 0:
print("Factorial is not defined for negative numbers")
else:
print(f"Factorial of {num} is {factorial(num)}")
# A few more, to check the base case
for n in [0, 1, 3, 10]:
print(f"{n}! = {factorial(n)}")
Output
Factorial of 5 is 120
0! = 1
1! = 1
3! = 6
10! = 3628800

How it works

  1. The base case n <= 1 returns 1 straight away, and it is what stops the function calling itself forever.
  2. The recursive step returns n * factorial(n - 1), so to find 5! the function multiplies 5 by 4!, which it gets by calling itself with 4.
  3. The calls go down through 5, 4, 3, 2 and 1, the call with 1 hits the base case, and the answers are multiplied on the way back up: 1, 2, 6, 24, 120.
  4. Negative numbers are checked before the function is called, because the factorial is not defined for them and the function would wrongly return 1.
  5. Python allows only about 1000 nested calls, so a loop or math.factorial() is better for very large numbers.

Other ways to write it

Watching the calls happen

Watching the calls happen
def factorial(n, depth=0):
indent = " " * depth
print(f"{indent}factorial({n}) is called")
if n <= 1:
print(f"{indent}base case: return 1")
return 1
result = n * factorial(n - 1, depth + 1)
print(f"{indent}return {n} x factorial({n - 1}) = {result}")
return result
print("Answer:", factorial(4))
Output
factorial(4) is called
    factorial(3) is called
        factorial(2) is called
            factorial(1) is called
            base case: return 1
        return 2 x factorial(1) = 2
    return 3 x factorial(2) = 6
return 4 x factorial(3) = 24
Answer: 24

Each call prints a line indented one level deeper than the call that made it, so you can watch the calls go down to the base case and the results come back up.

A one-line version

A one-line version
def factorial(n):
return 1 if n <= 1 else n * factorial(n - 1)
for n in range(1, 8):
print(f"{n}! = {factorial(n)}")
Output
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040

A conditional expression, a if condition else b, fits the base case and the recursive step on one line.

Try it yourself

Write a recursive function power(base, exp) that works out base ** exp by calling power(base, exp - 1).

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises