← Back to Index

PYTHON RECURSION

Solve problems by allowing a function to call itself, using a clear base case and recursive case to break complex problems into smaller subproblems.

🔄 What is Recursion in Python?

Recursion is a programming technique where a function calls itself to solve a smaller version of the same problem. A recursive function normally contains two important parts: a base case, which stops the recursion, and a recursive case, which calls the function again with a smaller or simpler input.

Basic Recursion Pattern:

Function starts → Check base case → If not finished, call the same function with smaller input → Continue until base case → Return results back through previous calls
1. Basic Recursion Example
The simplest way to understand recursion is to create a function that counts down until it reaches zero. The condition that stops the function is the base case.
Python 
def countdown(number):

    if number == 0:
        print("Blast Off!")
        return

    print(number)

    countdown(number - 1)


countdown(5)
Output: 5 4 3 2 1 Blast Off!
Real-Time Example 1: Calculate Factorial
Factorial calculations are a classic example of recursion. The factorial of a number is calculated by multiplying the number by the factorial of the previous number. For example, 5! = 5 × 4 × 3 × 2 × 1.
Python 
def factorial(number):

    if number <= 1:
        return 1

    return number * factorial(number - 1)


result = factorial(5)

print("Factorial of 5:", result)
Output: Factorial of 5: 120
Execution:
factorial(5) → 5 × factorial(4) → 5 × 4 × factorial(3) → 5 × 4 × 3 × factorial(2) → 5 × 4 × 3 × 2 × factorial(1) → 120
Real-Time Example 2: Calculate Fibonacci Numbers
The Fibonacci sequence is another well-known recursion example. Each number is calculated from the two previous numbers. This concept appears in mathematical modeling, algorithm exercises, and recursive problem-solving demonstrations.
Python 
def fibonacci(number):

    if number <= 1:
        return number

    return (
        fibonacci(number - 1)
        + fibonacci(number - 2)
    )


for i in range(8):
    print(fibonacci(i), end=" ")
Output: 0 1 1 2 3 5 8 13
Real-Time Example 3: Calculate Sum of Numbers
A recursive function can calculate the total of numbers from 1 to n. Each recursive call reduces the problem until it reaches the base case.
Python 
def calculate_sum(number):

    if number == 0:
        return 0

    return number + calculate_sum(number - 1)


total = calculate_sum(10)

print("Sum from 1 to 10:", total)
Output: Sum from 1 to 10: 55
Real-Time Example 4: Reverse a String
Recursion can process a string one character at a time. The function takes the first character and recursively processes the remaining characters.
Python 
def reverse_text(text):

    if len(text) <= 1:
        return text

    return reverse_text(text[1:]) + text[0]


message = "PYTHON"

result = reverse_text(message)

print("Original:", message)
print("Reversed:", result)
Output: Original: PYTHON Reversed: NOHTYP
Real-Time Example 5: Search a Nested Folder Structure
File systems are naturally hierarchical. A folder can contain files and other folders, which can themselves contain more folders. Recursion is useful for walking through this nested structure.
Python 
folder = {
    "name": "Project",
    "files": [
        "README.md",
        "app.py"
    ],
    "folders": [
        {
            "name": "src",
            "files": [
                "main.py",
                "database.py"
            ],
            "folders": []
        },
        {
            "name": "tests",
            "files": [
                "test_app.py"
            ],
            "folders": []
        }
    ]
}


def show_files(folder):

    print("Folder:", folder["name"])

    for file in folder["files"]:
        print("  File:", file)

    for child_folder in folder["folders"]:
        show_files(child_folder)


show_files(folder)
Output: Folder: Project File: README.md File: app.py Folder: src File: main.py File: database.py Folder: tests File: test_app.py
Real-Time Example 6: Calculate Power
Recursion can calculate mathematical powers by repeatedly multiplying a number by itself until the exponent reaches zero.
Python 
def power(base, exponent):

    if exponent == 0:
        return 1

    return base * power(base, exponent - 1)


result = power(2, 5)

print("2 raised to the power 5:", result)
Output: 2 raised to the power 5: 32
Real-Time Example 7: Find Maximum Value in a List
Recursion can compare one item with the maximum value found in the remaining list. This demonstrates how a larger problem can be divided into smaller problems.
Python 
def find_max(numbers):

    if len(numbers) == 1:
        return numbers[0]

    remaining_max = find_max(numbers[1:])

    return (
        numbers[0]
        if numbers[0] > remaining_max
        else remaining_max
    )


numbers = [12, 45, 7, 89, 23, 56]

result = find_max(numbers)

print("Maximum Value:", result)
Output: Maximum Value: 89
Real-Time Example 8: Count Items in Nested Categories
E-commerce systems often organize products into nested categories. Recursion can visit every category and count all products inside the hierarchy.
Python 
catalog = {
    "name": "Store",
    "products": 5,
    "categories": [
        {
            "name": "Electronics",
            "products": 10,
            "categories": [
                {
                    "name": "Mobiles",
                    "products": 8,
                    "categories": []
                },
                {
                    "name": "Laptops",
                    "products": 6,
                    "categories": []
                }
            ]
        },
        {
            "name": "Furniture",
            "products": 12,
            "categories": []
        }
    ]
}


def count_products(category):

    total = category["products"]

    for child in category["categories"]:
        total += count_products(child)

    return total


total_products = count_products(catalog)

print("Total Products:", total_products)
Output: Total Products: 41
Real-Time Example 9: Binary Search Using Recursion
Binary search repeatedly divides a sorted list into smaller sections. It is an important example of divide-and-conquer problem solving.
Python 
def binary_search(numbers, target, low, high):

    if low > high:
        return -1

    middle = (low + high) // 2

    if numbers[middle] == target:
        return middle

    if target < numbers[middle]:
        return binary_search(
            numbers,
            target,
            low,
            middle - 1
        )

    return binary_search(
        numbers,
        target,
        middle + 1,
        high
    )


numbers = [10, 20, 30, 40, 50, 60, 70]

target = 50

index = binary_search(
    numbers,
    target,
    0,
    len(numbers) - 1
)

print("Target:", target)
print("Found at index:", index)
Output: Target: 50 Found at index: 4
Real-Time Example 10: Calculate Directory Size
A directory can contain files and other directories. A recursive function can calculate the total size by adding file sizes and recursively processing every child directory.
Python 
directory = {
    "name": "Project",
    "files": [
        {"name": "app.py", "size": 1200},
        {"name": "README.md", "size": 800}
    ],
    "folders": [
        {
            "name": "src",
            "files": [
                {"name": "main.py", "size": 2500},
                {"name": "db.py", "size": 1800}
            ],
            "folders": []
        }
    ]
}


def calculate_size(folder):

    total = 0

    for file in folder["files"]:
        total += file["size"]

    for child in folder["folders"]:
        total += calculate_size(child)

    return total


total_size = calculate_size(directory)

print("Total Directory Size:", total_size, "bytes")
Output: Total Directory Size: 6300 bytes
Real-Time Example 11: Recursive Login Attempts
Recursion can model a limited sequence of retry operations. The example below demonstrates how a function can retry an operation a fixed number of times before stopping.
Python 
def login(attempt, max_attempts):

    print("Login attempt:", attempt)

    if attempt == max_attempts:
        print("Maximum attempts reached.")
        return

    print("Login failed. Retrying...")

    login(attempt + 1, max_attempts)


login(1, 3)
Output: Login attempt: 1 Login failed. Retrying... Login attempt: 2 Login failed. Retrying... Login attempt: 3 Maximum attempts reached.
Real-Time Example 12: Recursive Menu Processing
Applications can contain nested menus such as dashboards, administration panels, and website navigation. Recursion allows every nested menu item to be processed automatically.
Python 
menu = {
    "name": "Dashboard",
    "items": [
        {
            "name": "Users",
            "items": []
        },
        {
            "name": "Reports",
            "items": [
                {
                    "name": "Sales Report",
                    "items": []
                },
                {
                    "name": "Inventory Report",
                    "items": []
                }
            ]
        }
    ]
}


def display_menu(menu, level=0):

    print("  " * level + "- " + menu["name"])

    for item in menu["items"]:
        display_menu(item, level + 1)


display_menu(menu)
Output: - Dashboard - Users - Reports - Sales Report - Inventory Report
Real-Time Example 13: Common Recursion Mistake
Every recursive function needs a condition that eventually stops recursive calls. Without a proper base case, Python continues calling the function until it raises a RecursionError.
Python 
# Incorrect example

def infinite_recursion(number):

    print(number)

    # No base case
    infinite_recursion(number + 1)


# Do not execute this example.
# It will eventually raise RecursionError.
Result: RecursionError: maximum recursion depth exceeded
Important: Always make sure your recursive function has a reachable base case and that each recursive call moves toward that base case.

Summary of Python Recursion

  • Self-Calling Function: Recursion occurs when a function calls itself.
  • Base Case: The base case tells the function when to stop calling itself.
  • Recursive Case: The recursive case reduces the problem and calls the function again.
  • Nested Data: Recursion is especially useful for folders, menus, categories, trees, and other hierarchical structures.
  • Divide and Conquer: Algorithms such as recursive binary search divide a large problem into smaller problems.
  • Stack Usage: Every recursive call creates a new function call frame on the call stack.
  • Recursion Limit: Python limits recursion depth. Very deep recursion can result in RecursionError.
  • Use Carefully: Recursion is powerful for naturally recursive problems, but an iterative solution may be simpler or more memory-efficient for many tasks.