Рекурсия на простых примерах

Нужно узнать, сколько файлов лежит в папке «Школа», считая все вложенные. Внутри «Школы» есть «Информатика», в ней «Проекты», в ней «2026», в ней, возможно, ещё папки: как глубоко это уходит, заранее не известно. Цикл по содержимому «Школы» пересчитает то, что лежит прямо в ней, и остановится у каждой вложенной папки, не зная, что с ней делать.

Определение «рекурсия — это когда функция вызывает саму себя» читают многие и остаются при своём, потому что оно описывает приём, но не объясняет, откуда он берётся. Для большинства людей это первая тема, где код понятен построчно, а то, как он работает целиком, нет. Это нормально, и ниже путь расставлен так, чтобы к самой функции подойти последней: сперва задача, потом остановка, потом степень числа и только затем папки.

Что мешает циклу

Посмотрим, где именно застревает цикл. Папка «Школа» содержит файлы и другие папки. Файл считается без затей: плюс единица. Вложенная папка требует того же действия, что и сама «Школа»: посчитать файлы в ней, включая вложенные. То есть задача содержит в себе меньшую копию самой себя: число файлов в папке равно числу файлов, лежащих прямо в ней, плюс то же число для каждой вложенной папки.

Эта формулировка и есть рекурсивная идея. Она не говорит, сколько уровней вложенности будет, и ей это не нужно. В реальной работе с каталогами в Python для этого есть готовый os.walk, и пользоваться стоит им (о нём рассказано в статье про работу с файлами). Но идея нужна не только для папок: она же стоит за делением пополам при поиске, за разбором вложенных скобок и за многими задачами экзамена, поэтому её учат на таком материале.

Матрёшка и условие остановки

Папка слишком сложна для первого раза, и на её месте лучше матрёшка. Задача: узнать, сколько в ней кукол. Вы открываете самую большую. Внутри либо ещё одна, меньшего размера, либо ничего, потому что эта кукла цельная, последняя. Если внутри ничего, ответ один: перед вами одна кукла. Если внутри ещё одна, ответ равен единице плюс ответ для той, что внутри.

На Python матрёшку можно записать вложенными списками: цельная кукла — пустой список, а кукла с другой внутри — список из одного элемента, той самой внутренней куклы. Три куклы выглядят как [ [ [] ] ] (пробелы между скобками необязательны, они помогают глазу), и функцию подсчёта пишут одной строкой:

• def kukly(m): return 1 if m == [] else 1 + kukly(m[0])

Вызов kukly([ [ [] ] ]) вернёт 3. Условие после слова if проверяет, цельная ли кукла, и тогда ответ — единица; в остальных случаях функция открывает куклу, берёт то, что в ней (m[0]), и прибавляет единицу к ответу для неё.

Здесь видно устройство любой рекурсии из двух частей. Первая часть — остановка: случай, ответ на который известен без дальнейших вычислений (цельная кукла, значит, одна). Вторая — шаг: сведение задачи к такой же, но меньшей (кукла плюс ответ для вложенной). Если остановки нет, задача никогда не закончится: вы будете открывать куклу за куклой в воображаемой матрёшке без дна.

Остановку стоит записывать первой. Когда шаг написан раньше, остановка часто теряется, и функция работает на всех примерах, кроме последнего. Сначала спрашивайте себя, на каком самом маленьком случае ответ очевиден, и только потом, как к нему идти.

Степень числа: та же идея в одной строке

Теперь то же самое с числами. Задача: возвести x в степень n, не пользуясь готовым оператором. Самый маленький случай: любое число в нулевой степени равно единице. Шаг: x в степени n равно x, умноженному на x в степени n минус один. Записывается это так (знак умножения в строке — звёздочка):

• def power(x, n): return 1 if n == 0 else x * power(x, n - 1)

Вызов power(2, 3) вернёт 8. Что происходит внутри, лучше выписать на бумаге, и порядок записи называется трассировкой. Сначала спуск: функция вызывает сама себя, пока не дойдёт до остановки.

• power(2, 3) ждёт ответа от power(2, 2)
• power(2, 2) ждёт ответа от power(2, 1)
• power(2, 1) ждёт ответа от power(2, 0)
• power(2, 0) возвращает 1: остановка

У каждого из этих четырёх вызовов своя переменная n: в первом три, во втором два, в третьем один, в четвёртом нуль. Они не мешают друг другу, потому что переменные функции живут внутри вызова (подробнее об этом сказано в статье про функции и аргументы), и ответ возвращается по цепочке, ничего не теряя. Теперь подъём, в обратном порядке: power(2, 1) получает 1 и возвращает 2 умножить на 1, то есть 2; power(2, 2) получает 2 и возвращает 4; power(2, 3) получает 4 и возвращает 8. Ни один из вызовов не заканчивается раньше, чем закончится тот, что глубже: это вся хитрость, и именно она не видна в тексте функции, пока не выпишешь спуск на бумаге.

Чем рекурсия ломается

Поломок три. Две первые стоит увидеть до того, как они случатся сами.

Первая — забыта остановка:

• def power(x, n): return x * power(x, n - 1)

Функция вызывает сама себя бесконечно, и в какой-то момент Python прерывает её с сообщением «maximum recursion depth exceeded»: по умолчанию он разрешает порядка тысячи вложенных вызовов, а потом сдаётся. Это самое понятное из возможных сообщений, потому что говорит прямо: спуск не закончился.

Вторая коварнее: остановка есть, но шаг не приближается к ней. Функция вызывает power(x, n + 1), а остановка ждёт нуля. Условие остановки существует, и функция всё равно не закончит, потому что каждый вызов уводит от него. Проверка одна: после шага аргумент должен стать ближе к тому случаю, который останавливает рекурсию. Если по трассировке видно, что n растёт, а ждёт нуля, ошибка найдена.

Третья поломка бьёт по времени, ответ остаётся верным: функция вызывает сама себя дважды, и один и тот же случай считается заново много раз. Классический пример — числа Фибоначчи, где каждое число равно сумме двух предыдущих: запись def fib(n): return n if n < 2 else fib(n - 1) + fib(n - 2) верна и для десяти даёт 55 мгновенно, но на тридцати ответ ещё приходит мгновенно, к сорока ожидание становится заметным, а дальше растёт в разы с каждым шагом (замерьте сами, как показано в статье про сортировки и поиск); причина в том, что каждый из двух вызовов заново вычисляет то, что другой уже вычислил. Лечат это запоминанием результатов или циклом. Когда рекурсивную функцию приходится только читать, полезно помнить, что число вызовов способно расти намного быстрее самого аргумента.

Папки, теперь с кодом

Вернёмся к исходной задаче. Чтобы не трогать диск, папку удобно изобразить списком: строка в нём — файл, вложенный список — вложенная папка. Учебный каталог:

• papka = ["a.txt", ["b.txt", "c.txt", ["d.txt"]], []]

В корне лежит файл a.txt и вложенная папка, в ней два файла и ещё одна папка с одним файлом, а потом пустая папка. Всего четыре файла. Функция, которая их считает:

• def count(papka): return sum(1 if isinstance(x, str) else count(x) for x in papka)

Читается так: для каждого элемента папки, если это строка (файл), прибавить единицу, а если нет (вложенная папка), прибавить результат той же функции для неё. Остановка здесь спрятана: пустая папка даёт сумму нуль, и дальше спускаться не во что. Вызов count(papka) вернёт 4, и глубина вложенности не имеет значения, пока не превысит тот самый предел в тысячу вызовов.

Всё это можно написать циклом со стеком, который вы заведёте и будете вести сами, и на Python такой вариант часто надёжнее. Но рекурсивная запись короче и описывает задачу точнее: ровно так мы её и сформулировали в самом начале.

Как научиться читать рекурсию

Единственный способ, который работает у всех, — трассировка вручную, с бумагой и карандашом. Прочитанная глазами рекурсия понятна лишь до тех пор, пока функция проста, а при первой же сложной вы теряете, на каком уровне находитесь. Выписывайте спуск столбиком, как выше, и подъём тоже. Один пример на бумаге объясняет больше, чем десяток разобранных в уме.

Перед запуском чужой рекурсивной функции найдите глазами две строки: ту, на которой всё заканчивается, и ту, где аргумент меняется. Если первая не находится, функция не остановится; если вторая ведёт не к первой, ответ будет не тем, на который вы рассчитывали. В обоих случаях сообщение интерпретатора мало что объяснит, а трассировка на бумаге покажет сразу.

В видеокомнате нет ни показа экрана, ни общей доски, поэтому в чат уходит трассировка: спуск и подъём, переписанные текстом. Репетитору проще указать, на каком вызове вы потеряли нить, чем объяснять рекурсию заново.

В экзамене по информатике есть задание, где дана готовая рекурсивная функция, и по ней нужно найти значения. Здесь трассировка единственный надёжный инструмент: подробности — в статье про задание 16 ЕГЭ по информатике, а где оно стоит среди других заданий, показывает карта первой части. Устройство всей работы описано в обзоре структуры экзамена. Деление пополам из статьи про сортировки и поиск читается тем же способом: остановка — «элемент найден или список пуст», шаг — «половина списка»; и тема в целом входит в порядок курса из общей статьи про информатику.

Начать поиск:

• репетиторы по информатике по всем направлениям
• репетиторы по информатике для подготовки к ЕГЭ
• репетиторы по информатике с пробным занятием
• репетиторы по информатике для олимпиад

Вопросы и ответы

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

Почему Python останавливает рекурсию после тысячи вызовов? Каждый вызов занимает место в памяти до тех пор, пока не вернётся, и бесконечный спуск исчерпал бы её. Предел защищает программу от зависания. Если нужно спуститься глубже, берут цикл, а предел оставляют как есть.

Что делать, если рекурсия не даётся по тексту? Выписать на бумаге вызов с самым маленьким аргументом (степень с n, равным нулю), потом с n, равным единице, потом двойке. Три случая подряд обычно хватает, чтобы увидеть закономерность, и к сложной функции нужно подходить только после этого.