Recursion and Backtracking Questions

The idea in plain words

The natural solution is recursive: for each key, if the value is a dict, recurse with the path so far, otherwise yield the path. The trouble is that Python allows about 1,000 nested calls by default (sys.getrecursionlimit()), after which it raises RecursionError. A dictionary nested 50,000 levels deep breaks it. Such a dictionary is built by a loop (as the demo below does) or by a parser that does not recurse; Python 3.12's own json.loads raises RecursionError on 50,000 nested objects, so it cannot be the source.

The fix is to do what the call stack was doing, yourself. Each recursive call is just "a dict I am partway through scanning". Keep those in a list used as a stack: one iterator per dict (an object that remembers where it stopped) plus a list of the keys that lead to it. The call stack is the fixed-size region of memory where the language keeps one frame (the arguments and local variables) for every function call that has started and not yet returned; its size is what the depth limit protects. The heap is the general pool of memory where objects such as lists live, and it grows as needed until the machine runs out. A list on the heap therefore grows with available memory, not with the call-stack limit.

Approach

1. stack holds one iter(dict.items()) per dict we are still inside; keys holds the keys from the root to the current dict.
2. Take the next (key, value) from the iterator on top of the stack.
3. If value is a dict: push its iterator and append key to keys (go down).
4. Otherwise it is a leaf: yield the keys joined with dots plus this key.
5. If the top iterator is exhausted: pop it and drop the last key (go back up). The root dict has no key of its own in keys, so when the root iterator finishes keys is already empty and the if keys: guard skips the pop; without the guard, keys.pop() on an empty list would raise IndexError at the very end.

Because the function uses yield, it is a generator: it produces one path at a time, only when the caller asks, so the caller can stop early and memory stays at O(depth) rather than O(all paths).

Code

def leaf_paths(tree, sep="."):
    """Yield dotted key paths to every leaf, using an explicit stack so depth is limited by memory, not by the call stack."""
    keys = []                                   # keys on the path from the root to the current dict
    stack = [iter(tree.items())]                # one iterator per dict we are still scanning
    while stack:
        try:
            key, value = next(stack[-1])
        except StopIteration:                   # this dict is finished: step back up
            stack.pop()
            if keys:
                keys.pop()
            continue
        if isinstance(value, dict):
            keys.append(str(key))               # go down; the iterator remembers where each level stopped
            stack.append(iter(value.items()))
        else:
            yield sep.join(keys + [str(key)])


def leaf_paths_recursive(tree, prefix=""):
    for key, value in tree.items():
        path = f"{prefix}.{key}" if prefix else str(key)
        if isinstance(value, dict):
            yield from leaf_paths_recursive(value, path)
        else:
            yield path


def build_deep(depth):
    root = {"leaf": 1}
    for _ in range(depth):
        root = {"k": root}
    return root


if __name__ == "__main__":
    data = {"a": {"b": 1, "c": {"d": 2}}, "e": 3}
    print(list(leaf_paths(data)))
    print(list(leaf_paths_recursive(data)) == list(leaf_paths(data)))

    deep = build_deep(50_000)
    try:
        next(leaf_paths_recursive(deep))
    except RecursionError:
        print("recursive version at depth 50000: RecursionError")
    path = next(leaf_paths(deep))
    print("iterative version at depth 50000: path length", len(path), "characters, ends with", path[-8:])
    print(list(leaf_paths({})), list(leaf_paths({"a": {}, "b": 2})))

Output:

['a.b', 'a.c.d', 'e']
True
recursive version at depth 50000: RecursionError
iterative version at depth 50000: path length 100004 characters, ends with k.k.leaf
[] ['b']

In the recursive version, yield from leaf_paths_recursive(value, path) hands control to the inner generator and passes each value it yields straight out to the caller; it behaves like for item in inner: yield item, but written in one expression. The recursive version is included only for comparison. It raises RecursionError at depth 50,000; the iterative version returns the path, which is 100,004 characters long (50,000 copies of k. followed by leaf).

Worked trace

This is the printed output of an instrumented copy of the same loop on the example from the question.

def leaf_paths_traced(tree, sep="."):
    keys = []
    stack = [iter(tree.items())]
    step = 0
    while stack:
        step += 1
        try:
            key, value = next(stack[-1])
        except StopIteration:
            stack.pop()
            if keys:
                keys.pop()
            print(f"{step:2d} finished a dict      depth={len(stack)} keys={keys}")
            continue
        if isinstance(value, dict):
            keys.append(str(key))
            stack.append(iter(value.items()))
            print(f"{step:2d} enter {key!r:4}          depth={len(stack)} keys={keys}")
        else:
            print(f"{step:2d} leaf  {key!r:4} yield {sep.join(keys + [str(key)])!r}")
            yield sep.join(keys + [str(key)])

print(list(leaf_paths_traced({"a": {"b": 1, "c": {"d": 2}}, "e": 3})))

 1 enter 'a'           depth=2 keys=['a']
 2 leaf  'b'  yield 'a.b'
 3 enter 'c'           depth=3 keys=['a', 'c']
 4 leaf  'd'  yield 'a.c.d'
 5 finished a dict      depth=2 keys=['a']
 6 finished a dict      depth=1 keys=[]
 7 leaf  'e'  yield 'e'
 8 finished a dict      depth=0 keys=[]
['a.b', 'a.c.d', 'e']

Step 5 closes the dict under 'c' and removes 'c' from keys; step 6 closes the dict under 'a'; step 7 resumes the root iterator, which is why 'e' comes after the others and the order matches the recursive version.

Complexity

Let D be the nesting depth, L the number of leaves and P the total length of all output paths.

• Time: every dict entry is visited once, plus a join per leaf that costs O(length of that path). The total is O(number of entries + P). Output size is the unavoidable part.
• Space: O(D) for the stack and the keys list, plus O(length of one path) for the string being built. Nothing is held for earlier paths. The recursive version uses the same O(D) in call frames, but frames are limited to about 1,000 by default; the explicit stack is limited only by memory.
• Building each path by string concatenation at every level (prefix + "." + key) costs O(D^2) characters over a chain of depth D, because every level creates a new string. Joining once at the leaf avoids that.

Edge cases and decisions to state out loud

• Empty input {} yields nothing, and so does an empty nested dict ({"a": {}}) because it has no leaf. If you want 'a' reported, treat an empty dict as a leaf.
• Non-string keys are converted with str, so 1 and "1" produce the same path text.
• A key that itself contains a dot makes paths ambiguous ({"a.b": 1} and {"a": {"b": 1}} both give 'a.b'). Offer a different separator or return tuples of keys.
• Lists as values: this version treats a list as a leaf. Say so, or extend the isinstance check and add the index to the path.
• A dict that contains itself never finishes: the iterative version keeps pushing iterators until memory runs out and Python raises MemoryError (the recursive version would raise RecursionError). Track id(value) of the dicts on the current path if cycles are possible.
• Changing the dict while the generator is running raises RuntimeError: dictionary changed size during iteration.

Checking it

A random-input test compares the iterative generator with the recursive one (safe at shallow depth) on 500 random trees, including empty dicts:

import random
from nest import leaf_paths, leaf_paths_recursive

def random_tree(rng, depth):
    return {rng.choice("abcd") + str(i): (random_tree(rng, depth - 1) if depth and rng.random() < 0.5 else rng.randint(0, 9))
            for i in range(rng.randint(0, 4))}

rng = random.Random(7)
for _ in range(500):
    t = random_tree(rng, 5)
    assert list(leaf_paths(t)) == list(leaf_paths_recursive(t))
print("500 random trees: iterative and recursive versions agree")

500 random trees: iterative and recursive versions agree

Running the code

docker run --rm -v "$PWD":/w -w /w python:3.12 sh -c 'python nest.py; python nest_trace.py; python nest_test.py'

Save the listings as nest.py, nest_trace.py, nest_test.py in one folder. Python 3.12, standard library only.

The idea

Nested lists are a tree: a list is an inner node and an integer is a leaf. Flattening means visiting the leaves left to right. A generator (a function that uses yield to hand back one value at a time and pauses until asked for the next) fits because it produces each integer on demand, so the flat list is never built. The recursive version is natural: for every item, if it is a list, produce everything that list produces (yield from), otherwise yield the integer.

Approach

1. Walk the items in order.
2. A list item: delegate to a recursive call with yield from, which passes the inner generator's values straight out.
3. An integer item: yield it.
4. The iterative version replaces the call stack with your own stack, holding the iterators of the lists currently being walked.

Iterators and StopIteration, in four lines

The iterative version relies on Python's iterator protocol. iter(some_list) returns an iterator, an object that remembers its position in the list; each next(it) returns the following item, and when nothing is left next raises StopIteration, the signal that the sequence is finished. The explicit-stack code below catches that exception to learn that a list is exhausted:

numbers = [7, 8]
it = iter(numbers)          # an iterator remembers its position in the list
print(next(it))
print(next(it))
try:
    next(it)                # nothing left
except StopIteration:
    print("StopIteration: the iterator is exhausted")

Output:

7
8
StopIteration: the iterator is exhausted

The code

from typing import Iterator, List, Union

Nested = Union[int, List["Nested"]]   # a Nested value is an int or a list of Nested values (the type refers to itself)


def flatten(items: List[Nested]) -> Iterator[int]:
    """Recursive generator: yields integers lazily, left to right."""
    for item in items:
        if isinstance(item, list):
            yield from flatten(item)       # hand control to the inner generator
        else:
            yield item


def flatten_iterative(items: List[Nested]) -> Iterator[int]:
    """Same output with an explicit stack of list iterators instead of the call stack."""
    stack = [iter(items)]
    while stack:
        try:
            item = next(stack[-1])
        except StopIteration:
            stack.pop()                    # next() raised StopIteration: this list is exhausted, resume its parent
            continue
        if isinstance(item, list):
            stack.append(iter(item))       # go one level down
        else:
            yield item


data = [1, [2, [3, 4], 5], 6]
print(list(flatten(data)))
print(list(flatten_iterative(data)))

gen = flatten(data)
print(next(gen), next(gen))                # lazy: only two values have been produced so far

edge_cases = [[], [[]], [[], [[]], 7], [[[[1]]]], [0, [-5, [10 ** 20]]]]
for case in edge_cases:
    assert list(flatten(case)) == list(flatten_iterative(case))
    print(case, "->", list(flatten_iterative(case)))

deep = []
for _ in range(5000):
    deep = [deep, 1]                       # 5000 levels of nesting
print(sum(1 for _ in flatten_iterative(deep)))
try:
    sum(1 for _ in flatten(deep))
except RecursionError:
    print("recursive version: RecursionError")

Output:

[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
1 2
[] -> []
[[]] -> []
[[], [[]], 7] -> [7]
[[[[1]]]] -> [1]
[0, [-5, [100000000000000000000]]] -> [0, -5, 100000000000000000000]
5000
recursive version: RecursionError

next(gen) twice returns 1 and 2 and nothing else is computed, which shows the laziness. The 5,000-deep structure at the end, built by repeatedly wrapping, defeats the recursive version (it raises RecursionError, since each level of nesting adds generator frames to the call chain and the default limit is 1000) but not the explicit-stack one.

How the explicit stack works

The stack holds one iterator per open list. Look at the iterator on top: take its next item. If it is a list, push an iterator for it (descend). If it is an integer, yield it. When the top iterator is exhausted, pop it and carry on with its parent, which resumes exactly where it left off, because an iterator remembers its position. This is what the call stack did for you in the recursive version.

Worked trace of [1, [2, [3, 4], 5], 6]

def flatten_iterative_traced(items):
    stack = [iter(items)]
    while stack:
        try:
            item = next(stack[-1])
        except StopIteration:
            stack.pop()
            print(f"  list exhausted, pop -> stack depth {len(stack)}")
            continue
        if isinstance(item, list):
            stack.append(iter(item))
            print(f"  enter {item} -> stack depth {len(stack)}")
        else:
            print(f"  yield {item} (stack depth {len(stack)})")
            yield item


print(list(flatten_iterative_traced([1, [2, [3, 4], 5], 6])))

Output:

  yield 1 (stack depth 1)
  enter [2, [3, 4], 5] -> stack depth 2
  yield 2 (stack depth 2)
  enter [3, 4] -> stack depth 3
  yield 3 (stack depth 3)
  yield 4 (stack depth 3)
  list exhausted, pop -> stack depth 2
  yield 5 (stack depth 2)
  list exhausted, pop -> stack depth 1
  yield 6 (stack depth 1)
  list exhausted, pop -> stack depth 0
[1, 2, 3, 4, 5, 6]

Reading it: the stack depth rises to 3 inside [3, 4], shrinks as lists run out, and the values come out in order 1, 2, 3, 4, 5, 6.

Complexity

• Time: each element of the structure is visited once, so O(N) for N integers and lists in total. The iterative version does O(1) amortised work per element of the structure (each integer or list is pushed, yielded or popped once). That is an average over the whole run, not a promise about each value: the work between two yields can be as long as the nesting is deep, because every level has to be pushed or popped on the way. The listing below counts the loop steps for one integer wrapped in d nested lists, followed by a second integer.

def steps_between_values(depth):
    value = [1]
    for _ in range(depth):
        value = [value]
    stack = [iter([value, 2])]              # the integer 1 sits `depth` + 1 lists down, then comes 2
    steps = []
    while stack and len(steps) < 2:
        count = 0
        while True:
            count += 1
            try:
                item = next(stack[-1])
            except StopIteration:
                stack.pop()
                continue
            if isinstance(item, list):
                stack.append(iter(item))
            else:
                break
        steps.append(count)
    return steps


for depth in (100, 200, 400):
    print(depth, steps_between_values(depth))

Output:

100 [102, 102]
200 [202, 202]
400 [402, 402]

Each of the two values takes d + 2 steps, so the time between values grows with d even though the total work stays O(N).

• The recursive generator pays for depth on every value: a value yielded from depth d is passed up through d yield from levels, so asking for the next value resumes every paused generator on the way down to it. The explicit-stack version resumes one generator per value. The listing counts resumed generator frames per value (sys.setprofile reports a call event each time a paused generator is resumed), for 1000 integers wrapped in depth extra lists:

import sys


def flatten(items):
    for item in items:
        if isinstance(item, list):
            yield from flatten(item)
        else:
            yield item


def flatten_iterative(items):
    stack = [iter(items)]
    while stack:
        try:
            item = next(stack[-1])
        except StopIteration:
            stack.pop()
            continue
        if isinstance(item, list):
            stack.append(iter(item))
        else:
            yield item


def resumes_per_value(func, depth):
    data = list(range(1000))
    for _ in range(depth):
        data = [data]                       # 1000 integers, wrapped in `depth` extra lists
    resumes = 0

    def count_calls(frame, event, arg):
        nonlocal resumes
        if event == "call":                 # also fires each time a paused generator is resumed
            resumes += 1

    gen = func(data)
    next(gen)                               # first value: pay the descent once
    resumes = 0
    sys.setprofile(count_calls)
    for _ in gen:
        pass
    sys.setprofile(None)
    return resumes / 999


for depth in (1, 10, 100):
    print(depth, round(resumes_per_value(flatten, depth), 1), round(resumes_per_value(flatten_iterative, depth), 1))

Output:

1 2.0 1.0
10 11.0 1.0
100 101.1 1.0

The columns are the depth, the recursive version and the explicit-stack version. The recursive form resumes about depth + 1 frames per value and the stack form resumes 1. These counts are one CPython 3.12 measurement.

• Space: O(d) for nesting depth d in both forms (generator frames in one, iterators in the other). The flat list is never built, so memory does not grow with the number of integers.
• Recursion limit: the recursive form fails at roughly the default limit of 1000 nested levels (the 5,000-deep case above). The stack form has no recursion limit; its stack of iterators lives on the heap, and the 5,000-deep case above runs.

Edge cases and common mistakes

• Empty lists anywhere ([], [[]], [[], [[]], 7]) yield nothing for that part and must not stop the walk.
• Negative numbers, zero and very large integers pass through untouched ([0, [-5, [10**20]]]).
• Forgetting yield from and writing flatten(item) alone creates a generator and throws it away, so inner values vanish (on [1, [2, [3, 4], 5], 6] only 1 and 6 come out).
• Writing for x in flatten(item): yield x produces the same values but is wordier than yield from.
• Other iterables: strings are iterable and each character is itself a string, so an isinstance(item, Iterable) test would recurse until RecursionError on "a" (a one-character string yields itself as its only item); testing for list (or for a list/tuple pair) avoids that.
• Mutating the input while a generator is half-consumed changes what the rest of the iteration produces, because the generator reads the live list (appending 9 to [1, 2, 3] after taking the first value makes the remaining values [2, 3, 9]). Copy the input if that matters.

Follow-ups

• Return a flat list instead: list(flatten(x)), which uses O(N) extra memory, the cost the generator avoided.
• Support tuples and other sequences, or a depth limit parameter (flatten only k levels).
• A nested-iterator class with next() and has_next(): has_next() must answer yes or no without consuming a value, so the class runs the explicit-stack loop until it finds the next integer, stores it, and reports True; next() hands out the stored value and fetches the following one.

Running the code

Python 3.12, standard library only.
python3 flatten.py ; python3 flatten_trace.py ; python3 flatten_steps.py ; python3 flatten_resumes.py   (the main listing, the trace, the step counter and the resume counter; the four-line iterator snippet near the top runs on its own)