Как рекурсивно обойти вложенный список произвольной глубины

Задача на рекурсию: обойти вложенный список произвольной глубины

Для обхода вложенного списка произвольной глубины используют рекурсию: если элемент — список, функция вызывает себя для него; если элемент обычный, добавляет его в результат. Такое решение посещает каждый элемент один раз и работает за O(n).

Подробный ответ

Условие задачи

Нужно получить плоский список из вложенной структуры, глубина которой заранее неизвестна.

items = [1, [2, [3, 4], 5], [6, [7]]]
# Ожидаемый результат: [1, 2, 3, 4, 5, 6, 7]

Рекурсивное решение

def flatten(items: list) -> list:
    result = []

    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)

    return result

Пример

items = [1, [2, [3, 4], 5], [6, [7]]]
print(flatten(items))
# [1, 2, 3, 4, 5, 6, 7]

Вариант с передачей результата

Этот вариант избегает создания промежуточных списков на каждом уровне рекурсии.

def flatten(items: list) -> list:
    result = []

    def visit(current_items: list) -> None:
        for item in current_items:
            if isinstance(item, list):
                visit(item)
            else:
                result.append(item)

    visit(items)
    return result

Итеративный вариант

Если глубина вложенности может быть очень большой, рекурсивный вариант способен достигнуть лимита глубины Python. Тогда можно использовать явный стек.

def flatten_iterative(items: list) -> list:
    result = []
    stack = list(reversed(items))

    while stack:
        item = stack.pop()

        if isinstance(item, list):
            stack.extend(reversed(item))
        else:
            result.append(item)

    return result

Сложность

Каждый элемент посещается один раз, поэтому время равно O(n). Дополнительная память зависит от результата и глубины вложенности: рекурсивный стек в худшем случае может занимать O(d), где d — глубина.

Как ответить на собеседовании

Проверяю тип каждого элемента: если это список, рекурсивно обхожу его, иначе добавляю значение в результат. Каждый элемент посещается один раз, поэтому время O(n). Если вложенность может быть очень глубокой, заменяю рекурсию явным стеком, чтобы избежать RecursionError.