Рекурсия: функция, которая вызывает саму себя
Что будет, если функция позовёт сама себя? Не бесконечная катастрофа, а один из самых элегантных приёмов в программировании. Разбираемся, как рекурсия решает большие задачи, разбивая их на копии самих себя поменьше.
Представь книгу, на обложке которой нарисована эта же книга. А на той обложке — снова она, только меньше. И так до бесконечности. Звучит как фокус, но именно так работает один из самых красивых приёмов в программировании. Он называется рекурсия — это когда функция вызывает саму себя.
Матрёшка, которая объясняет всё
Самая честная аналогия рекурсии — это русская матрёшка. Ты открываешь большую куклу, а внутри — точно такая же, только поменьше. Открываешь её — снова кукла. И так пока не доберёшься до самой крошечной, которая уже не открывается.
Рекурсия в коде устроена ровно так же. У тебя есть задача, которую трудно решить целиком. Но её можно свести к такой же задаче, только поменьше. А ту — к ещё меньшей. И так до тех пор, пока не останется что-то совсем простое, ответ на что ты знаешь сразу.
Классический пример — посчитать факториал числа (это произведение всех чисел от 1 до данного: факториал пяти равен 5 × 4 × 3 × 2 × 1). Заметь хитрость: факториал пяти — это просто пять, умноженное на факториал четырёх. А факториал четырёх — это четыре, умноженное на факториал трёх. Большая задача растворяется в такой же задаче поменьше. Это и есть рекурсивное мышление.
Два правила, без которых всё рухнет
Чтобы рекурсия работала, а не зациклилась навсегда, у неё всегда есть две части. Запомни их — это сердце всего приёма.
- Базовый случай — момент, когда матрёшка перестаёт открываться. Это самый простой вариант задачи, на который функция отвечает сразу, не вызывая себя снова. Например: «факториал единицы равен единице». Точка.
- Рекурсивный случай — шаг, на котором функция вызывает саму себя, но с задачей поменьше, ближе к базовому случаю.
Если убрать базовый случай, получится катастрофа: функция будет звать себя бесконечно, как два зеркала, поставленные друг напротив друга. Коридор отражений без конца. Программа в этот момент не зависает молча — она упирается в предел и аварийно останавливается. Об этом пределе — дальше.
Рекурсия без базового случая — это лестница без последней ступеньки. Спускаешься, спускаешься, а дна всё нет.
Куда складываются вызовы: стек
Когда функция вызывает саму себя, старый вызов никуда не исчезает — он терпеливо ждёт. Представь стопку тарелок. Ты позвал функцию для числа пять — кладёшь тарелку. Внутри она зовёт себя для четырёх — кладёшь сверху ещё одну. Для трёх — ещё. Стопка растёт.
Эта стопка называется стеком вызовов. Каждый незаконченный вызов лежит в ней и помнит, на чём остановился. Как только мы добираемся до базового случая (тарелка для единицы), стопка начинает разбираться сверху вниз: каждый вызов получает ответ от того, кто лежал выше, домножает на своё число и отдаёт результат ниже. Сначала задача «разворачивается» вглубь, а потом «сворачивается» обратно с готовым ответом.
У стопки есть физический предел высоты. Память под стек ограничена, и если рекурсия уходит слишком глубоко (или не доходит до базового случая вовсе), стопка переполняется. Эту ошибку так и называют — переполнение стека, stack overflow. Да, тот самый сайт для программистов назван в её честь.
Где рекурсия живёт в реальном мире
Рекурсия — не просто учебный фокус. Она везде, где встречаются структуры, вложенные сами в себя.
- Папки на компьютере. Внутри папки лежат файлы и другие папки. Внутри тех — снова файлы и папки. Чтобы найти что-то во всех вложенных папках сразу, программа спускается рекурсивно, уровень за уровнем.
- Деревья. Меню сайта, генеалогическое древо, структура комментариев под постом — всё это деревья, у которых каждая ветка устроена как маленькое дерево. Рекурсия обходит их естественно.
- Фракталы. Снежинка, ветвление дерева, береговая линия — узоры, где маленький кусочек повторяет форму целого. Их рисуют рекурсивными алгоритмами.
Почти любую рекурсивную задачу можно переписать обычным циклом — и иногда это даже быстрее. Но есть случаи, где рекурсия читается настолько естественно, что цикл выглядел бы громоздким и запутанным. Хороший программист умеет выбирать инструмент под задачу.
Главное, что стоит унести с собой
Рекурсия пугает только на первый взгляд. На деле это всего лишь способ сказать: «Большую задачу я решу, если решу такую же, но поменьше». Добавь к этому правило «когда задача станет совсем крошечной — отвечу сразу», и весь механизм у тебя в руках.
Когда в следующий раз увидишь матрёшку, вложенные папки или зеркальный коридор — вспомни, что ты смотришь на рекурсию вживую. А потом попробуй написать функцию, которая считает факториал, позвав саму себя. Когда она впервые сработает, ты почувствуешь это особое удовольствие — будто понял фокус, который только что казался магией.