Real-life Examples of Recursion (with Python codes)

In the previous article, I wrote about the basics of recursion. If you are new to this concept, please read that article first. This article will explore how recursion is used in real-world scenarios.

Recursion is often studied with games (like the N-Queens puzzle) or mathematical problems (such as calculating factorials). The same concepts are used to solve real-world scenarios. For instance, the warehouse management scenario is similar to solving the Tower of Hanoi. The merge sort is applied to sorting stock prices.

The code snippets here are tested in Google Colab.

People coming out of Maze using recursion (Photo by Susan Q Yin on Unsplash)

#1 — File System Navigation and Operations:

In many corporate environments, working with file systems is a common task. Recursion is often used to traverse directory structures, search for files, or perform operations on nested folders. This is particularly useful in data management, backup systems, and file organization tools.

— Example code —

• This code recursively searches a directory structure for files with a specific extension.
• Code checks if it's a directory (dictionary in Python) and if yes, it calls itself recursively to search within that directory (recursive block).
• If it's a file with the desired extension, it prints the file's path (base case).
• The process continues until all nested directories and files are checked.

# Simulated file system structure for testing
file_system = {
    'root': {
        'folder1': {
            'file1.txt': None,
            'file2.doc': None,
            'subfolder1': {
                'file3.txt': None,
                'file4.py': None
            }
        },
        'folder2': {
            'file5.jpg': None,
            'file6.txt': None
        },
        'file7.pdf': None
    }
}

# Actual recursion code starts here
def search_files(directory, file_extension, path=''):

    for name, item in directory.items():
        current_path = path + '/' + name if path else name

        if isinstance(item, dict):
            # If the item is a directory, recursively search it
            search_files(item, file_extension, current_path)

        elif name.endswith(file_extension):
            # If the item is a file and has the correct extension, print its path
            print(current_path)

# Example usage:
# Change '.txt' to the file extension you want to search for
# search_files(file_system, '.txt')

Try modifying the file_systemdictionary to add more nested folders and different file types, and see how the function adapts to find various file extensions.

#2 — Logistics and Warehouse Management

In logistics and warehouse management, a recursive algorithm can be applied to optimize the relocation of goods between different storage locations. This is particularly useful when reorganizing inventory to maximize space utilization or during large-scale relocations of warehouse sections. This concept is similar to the Tower of Hanoi problem.

— Example Code —

Imagine we have three warehouses: A, B, and C. Our goal is to move items from Warehouse A to Warehouse C in such a way that we cannot place a larger item on top of a smaller one. The relocate_items function helps us do this efficiently by using Warehouse B as an intermediate stop.

def relocate_items(n, source, target, intermediate):
    
  if n == 1:
        print(f"Move item 1 from {source} to {target}")
        return
    relocate_items(n-1, source, intermediate, target)
    print(f"Move item {n} from {source} to {target}")
    relocate_items(n-1, intermediate, target, source)

# Example usage:
"""
4 input parameters are:
    n: int - Number of items to move
    source: str - The starting location (e.g., 'Warehouse A')
    target: str - The destination location (e.g., 'Warehouse C')
    intermediate: str - The intermediate location (e.g., 'Warehouse B')

    This function prints the steps to move items from the source to the target,
    while ensuring that no larger item is placed on top of a smaller one.

n = 3  # Number of items
relocate_items(n, 'Warehouse A', 'Warehouse C', 'Warehouse B')
"""

Please search for the Tower of Hanoi to understand this problem better.

Now, let’s look at the last problem which covers a different use case.

#3 — Efficient Data Processing in Financial Analysis

In financial analysis, large datasets of stock prices, transaction records, or economic indicators often need to be sorted and processed quickly. The divide-and-conquer approach, such as the merge sort algorithm, is ideal for handling these large datasets efficiently.

— Example Code —

This code sorts a dataset of stock prices using the merge sort algorithm. The merge_sort function splits the dataset into smaller sublists, recursively sorts each sublist, and then merges them back together in sorted order.

# Recursively sort a dataset using the merge sort algorithm.

def merge_sort(data):
    if len(data) <= 1:
        return data
    
    mid = len(data) // 2
    left_half = merge_sort(data[:mid])
    right_half = merge_sort(data[mid:])
    
    return merge(left_half, right_half)

# Merge two sorted lists into one sorted list.
def merge(left, right):

    sorted_list = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i]['price'] < right[j]['price']:
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1
    
    sorted_list.extend(left[i:])
    sorted_list.extend(right[j:])
    
    return sorted_list

# Example usage:
"""
stock_prices = [
    {'date': '2024-01-01', 'price': 150},
    {'date': '2024-01-02', 'price': 142},
    {'date': '2024-01-03', 'price': 165},
    {'date': '2024-01-04', 'price': 120},
    {'date': '2024-01-05', 'price': 158},
]
sorted_prices = merge_sort(stock_prices)
print('Sorted stock prices by price:')
for record in sorted_prices:
    print(record)
""" 

Try modifying the dataset to see how the algorithm handles different financial records and scales efficiently. This method can be applied to any other large-scale data sorting.

Conclusion

In this article, we’ve explored how recursion with real-world problems. These examples provide a glimpse into the practical applications of recursion.

Here is the list of additional recursive problems to explore recursion further — binary tree traversals, dynamic programming challenges, N-Queens, Tower of Hanoi, Sudoku solvers, depth-first search (DFS), breadth-first search (BFS), quicksort, merge sort, and backtracking algorithms.

I hope this helps you with experimenting, learning, and applying recursion in various contexts. Cheers!