Выпрямление списков при помощи рекурсии

Описание задачи

Программа принимает на вход список, состоящий из других списков, и возвращает обычный список, в котором присутствуют все элементы из вложенных списков. Эта операция производится при помощи рекурсии.

Решение задачи

  1. Инициализируем переменную списком, в котором содержатся вложенные списки.
  2. Передаем этот список в рекурсивную функцию для преобразования в обычный список.
  3. Базовым условием рекурсии будет равенство входящего списка пустому списку. В этом случае возвращается пустой список и дальнейшие вызовы рекурсивной функции не осуществляются.
  4. В противном случае проверяется, является ли элемент списка вложенным списком или обычным элементом списка.
  5. Если элемент списка тоже список, то он целиком передается нашей рекурсивной функции в качестве аргумента и к этому прибавляется остальная часть основного списка, которую мы также передаем в функцию в качестве аргумента.
  6. Если же элемент списка обычное число, то оно выводится в результат в виде списка из одного элемента и к нему прибавляется рекурсивная функция, в которой в качестве аргумента остальная часть списка. Таким образом, мы можем «распрямить» списки со сколь угодно глубокими вложениями.
  7. После окончания работы функции выпрямленный список выводится на печать.
  8. Конец.

Исходный код

Ниже дан исходный код, который осуществляет выпрямление списка с использованием рекурсии. Результаты работы программы также даны ниже.

def flatten(s):
    if s == []:
        return s
    if isinstance(s[0], list):
        return(flatten(s[0]) + flatten(s[1:]))
    return(s[:1] + flatten(s[1:]))
s = [[1, 2], [3, 4]]
print("Выпрямленный список: ", flatten(s))

Объяснение работы программы

  1. Инициализируем переменную s списком, в котором содержатся вложенные списки.
  2. Передаем этот список в рекурсивную функцию flatten() для преобразования в обычный список.
  3. Базовым условием рекурсии будет равенство входящего списка пустому списку. В этом случае возвращается пустой список и дальнейшие вызовы рекурсивной функции не осуществляются.
  4. В противном случае проверяется, является ли первый элемент списка вложенным списком или обычным элементом списка. Проверка осуществляется при помощи функции isinstance(s[0], list).
  5. Если элемент списка тоже список, то он целиком передается нашей рекурсивной функции в качестве аргумента и к этому прибавляется остальная часть основного списка, которую мы также передаем в функцию в качестве аргумента. А именно: flatten(s[0]) + flatten(s[1:].
  6. Если же элемент списка обычное число, то он выводится в результат в виде списка из одного элемента и к нему прибавляется рекурсивная функция, в которой в качестве аргумента остальная часть списка. А именно: s[:1] + flatten(s[1:]. Таким образом мы можем «распрямить» списки со сколь угодно глубокими вложениями.
  7. После окончания работы функции выпрямленный список выводится на печать.
  8. Конец.

Результаты работы программы

Пример 1:
Выпрямленный список:  [1, 2, 3, 4]