Введение в Python. Часть 12. Рекурсия

В этом уроке «Мастерской» мы поговорим о рекурсии. Это такой прием в программировании, когда функция вызывает саму себя.

Для того, чтобы рекурсия работала, нужно решить две задачи. Во-первых, нужно найти базовый случай, то есть тот случай, когда функция завершает свою работу. Во-вторых, нужно разбить нашу проблему, которую мы хотим решить с помощью рекурсии, на множество мелких подпроблем; и если мы сможем найти решение для подпроблемы, значит мы решили всю задачу.

Задача 1 

Давайте попробуем разобрать рекурсию на каком-то очень простом примере. Скажем, у нас есть строка и мы хотим напечатать все ее буквы. Для этого нам потребуется такая функция:

Давайте разберем каждую строчку кода, чтобы лучше понять, что происходит. Сначала нам нужно определиться с базовым случаем. И для этой задачи функция должна завершить свою работу, когда ей передадут пустую строку. Логично: если нет букв, значит нечего печатать. И этот базовый случай мы описываем в этой сточке кода: if not text: return. Обратите внимание, что мы используем ключевое слово return, но ничего при этом не возвращаем, — это просто команда «Выходи» для функции. 

Дальше нам нужно разбить нашу задачу на мелкие подзадачи. В нашем случае задача распечатать все буквы строки и так проста, но магия рекурсии заключается в том, что даже самую простую задачу можно разбить на еще более простую подзадачу. Какой она может быть?

Если мы хотим понять, как распечатать все буквы строки, то нам достаточно понять, как распечатать первую букву строки. И все! Для этого мы берем первую букву строки и печатаем ее: 

first_letter = text[0]   

print(first_letter) 

А далее включаем магию рекурсии: возвращаем нашу же функцию, но уже без первой буквы, потому что для мы решили задачу: recurs_print(text[1:])

Задача 2

Чтобы углубить наше понимание рекурсии, попробуем решить чуть более сложную задачу. Но ее решение во многом будет похожим на решение предыдущей проблемы. Задача: вернуть четные числа из списка. 

Для начала определимся с базовым случаем. Он — такой же, как и в предыдущей задаче: если список пустой, завершай работу. 

Теперь разобьем нашу проблему на подпроблемы. И снова все очень похоже на задачу с распечатыванием букв. Чтобы проверить все числа из списка, нужно всего лишь проверить первое число. Для этого мы пишем: 

first_element = num_list[0]

if first_element % 2 == 0: 

    result.append(first_element)

Обратите внимание, что в данному случае мы передаем result в качестве параметра функции. Если бы мы это сделали внутри функции, то присваивание пустого списка имени result повторялось бы при каждом вызове функции. Таким образом, мы бы в конце получали пустой список. Но если мы используем result в качестве параметра, то его значение не будет перевычисляться на каждом вызове. 

И в конце снова используем магию рекурсии: функция вызывает саму себя, но уже без первого элемента, для которого мы проверили условие выше. 

Задача 3

На этом этапе мог возникнуть вопрос: зачем решать простые задачи более изощренным способом? И ответить на этот вопрос нам поможет следующая проблема. Огромное количество открытых данных хранится в интернете в формате json. Грубо говоря, это «питоновский» словарь, в котором есть ключи и значения. Эти словари, как правило, имеют вложенные словари и списки, которые в свою очередь тоже могут содержать вложенные словари. И часто возникает необходимость найти какое-то значение в такой сложной структуре данных. А из-за того, что редкий сервис в интернете (особенно государственный) выдает данные в чистом виде, приходится писать громоздкий код со множеством условий и исключений для по сути очень простой задачи — поиска значения по ключу. 

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

Итак, для начала определимся с базовым случаем. Он простой: если ключ есть в словаре, верни его значение: if key in obj: return obj[key]

В противном случае нам нужно с помощью цикла for пройтись по всем ключам и значениям словаря, чтобы понять, есть ли среди значений вложенные словари. И если объект — вложенный словарь, то мы используем магию рекурсии: вызываем нашу же функцию и передаем ей в качестве параметра объект. 

Следующая строчка кода (if result is not None) важна, потому, когда наша функция проверяет базовый случай и не находит сразу значение по ключу, она возвращает None. Чтобы этого не случилось, нам и нужно «приказать» ей вернуть значение, если оно на равно None. 

И мы можем проверить работу нашей функции на примере сокращенной выгрузки государственного контракта из сервиса «Госзакупки». К примеру, мы хотим распечатать значение ключа date, которое находится во вложенном словаре. Для этого нам всего лишь нужно написать одну строчку кода: recurs_find_key('date', data)