Ad – 728×90
⚙️ Functions

Python Recursion – Functions that Call Themselves

Recursion is a technique where a function calls itself to solve a problem. It works by breaking a large problem into smaller, identical sub-problems. Every recursive solution has two parts: a base case (where it stops) and a recursive case (where it calls itself).

⏱️ 22 min read 🎯 Intermediate 📅 Updated 2026

How Recursion Works

When a function calls itself, a new frame is added to the call stack. When the base case is reached, the frames unwind and return values back up the chain.

Python
def countdown(n):
    if n <= 0:           # Base case - MUST exist to prevent infinite loop
        print("Done!")
        return
    print(n)
    countdown(n - 1)    # Recursive case - calls itself with smaller n

countdown(5)
▶ Output
5 4 3 2 1 Done!

Classic Example – Factorial

n! (n factorial) = n × (n-1) × (n-2) × ... × 1. This is the quintessential recursion example.

Python
def factorial(n):
    if n == 0 or n == 1:     # Base case
        return 1
    return n * factorial(n - 1)  # Recursive case

print(factorial(5))   # 120  (5×4×3×2×1)
print(factorial(10))  # 3628800
▶ Output
120 3628800
Ad – 336×280

Fibonacci Sequence

Fibonacci: each number is the sum of the two preceding ones. 0, 1, 1, 2, 3, 5, 8, 13...

Python
def fibonacci(n):
    if n <= 1:              # Base case
        return n
    return fibonacci(n-1) + fibonacci(n-2)  # Recursive

for i in range(8):
    print(fibonacci(i), end=" ")
▶ Output
0 1 1 2 3 5 8 13
💡
Tip

Naive Fibonacci recursion is exponentially slow (O(2^n)). Use memoization (@functools.lru_cache) for performance.

Recursion vs Iteration

Recursion is elegant but not always the best choice. Python has a default recursion limit of 1000 calls (sys.setrecursionlimit()).

Python
# Recursive factorial
def factorial_recursive(n):
    return 1 if n <= 1 else n * factorial_recursive(n - 1)

# Iterative factorial (usually preferred in Python)
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_recursive(10))  # 3628800
print(factorial_iterative(10))  # 3628800 - same result
▶ Output
3628800 3628800
Ad – 728×90