Python Program to Find Factorial Using Recursion

You can find the factorial of a number using recursion in Python by defining a function like def factorial(n): return 1 if n == 0 else n * factorial(n-1) which calls itself until it reaches zero.

Examples

Input0

Output1

Input5

Output120

Input1

Output1

How to Think About It

To find the factorial of a number using recursion, think of the problem as multiplying the number by the factorial of the number just before it. Keep doing this until you reach 0, where the factorial is defined as 1. This way, the function calls itself with smaller numbers until it reaches the base case.

Algorithm

1

Get the input number n

2

Check if n is 0; if yes, return 1 as factorial of 0 is 1

3

Otherwise, call the factorial function with n-1

4

Multiply n by the result of factorial(n-1)

5

Return the multiplication result

Code

python

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

print(factorial(5))

Output

120

Dry Run

Let's trace factorial(5) through the code

1

Call factorial(5)

Since 5 != 0, return 5 * factorial(4)

2

Call factorial(4)

Since 4 != 0, return 4 * factorial(3)

3

Call factorial(3)

Since 3 != 0, return 3 * factorial(2)

4

Call factorial(2)

Since 2 != 0, return 2 * factorial(1)

5

Call factorial(1)

Since 1 != 0, return 1 * factorial(0)

6

Call factorial(0)

Since 0 == 0, return 1

7

Return values back up

factorial(1) = 1 * 1 = 1 factorial(2) = 2 * 1 = 2 factorial(3) = 3 * 2 = 6 factorial(4) = 4 * 6 = 24 factorial(5) = 5 * 24 = 120

Call	Return Value
factorial(0)	1
factorial(1)	1
factorial(2)	2
factorial(3)	6
factorial(4)	24
factorial(5)	120

Why This Works

Step 1: Base Case

The function stops calling itself when it reaches n == 0, returning 1 because factorial of zero is defined as 1.

Step 2: Recursive Call

For any other number, the function calls itself with n-1, breaking the problem into smaller parts.

Step 3: Multiplying Results

Each call multiplies the current number n by the factorial of n-1, building up the final factorial value.

Alternative Approaches

Iterative approach

python

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

print(factorial_iterative(5))

This uses a loop instead of recursion and is often easier to understand for beginners.

Using math module

python

import math
print(math.factorial(5))

This uses Python's built-in function which is optimized and simple to use.

Complexity: O(n) time, O(n) space

Time Complexity

The function calls itself n times, so the time grows linearly with the input number.

Space Complexity

Each recursive call adds a new layer to the call stack, so space used is proportional to n.

Which Approach is Fastest?

The iterative and math module methods use constant space and are faster in practice, but recursion is clearer for learning.

Approach	Time	Space	Best For
Recursion	O(n)	O(n)	Learning recursion and simple code
Iterative	O(n)	O(1)	Performance and memory efficiency
math.factorial	O(n)	O(1)	Quick and optimized built-in solution