Python Recursion: Base Case, Call Stack and Nested Data

Imagine the regional head of a retail chain in Madhya Pradesh wants the total November sales. She does not visit every shop. She phones the Indore city manager and the Bhopal city manager and says, "Send me your city total."

The Indore manager does the same one level down, calling the Vijay Nagar, Palasia and Rajwada store heads. Each store head reads one number from the till and sends it back up. Nobody needs to know the whole structure.

That chain of phone calls is recursion. The question "what is your total?" is one function. Each manager calling the level below is the function calling itself. The store head reading the till is the base case, the point where the questions stop and answers start flowing back up.

Recursion in Python is a technique where a function calls itself on a smaller version of its input, stopping at a base case that can be answered directly, and combining the returned results.

This lesson follows Python lambda functions and builds on Python functions. The examples target Python 3.12 and later.

What is a recursive function in Python?

A recursive function has two parts. The base case handles the smallest input and returns a result immediately. The recursive case breaks the input into something smaller, calls the same function on it, and combines the answer.

Here is the smallest useful example: totalling a list of daily sales without a loop. The total of a list is the first item plus the total of the rest. The total of an empty list is zero.

def total_sales(days):
    if not days:                 # base case: nothing left to add
        return 0
    first, *rest = days          # split off one item
    return first + total_sales(rest)   # recursive case: smaller list

november = [1200, 950, 1800, 640]
print(total_sales(november))
print(total_sales([]))
print(sum(november))             # the built-in agrees

Each call works on a shorter list, which guarantees the function eventually reaches the base case.

How do you identify the base case?

Ask, "What is the simplest input whose answer I already know?" For a list it is the empty list; for a countdown, zero; for a tree, a leaf with no children. Write that case first, at the top of the function.

How does the call stack work in recursion?

Every time Python calls a function, it creates a frame: a small workspace holding that call's local variables. Frames pile up on the call stack. When a call returns, its frame is removed and its result is handed to the frame below.

With recursion, the stack grows one frame per call until the base case is reached. Then the frames unwind in reverse order, each one finishing its addition with the value it received.

Calls go down until the base case returns 0, then each frame adds its own item on the way back up.

You can watch this happen by printing with indentation that matches the depth.

def total_sales(days, depth=0):
    pad = "    " * depth
    print(f"{pad}total_sales({days})")
    if not days:
        print(f"{pad}-> base case returns 0")
        return 0
    result = days[0] + total_sales(days[1:], depth + 1)
    print(f"{pad}-> returns {result}")
    return result

total_sales([1200, 950, 1800])

The first lines show the stack growing; the last ones show it unwinding. Nothing is added until the base case answers, so the additions print in reverse order.

Recursion on nested data: summing a sales tree

The list example is a teaching toy; sum() does it better. Recursion earns its place when data is nested to an unknown depth, like the regional sales structure from the opening.

A dictionary can model that tree. A key maps either to a number (a store, the base case) or to another dictionary (a region with children, the recursive case).

Each node asks its children for their totals; only the leaf stores read a number directly.

sales = {
    "Indore": {"Vijay Nagar": 48200, "Palasia": 39100,
               "Rajwada": {"Main shop": 22500, "Kiosk": 6400}},
    "Bhopal": {"MP Nagar": 41800, "New Market": 27300},
    "Ujjain": 18900,
}

def tree_total(node):
    if isinstance(node, (int, float)):      # base case: a store
        return node
    return sum(tree_total(child) for child in node.values())

print("Region total:", tree_total(sales))
for city, node in sales.items():
    print(f"{city:<7} {tree_total(node):>7,}")

The function does not care that Rajwada has a sub-level and Ujjain has none. Each call looks at one node and trusts the recursive calls to handle whatever sits underneath.

Flattening nested lists

Flattening is another common task. Survey exports sometimes deliver tags as lists inside lists.

def flatten(items):
    flat = []
    for item in items:
        if isinstance(item, list):
            flat.extend(flatten(item))   # recursive case: go inside
        else:
            flat.append(item)            # base case: a plain value
    return flat

tags = ["sale", ["festive", ["diwali", "gift"]], "indore", [["repeat"]]]
print(flatten(tags))
print(len(flatten(tags)), "tags")

Here the base case sits inside the loop: a plain value is appended directly, while a list triggers another call. The same pattern works for nested JSON, which you will meet again in working with JSON in Python.

What is the recursion limit in Python?

Each frame uses memory, so Python caps how deep the stack can grow. The default limit is 1,000 frames, which you can read with sys.getrecursionlimit(). Going past it raises RecursionError instead of crashing the interpreter.

The usual cause is a missing or unreachable base case. The demo below lowers the limit to 50 to trigger the error quickly and safely, then restores it.

import sys

def countdown_broken(n):
    return countdown_broken(n - 1)      # no base case: never stops

print("Default limit:", sys.getrecursionlimit())
old = sys.getrecursionlimit()
sys.setrecursionlimit(50)
try:
    countdown_broken(10)
except RecursionError as err:
    print("Stopped:", type(err).__name__)
finally:
    sys.setrecursionlimit(old)
print("Limit restored:", sys.getrecursionlimit())

Raising the limit is rarely the right fix. If real data is that deep, such as a chain of 50,000 referral records, rewrite the function as a loop. The try and finally pattern used here is explained properly in Python exception handling.

Making recursion fast with functools.cache

Some recursive functions call themselves more than once per step, and end up solving the same small problem many times. Caching remembers each answer so it is computed only once.

Suppose a warehouse packs orders using 1 kg and 2 kg bags. How many different sequences of bags make up an order of n kg? The answer for n is the answer for n - 1 (start with a 1 kg bag) plus the answer for n - 2 (start with a 2 kg bag).

from functools import cache

calls = 0
def ways(n):
    global calls
    calls += 1
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

print(ways(22), "ways,", calls, "calls without cache")

@cache
def ways_fast(n):
    if n <= 1:
        return 1
    return ways_fast(n - 1) + ways_fast(n - 2)

print(ways_fast(22), "ways,", ways_fast.cache_info().misses, "distinct calls with cache")

Without a cache the function makes more than 57,000 calls for a 22 kg order. With @cache it computes each n exactly once, so 23 calls are enough. The @ line is a decorator, covered later in Python decorators. The global calls line is explained in the next lesson.

Recursion vs iteration: which should you use?

Anything recursion can do, a loop with an explicit stack can do too. The choice is about clarity and the shape of your data.

def total_loop(days):
    running = 0
    for amount in days:
        running += amount
    return running

def tree_total_loop(root):
    total, stack = 0, [root]
    while stack:
        node = stack.pop()
        if isinstance(node, dict):
            stack.extend(node.values())
        else:
            total += node
    return total

print(total_loop([1200, 950, 1800, 640]))
print(tree_total_loop({"Indore": {"A": 48200, "B": {"C": 22500}}, "Ujjain": 18900}))

The loop version keeps its own list of nodes still to visit, which is what the call stack did for you automatically. Day to day, analysts mostly write loops and pandas operations, and reach for recursion when data is nested.

Common mistakes with Python recursion

• No base case, or one that is never reached. For example, countdown(n - 2) starting at an odd number skips past n == 0. Use n <= 0 for safety.
• Not returning the recursive result. Writing total_sales(rest) without return makes the function return None.
• Forgetting to shrink the input. Calling f(items) instead of f(items[1:]) recurses forever.
• Using recursion on long flat lists. A list of 5,000 transactions will hit the recursion limit. Use a loop or sum().
• Repeating work. Branching recursion without @cache can make millions of calls for small inputs.

Key takeaways

• A recursive function calls itself on a smaller input and combines the results.
• Write the base case first; make sure every recursive call moves towards it.
• Each call adds a frame to the call stack, and frames unwind in reverse order.
• Recursion suits nested data of unknown depth; loops suit flat data.
• The default limit is about 1,000 levels; deep data needs an iterative rewrite.
• functools.cache turns slow branching recursion into fast recursion.

Next, learn which variables a function can see and change in Python variable scope. For a guided path from Python basics to analysis projects, see the Python-to-pandas data analytics course in Indore.