Рекурсия в Python 10 класс: примеры задач

Открой любую матрёшку: внутри — ещё одна, поменьше, и так до крошечной, которая дальше уже не открывается. Рекурсия — функция, устроенная точно так же: она решает большую задачу, сводя её к той же задаче поменьше, и вызывает себя снова, пока не доберётся до совсем простого случая. В математике это встречается постоянно: факториал числа определяется через факториал меньшего числа. А в программировании рекурсия — один из самых красивых инструментов: пять строк кода там, где цикл требует десятков. Сегодня разберём, как она работает внутри, почему без «стоп-крана» она падает и в каких задачах она блестит.

У любой рекурсивной функции две обязательные части. Базовый случай — ситуация, которая решается без вызова себя: это та самая крошечная матрёшка. Рекурсивный случай — шаг, где функция вызывает себя с уменьшенной задачей: задача приближается к базовой с каждым вызовом. Забудешь базовый случай — функция вызовет себя бесконечно, и программа рухнет с ошибкой переполнения стека. Сделаешь шаг неубывающим — эффект тот же. Поэтому написание рекурсии начинается не с кода, а с ответа на два вопроса: какой случай самый простой и как каждый шаг приближает к нему. Пока оба ответа не звучат в голове ясно, код писать рано: рекурсия без ясной схемы — это машина без тормозов.

Факториал: учебный пример с трассировкой

Факториал числа — произведение всех целых чисел от единицы до него: пять факториал — это пять на четыре на три на два на один. Классическое определение рекурсивно: факториал нуля равен единице — это базовый случай, а факториал числа больше нуля равен числу, умноженному на факториал числа минус один. В переводе на Python это три строки: функция с проверкой, если аргумент ноль или один, вернуть единицу, иначе вернуть аргумент, умноженный на вызов той же функции с аргументом минус один. Компактно и почти дословно повторяет математическую формулировку — в этом прелесть рекурсии: код читается как определение.

Трассировка показывает механику: вызовы складываются в стопку, как тарелки. Пока факториал четырёх ждёт результат от факториала трёх, тот ждёт от двойки — все они стоят в памяти незакрытыми. Эта стопка называется стеком вызовов: каждый вызов занимает место, и стек конечен. Базовый случай достаёт нижнюю тарелку, и ответы начинают подниматься наверх, каждый вызов умножает и возвращает. Глубина рекурсии — сколько вызовов уместилось в стеке: у факториала она равна числу, и для больших чисел стек переполняется, поэтому в Python глубину ограничивают настройкой по умолчанию в тысячу вызовов.

Числа Фибоначчи: красивый и опасный пример

Последовательность Фибоначчи начинается с единиц, а каждое следующее число — сумма двух предыдущих: один, один, два, три, пять, восемь, тринадцать. Рекурсивное определение идеально лаконично: базовые случаи — первые два, рекурсивный шаг — сумма двух вызовов для меньших номеров. Но у этой красоты есть цена: каждый вызов порождает два новых, те — по два, и дерево вызовов раздувается экспоненциально. Функция для сорокового числа Фибоначчи делает миллиарды вызовов и работает минутами, потому что одни и те же значения пересчитываются тысячи раз: факториал тридцати пяти посчитается мгновенно, а Фибоначчи тридцати пяти — нет.

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

Ханойские башни: где рекурсия раскрывается

Классическая головоломка Ханойские башни показывает рекурсию во всей красе. Есть три стержня и стопка дисков разного размера на первом; нужно перенести всё на третий, беря по одному диску и никогда не кладя большой на меньший. Человеческая попытка решить это «в лоб» тонет в ходах, а рекурсивное решение — три предложения: перенести все диски, кроме нижнего, на вспомогательный стержень; перенести нижний на цель; перенести стопку со вспомогательного на цель. Каждый пункт — та же задача меньшего размера, и функция вызывает себя дважды. Код в пять строк решает головоломку для любого числа дисков — и это честная демонстрация силы метода: рекурсивная структура задачи есть, и код её просто повторяет.

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

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

Рекурсия живёт и за пределами программ. Фрактальные снежинки и папоротники повторяют свой узор на каждом масштабе: маленькая часть формы устроена как целое — природа рисует рекурсией. Грамматики языков описывают предложения через вложенные предложения, а калькуляторы разбирают скобочные выражения рекурсивно: выражение в скобках — то же выражение, только меньше. Даже семейное дерево — рекурсивная структура: у каждого человека есть родители, у каждого родителя — свои. Так что навык видеть самоподобие в задаче — это ещё и способ читать мир: формы, языки и родства устроены одинаково на разных уровнях. А когда встретишь задачу с таким самоподобием — у тебя уже есть инструмент, который её съест.

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

Подсказка: клавиши J — следующая тема, K — предыдущая, на телефоне: свайп влево/вправо — соседняя тема