Practice: Flattening a Nested List of Numbers

A list may hold numbers or more lists; return every number in order.

Flattening a nested list, a list whose items are numbers or further lists, means returning all its numbers in one plain list, in the order they appear. This card covers that task as an exercise in writing a recursive function, tracing it, and deciding when a loop should replace it, with an answer to check yours against.

The input is [1, [2, [3, 4]], [], 5], and the answer is [1, 2, 3, 4, 5].

Write flatten(items) recursively. Name its base case, the input it answers without calling itself; the smaller input each call passes on; and how the answers are combined.
Trace it on the input: list every call in the order it is made, and what each returns.
Say when the recursive version would fail, and write a version that uses a loop and a stack of your own, keeping the numbers in order.

An answer: the recursive function, its trace, and a loop with an explicit stack

The smaller input is each item that is itself a list, and the combine step appends a number as it is or extends the result with the flattened inner list. The base case is a list with no lists inside it: the loop appends its numbers, makes no call, and returns. The empty list is the smallest case of all, and returns an empty result.

The trace, indented by depth as an instrumented run printed it, shows each inner list flattened and returned before the list around it carries on:

text

call flatten([1, [2, [3, 4]], [], 5])
  call flatten([2, [3, 4]])
    call flatten([3, 4])
    flatten([3, 4]) returns [3, 4]
  flatten([2, [3, 4]]) returns [2, 3, 4]
  call flatten([])
  flatten([]) returns []
flatten([1, [2, [3, 4]], [], 5]) returns [1, 2, 3, 4, 5]

The depth of the calls equals the depth of the nesting, so a list nested a few thousand levels deep exceeds Python's default limit of 1000 frames. The loop version keeps a list of items still to look at. It pushes each list's items in reverse, so that the first item is on top and comes off first, and the numbers stay in order. The listing ran both versions on the input and on a list nested 5,000 levels deep around a single 7.

flatten.pypy

def flatten(items):
    numbers = []
    for item in items:
        if isinstance(item, list):
            numbers.extend(flatten(item))
        else:
            numbers.append(item)
    return numbers


def flatten_with_stack(items):
    numbers = []
    pending = list(reversed(items))
    while pending:
        item = pending.pop()
        if isinstance(item, list):
            pending.extend(reversed(item))
        else:
            numbers.append(item)
    return numbers


nested = [1, [2, [3, 4]], [], 5]
print(flatten(nested))
print(flatten_with_stack(nested))

deep = [7]
for _ in range(5_000):
    deep = [deep]
try:
    print(flatten(deep))
except RecursionError as error:
    print("flatten(deep) raised", type(error).__name__)
print("flatten_with_stack(deep)", flatten_with_stack(deep))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
flatten(deep) raised RecursionError
flatten_with_stack(deep) [7]

Both versions return [1, 2, 3, 4, 5] on the input. On the deep list, the recursive version raised RecursionError and the loop returned [7]. Keep the recursive version where nesting is shallow, as in most data a person types; switch to the loop when the input comes from a program or a file that can nest without bound.

← → move through sections and cards