Рекурсия. Какие эмоции вызывает у вас это слово? Страх? Восторг? Тут возможны варианты. Но, честно говоря, рекурсия это просто еще один способ решения итеративных задач.
В наших циклах for мы выполняем какое-то действие Х десять раз. А в рекурсии Х — это повторный вызов того же метода. И вместо того чтобы вызывать его десять раз, мы вызываем его до тех пор, пока не будет соблюдено какое-то условие. Что это может быть за условие? Его мы определяем сами.
Давайте разберем это на примере решения задачи с собеседования.
Трамплин для прыжков в воду должен быть определенной длины и сделан из определенного числа досок. Имея список чисел (каждое число - длина какой-нибудь доски) и число k, определите, можно ли из любых двух чисел из списка составить число k. Например, если дан список [10, 15, 3, 7] и k = 17, нужно вернуть True, потому что 10 + 7 равно 17.
Для начала давайте подумаем, как нам решить эту задачу итеративно. Придумаем брутфорс-решение, так сказать.
Мы можем просто создать вложенный цикл for, в котором будем складывать каждое число списка с каждым из остальных чисел в списке, проверяя, равна ли их сумма k.
Начнем с создания метода add_to_k(), принимающего два параметра: наш список numbers и сумму k.
def add_to_k(numbers, k):
pass
В первом цикле for мы будем перебирать индексы в диапазоне от 0 до длины списка, уменьшенной на единицу. Мы вычитаем единицу, чтобы впоследствии не захватывать последний элемент списка: за ним уже ничего нет, так что не будет, с чем его сравнивать.
def add_to_k(numbers, k):
for i in range(len(numbers) - 1):
...
Внутри цикла мы возьмем первый выбранный элемент и поместим его в переменную current. После этого нам нужно пересмотреть все числа в списке, идущие за этим элементом. Тут нам поможет вложенный цикл for.
def add_to_k(numbers, k):
for i in range(len(numbers) - 1):
current = numbers[i]
for j in range(i + 1, len(numbers)):
...
Наконец, если сумма двух чисел равна k, мы вернем True. Если мы переберем весь список и не найдем подходящих слагаемых, дающих в сумме k, мы вернем False (вне цикла). Все вместе выглядит следующим образом:
def add_to_k(numbers, k):
for i in range(len(numbers) - 1):
current = numbers[i]
for j in range(i + 1, len(numbers)):
# print("checking", current, "+", numbers[j])
if current + numbers[j] == k:
return True
return False
Давайте попробуем запустить это решение.
num_list = [10, 15, 3, 7] k = 10 print(add_to_k(num_list, k)) # -> True
Отлично. Задача решена, но можно ли сделать то же самое рекурсивно?
Рекурсивный поиск
Начинаем писать метод точно так же. Он будет принимать параметры numbers и k.
def add_to_k_recursive(numbers, k):
pass
Далее нам нужно определить наш базовый случай (или случаи). Когда имеешь дело с рекурсией, нужно спросить себя: «Каким будет простейший случай?» Подключите своего внутреннего ленивого программиста. Если бы вам нужно было решить эту задачу, имея возможность выбрать список, какой бы вы выбрали?
Вероятно, это был бы список со всего одним элементом: в этом случае ответ точно был бы False. Это и будет наш первый базовый случай. Поставим длину списка меньше 2: таким образом пустые списки тоже попадут в эту категорию.
def add_to_k_recursive(numbers, k):
if (len(numbers) < 2):
return False
Что дальше? Нам нужно прописать еще один базовый случай. Если список должен содержать как минимум два элемента, самым простым вариантом будет список, содержащий ровно два элемента! В таком случае мы сможем просто сложить эти два числа и проверить, равна ли их сумма k. Поскольку длина списка нам не известна, давайте будем просто складывать первый и последний элемент списка.
def add_to_k_recursive(numbers, k):
if (len(numbers) < 2):
return False
elif numbers[0] + numbers[-1] == k:
return True
Теперь нам остается только прописать наш рекурсивный случай, т. е. тот, где мы заново вызываем наш метод.
Давайте подумаем. Наш список — [10, 15, 3, 7] и мы ищем числа, в сумме дающие 10.
Очевидно, что длина списка больше 2, так что мы пропускаем первое условие if. В elif мы видим, что первый и последний элементы в сумме дают 17, что не равно 10. И что теперь?
Нам нужно вызвать метод add_to_k_recursive() для меньшего списка, в котором первый и последний элементы будут другими. Мы можем проверить два варианта меньшего списка:
- Все те же числа, за исключением первого значения.
- Все те же числа, за исключением последнего значения.
На Python это выглядит следующим образом (см. срезы):
numbers[1:] numbers[:-1]
Таким образом, мы будем вызывать наш метод дважды, по разу для каждого из двух меньших списков. Что мы будем возвращать? Припомните, что в Python при помощи or можно вернуть первое истинное значение. Мы вернем один вызов метода или другой.
def add_to_k_recursive(numbers, k):
if (len(numbers) < 2):
return False
elif numbers[0] + numbers[-1] == k:
return True
else:
return add_to_k_recursive(numbers[:-1], k) or add_to_k_recursive(numbers[1:],
Проверяем
Запустим тот же код, что и раньше. Мы должны получить тот же результат — True.
num_list = [10, 15, 3, 7] k = 10 print(add_to_k_recursive(num_list, k))
Давайте посмотрим, что происходит под капотом.
Мы начинаем со списка [10, 15, 3, 7]. Как уже говорилось, первый и последний элементы в сумме не дают 10. Поэтому мы вызываем функцию снова для меньших списков, [10, 15, 3] и [15, 3, 7].
Каждый из этих списков снова разбивается надвое. Второй список разделится на [15, 3] и [3, 7]. Вызов нашего метода для последнего из этих списков вернет True. Таким образом True будет возвращаться по цепочке вверх до начального экземпляра метода.
Надеемся, это помогло вам приблизиться к пониманию рекурсии. Ее применение в данном случае ничуть не улучшило временную сложность решения. Нам все равно приходится просматривать каждое число дважды (примерно), а это O(N2). Но вы можете найти это решение более элегантным. К тому же, уметь применять рекурсию — совсем не плохо, особенно, когда в задаче на собеседовании нужно проверить «все возможные комбинации».
