Python Recursion and Hash Tables Explained

Recursion: a function calling itself

Recursion is a technique where a function calls itself to solve a smaller version of the same problem. The key is a base case that stops the recursion, otherwise the function calls itself infinitely.

Think of it like this: to solve a big problem, solve a smaller version of it. To solve that smaller version, solve an even smaller one. Eventually you reach a trivial case (the base case) where the answer is obvious.

Recursive functions in Python

A classic example is calculating factorials. The factorial of 5 is 5 × 4 × 3 × 2 × 1, which equals 120.

A factorial is a perfect recursion example because 5! = 5 × 4!, 4! = 4 × 3!, and so on, until you reach 0! = 1 (the base case).

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

print(factorial(5))

Output:

120

The function checks if the input is 0 (base case) and returns 1. Otherwise, it returns number times the result of factorial(number - 1). This breaks the problem into smaller pieces until the base case is reached.

The importance of a base case

Without a base case, recursion never stops. Here’s an example with a safety guard:

def count(number, max_depth=10):
    if number > max_depth:
        return
    print(number, end=" ")
    number = number + 1
    count(number, max_depth)

count(0, 5)

Output:

0 1 2 3 4 5

I added a depth limit here to prevent infinite recursion. Without it, the function would keep calling itself until Python hits the recursion limit (usually 1000 calls on most systems) and raises RecursionError. Negative input to factorial() also never terminates, so always validate your inputs.

Recursion vs. loops: time and space trade-offs

A loop and a recursive function solving the same problem take the same time. Recursion doesn’t reduce time complexity. It’s a different way of thinking about the problem.

The trade-off is memory. Each function call uses stack space to store variables and return addresses. Deep recursion consumes more memory than a loop. For factorials, a loop is more efficient. But for problems like tree traversal, recursion reads more naturally and uses the call stack as implicit bookkeeping.

Hash tables: fast lookups with dictionaries

Hash tables are data structures that map keys to values using a hash function. In Python, dictionaries are the built-in hash table implementation, documented in the Python tutorial’s dictionaries section.

A hash function transforms a key into a number that determines where the value is stored. This gives you constant-time lookup in the average case: finding a value by key takes the same time whether you have 10 items or 10 million.

Using dictionaries in Python

Creating a dictionary:

employee = {"Name": "Peter Pan", 
            "Designation": "Store Manager",
            "Phone Number": 99011110222}

print(employee)

Output:

{'Name': 'Peter Pan', 'Designation': 'Store Manager', 'Phone Number': 99011110222}

Access values by key:

name = employee["Name"]
print(name)

designation = employee.get("Designation")
print(designation)

Output:

Peter Pan
Store Manager

The bracket notation and .get() method both return the value. .get() returns None if the key doesn’t exist, while brackets raise KeyError.

Update a value:

employee["Phone Number"] = 123456789
print(employee)

Output:

{'Name': 'Peter Pan', 'Designation': 'Store Manager', 'Phone Number': 123456789}

Add a new key:

employee["Age"] = 27
print(employee)

Output:

{'Name': 'Peter Pan', 'Designation': 'Store Manager', 'Phone Number': 123456789, 'Age': 27}

Adding works the same as updating. If the key exists, you overwrite it. If it’s new, you add it.

Remove values:

employee_copy = employee.copy()
employee_copy.pop("Name")
print(employee_copy)

Output:

{'Designation': 'Store Manager', 'Phone Number': 123456789, 'Age': 27}

The .pop() method removes a key-value pair by key. .popitem() removes the most recently added item (since Python 3.7, dictionaries maintain insertion order):

employee_copy2 = employee.copy()
employee_copy2.popitem()
print(employee_copy2)

Output:

{'Name': 'Peter Pan', 'Designation': 'Store Manager', 'Phone Number': 123456789}

Hash collisions: when keys map to the same bucket

A hash function can map different keys to the same location (a collision). Python’s dictionaries handle this transparently with open addressing: if a spot is taken, the dictionary probes for another empty spot in the table.

To understand how collisions work, here’s a simple deterministic hash function:

def simple_hash(key):
    return sum(ord(c) for c in str(key)) % 8

data = {"name": "Alice", "age": 30, "city": "NYC", "role": "Engineer"}

print("Key -> Bucket (hash value)")
for key in data:
    bucket = simple_hash(key)
    print(f"{key:10} -> {bucket}")

Output:

Key -> Bucket (hash value)
name       -> 1
age        -> 5
city       -> 1
role       -> 2

Notice “name” and “city” both map to bucket 1. That’s a collision. Python’s dict handles it internally, but in a naive hash table you’d have to resolve it using open addressing or chaining.

Combining recursion and hash tables: memoization

The real power comes when you combine recursion with hash tables to avoid redundant calculations. Memoization stores results in a dictionary so you don’t recompute them.

Fibonacci numbers illustrate this perfectly. fib(n) = fib(n-1) + fib(n-2). Without memoization:

def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

print(fib_naive(10))

Output:

55

But this function calls itself many times with the same arguments. fib(10) calls fib(9) and fib(8). fib(9) calls fib(8) again. That’s redundant.

With memoization:

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    
    if n in memo:
        return memo[n]
    
    if n <= 1:
        return n
    
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

print(fib_memo(10))

Output:

55

The dictionary stores results. Before recursing, we check if we’ve already computed this value. If yes, we use the cached result instead of recomputing. This transforms an exponential algorithm into a linear one.

Why Python recursion and hash tables matter

Recursion lets you think in terms of smaller subproblems. Hash tables let you store results for reuse. Together, they’re a cornerstone pattern in algorithm design.

Without memoization, some recursive problems are impossibly slow. With it, they’re efficient. The dictionary lookup is O(1), so the memoized version runs in O(n) time, not exponential time.

Memoization is a key technique in algorithm design, one of many that separate a working solution from a fast one. For another algorithm built from scratch in Python, see KNN with scikit-learn. Do you use recursion or memoization in your own code, or do loops feel more comfortable for most problems you solve?