Введение. Примеры задач на рекурсию.

Идут Гоша, Тимофей и Алла по дороге.
Гоша: А всё-таки полезно разбираться в алгоритмах! Иногда без этого не решить задачу оптимальным способом.
Тимофей: Да, кроме того, алгоритмы — это очень интересно!
Алла: Тимофей, а какой твой любимый алгоритм?
Тимофей: Я бы не стал выделять любимый алгоритм, я бы остановился на любимом подходе. Мне очень нравится рекурсия.
Алла: А почему?
Тимофей: Пожалуй, главное преимущество этого метода — удобство реализации рекурсивных алгоритмов. Обычно код получается простым, кратким и интуитивно понятным.
Гоша: Да, помню, было у нас что-то такое в универе. Но очень сложным казалось.
Тимофей: Мало у кого получается быстро разобраться с рекурсией. Но только вы поймёте, как она работает, сразу начнёте экономить кучу времени и решать задачи удобным способом.
Гоша: Какие, например, задачи?
Представь, что хочешь найти определённый файл у себя в компьютере. Как это сделать без использования автоматического поиска?
Вот смотрите. Схема одного из вариантов решения этой задачи может выглядеть так:
image
Чтобы найти файл, нужно:
  1. Сложить все папки в корневом каталоге в очередь.
  2. Взять из очереди папку и посмотреть содержимое.
  3. Если обнаружили папку, добавить её в очередь.
  4. Если в ней хранится файл, перейти к следующему пункту.
  5. Если это искомый файл, поиск окончен.
  6. Если нет, пропустить файл.
  7. Повторить процедуру.
Существует другой вариант решения:
image
При использовании алгоритма, изображённого на схеме, нужно:
  1. Изучить содержимое папки.
  2. Если вы обнаружили папку, вернуться к шагу 1.
  3. Если нашли файл, проверить его.
  4. Если это искомый файл, поиск окончен.
  5. Иначе пропустить файл.
Попробуйте для тренировки написать код первого алгоритма и найти какой-нибудь файл у себя на компьютере.
Второй алгоритм — рекурсивный. Вот пример его реализации на Python:
Скопировать кодPYTHON
import os

file_to_find = 'some_file'
path = os.getcwd()

def look_for_file(path):
    for _object in os.listdir(path):
        if os.path.isdir(_object):
            look_for_file(_object)
        else:
            if _object == file_to_find:
                return _object

# Комментарии к используемым методам:

os.path.isdir(path) # True, если объект является папкой

os.path.isfile(path) # True, если объект является файлом

os.getcwd() # узнать текущую директорию

os.listdir(path) # получить содержимое папки
Тимофей: Обратите внимание: внутри функции look_for_file происходит вызов самой функции look_for_file. Это и есть рекурсия.
Если функция вызывает саму себя, рекурсия называется простой. Когда A вызывает функцию B, а функция B — функцию A, то рекурсия называется сложной.
image
Алла: Круто! Функция внутри функции! Как матрёшки.
Рассмотрим рекурсивную функцию, которая создаёт матрёшку размера size с n-1 матрёшкой внутри.
Скопировать кодPYTHON
def matryoshka_builder(size, n):
    if n >= 1:
        print("Создаём низ матрёшки размера {}.".format(size))
        matryoshka_builder(size - 1, n - 1)
        print("Создаем верх матрешки размера {}.".format(size))  
        print('Матрешка размера {} готова!'.format(size))
    else:
        return
Создадим матрёшку размера 4, внутри которой ещё 2 матрёшки. То есть всего будет 3 матрешки.
Скопировать кодPYTHON
matryoshka_builder(4, 3)

# Получим вывод:

Создаём низ матрёшки размера 4.
Создаём низ матрёшки размера 3.
Создаём низ матрёшки размера 2.
Создаём верх матрёшки размера 2.
Матрёшка размера 2 готова!
Создаём верх матрёшки размера 3.
Матрёшка размера 3 готова!
Создаём верх матрёшки размера 4.
Матрёшка размера 4 готова!
image
В функции matryoshka_builder с параметрами size = 4 и n = 3 создаётся низ матрёшки размера 4.
Затем вызывается matryoshka_builder с параметрами size = 3 и n = 2. В этом месте происходит рекурсивный вызов. Функция вызывает сама себя, но уже с другими параметрами.
Внутри функции с параметрами size = 3 и n = 2 после создания нижней части матрёшки размера 3 снова происходит рекурсивный вызов. Вызывается matryoshka_builder со значениями size = 2, n = 1.
При вызове функции создаётся низ матрёшки размера 2 и вновь рекурсивно вызывается функция matryoshka_builder. Но уже с параметрами size = 1 и n = 0.
При каждом вызове функции до этого условие n ≥ 1 выполнялось. Теперь параметр n равен нулю. Поэтому перемещаемся в ветку else. Там происходит возврат из функции в matryoshka_builder со значениями size = 2, n = 1. Создаётся верх матрешки размера 2 и выводится сообщение о том, что эта матрёшка готова.
Далее происходит возврат в matryoshka_builder с параметрами size = 3, n = 2. Создаётся верх матрёшки размера 3 и выводится сообщение о её готовности.
В конце возвращаемся в функцию matryoshka_builder со значениями параметров size = 4, n = 3. Эта функция вызывалась первой. Создаётся верх для самой большой матрёшки и выводится сообщение, что матрёшка готова.
После этого матрёшка полностью готова!
Тимофей: Вот так с помощью рекурсивной функции можно сделать матрёшку.
Алла: Здорово! Быстро и удобно.
Тимофей: Если говорить о быстроте, то рекурсия не ускоряет работу программы. Более того, алгоритмы, реализованные с применением циклов, часто исполняются быстрее. Зато рекурсия экономит время программиста. А код обычно получается понятный и компактный. Особенно часто рекурсию используют при работе с деревьями. Я расскажу об этом позже.
Решите задачи A - D: https://contest.yandex.ru/contest/18359/problems/A/ .