1. Знакомство с рекурсией в реальной жизни
Рекурсия кажется абстрактной идеей, но на самом деле мы сталкиваемся с ней постоянно — просто не называем её этим словом.
Представьте задачу: скопировать папку на компьютере. Внутри папки могут лежать файлы и другие папки. А внутри этих папок — ещё папки и файлы. Если описать алгоритм словами, он получится очень простым:
- Скопировать все файлы в текущей папке.
- Для каждой вложенной папки — скопировать её тем же способом.
То есть программа делает одно и то же действие на каждом уровне:
Documents
├─ report.pdf
├─ photo.jpg
└─ Projects
├─ code.swift
└─ Archive
└─ old.txt
Алгоритм выглядит примерно так:
copyDirectory("Documents")
├─ copy file: report.pdf
├─ copy file: photo.jpg
└─ copyDirectory("Projects")
├─ copy file: code.swift
└─ copyDirectory("Archive")
└─ copy file: old.txt
Каждая вложенная папка обрабатывается точно так же, как и основная. Именно такая структура задач и приводит нас к рекурсии.
Похожие ситуации встречаются и в других местах:
- обход файловой системы
- ветки комментариев на форумах
- меню с вложенными разделами
- структуры вроде «деревьев»
Во всех этих случаях объект может содержать другие объекты того же типа, и алгоритм обработки повторяется на каждом уровне.
2. Что такое рекурсия
В программировании рекурсия означает, что функция решает задачу, вызывая саму себя.
Но если остановиться только на этой фразе, можно легко написать функцию, которая будет вызывать себя бесконечно. Поэтому правильнее думать о рекурсии не как о «самовызове», а как о способе разбить задачу на более простые части.
Любая корректная рекурсивная функция состоит из двух элементов.
Базовый случай — момент, когда рекурсивные вызовы прекращаются. Это самая простая ситуация, которую можно решить сразу.
Рекурсивный шаг — правило, по которому задача уменьшается и передаётся следующему вызову функции.
Если вернуться к примеру с копированием папки, эти элементы выглядят так:
- базовый случай — в папке нет вложенных папок, остаётся только скопировать файлы;
- рекурсивный шаг — для каждой вложенной папки запустить тот же алгоритм копирования.
Получается простая схема:
задача
↓
уменьшаем задачу
↓
уменьшаем ещё
↓
базовый случай
После того как достигнут базовый случай, выполнение начинает «разворачиваться назад», и каждый уровень функции завершает свою работу. Именно поэтому рекурсия хорошо подходит для задач со вложенной или древовидной структурой: файловые системы, комментарии, каталоги, деревья данных.
В следующих разделах мы посмотрим, как эта идея превращается в код и как устроен каркас рекурсивной функции.
Каркас рекурсивной функции: базовый случай и шаг
В рекурсии есть железное правило, почти как «не трогай ! без причины»: в каждой рекурсивной функции должен существовать достижимый базовый случай. Это не рекомендация, а условие выживания программы (и вашего сна). Базовый случай — это ситуация, когда функция больше не вызывает себя и сразу возвращает результат или завершает работу.
Рекурсивный шаг — это то, как мы переходим к меньшей задаче. Важно, чтобы «меньшая» была реально меньше: вход должен двигаться в сторону базового случая. Если вы «уменьшаете» вход так, что он остаётся тем же самым — вы строите вечный двигатель (а компилятор не обязан спасать человечество от вечных двигателей).
Очень полезно держать мини-шаблон в голове:
| Часть | Что это | Как выглядит в коде |
|---|---|---|
| Базовый случай | Остановка | |
| Шаг | Уменьшаем вход | |
| Сборка результата | (Иногда) объединяем | |
Заметьте важную деталь: сборка результата бывает не всегда. Если рекурсия «с эффектом» (например, только печатает), то она может ничего не возвращать.
3. Примеры рекурсии: эффект, стек и возврат значения
Рекурсия с эффектом: countdown и «путь вниз»
С рекурсией легче всего начать не с математики, а с чего-то очень конкретного: «печатай числа, уменьшаясь». Это полезно, потому что вы сразу видите порядок выполнения и не запутываетесь в возвратах.
Давайте напишем функцию countdown(from:), которая печатает числа от n до 1, а затем печатает "Go!". Здесь базовый случай — когда n <= 0. Рекурсивный шаг — вызов с n - 1.
import Foundation
func countdown(from n: Int) {
if n <= 0 {
print("Go!")
return
}
print(n) // например: 3 потом 2 потом 1
countdown(from: n - 1)
}
countdown(from: 3)
Здесь важная мысль: всё, что написано до рекурсивного вызова, выполняется «на пути вниз». То есть мы печатаем 3, потом вызываем функцию для 2, потом печатаем 2, вызываем для 1… и так далее.
Если вы мысленно представите лестницу, то мы идём вниз по ступенькам, печатая число на каждой ступеньке, пока не дойдём до пола (n <= 0).
Стек вызовов: почему «продолжение» ждёт возврата
Когда рекурсивная функция вызывает себя, кажется, будто она «переходит» в себя же. На самом деле она делает более скучную, но важную вещь: она останавливается и ждёт, пока не завершится следующий вызов. Это и есть причина, почему нам нужен базовый случай: иначе ждать придётся вечно.
Эту «очередь ожиданий» удобно представлять как стопку листов на столе (stack). Каждый вызов кладёт сверху новый лист «что делать дальше», а когда нижний лист заканчивается (базовый случай), мы начинаем снимать листы обратно и продолжать выполнение.
Чтобы увидеть это прямо глазами, напишем функцию trace(_:), которая печатает вход и выход. Это один из самых полезных учебных примеров: он показывает, что рекурсивная функция выполняется в двух направлениях — вниз и вверх.
import Foundation
func trace(_ n: Int) {
print("enter \(n)") // enter 2, enter 1, enter 0
if n > 0 {
trace(n - 1)
}
print("exit \(n)") // exit 0, exit 1, exit 2
}
trace(2)
Если запустить trace(2), вы увидите, что "enter" идёт в порядке 2, 1, 0, а "exit" — в обратном порядке 0, 1, 2. Это и есть «разворачивание» стека.
Можно даже нарисовать это в виде небольшой схемы:
flowchart TD
A["trace(2) печатает enter 2"] --> B["trace(1) печатает enter 1"]
B --> C["trace(0) печатает enter 0"]
C --> D["trace(0) печатает exit 0 и возвращается"]
D --> E["trace(1) печатает exit 1 и возвращается"]
E --> F["trace(2) печатает exit 2 и возвращается"]
Главная практическая польза этого понимания: в рекурсии всегда задавайте себе вопрос — что я делаю до вызова и что я делаю после него. Это почти всегда ключ к чтению кода.
Рекурсия с возвратом: sumTo и «сборка наверх»
Теперь перейдём к рекурсии, которая не только что-то делает, но и возвращает значение. Здесь появляется третий элемент каркаса: «сборка результата». Обычно она выглядит как «текущая часть + результат подзадачи».
Пример — сумма чисел от 1 до n. Мы хотим написать sumTo(3) == 6, потому что 3 + 2 + 1.
import Foundation
func sumTo(_ n: Int) -> Int {
if n <= 0 { return 0 } // базовый случай
return n + sumTo(n - 1) // шаг + сборка результата
}
print(sumTo(3)) // 6
Здесь происходит важная (и немного «математическая») вещь: функция возвращает выражение, которое включает рекурсивный вызов. То есть sumTo(3) не может сразу вернуть число — ей нужно узнать sumTo(2). А sumTo(2) нужно узнать sumTo(1). А sumTo(1) — sumTo(0). И только когда sumTo(0) возвращает 0, всё начинает собираться назад.
Если развернуть это вручную, получится примерно так:
- sumTo(3) = 3 + sumTo(2)
- sumTo(2) = 2 + sumTo(1)
- sumTo(1) = 1 + sumTo(0)
- sumTo(0) = 0
И дальше вверх:
- sumTo(1) = 1 + 0 = 1
- sumTo(2) = 2 + 1 = 3
- sumTo(3) = 3 + 3 = 6
Это и есть «разбей и собери» в самом простом виде: разбиваем задачу на «текущий n» и «остаток n - 1», а потом собираем через +.
Мини-пример: Recursion Lab в консольном приложении
Давайте аккуратно встроим рекурсию в наше мини-приложение, которое вы можете запускать и тестировать разными входами. Мы не делаем полноценный парсер команд (это отдельная большая тема), но простой выбор режима по числу нам уже по силам: читаем строку, превращаем в Int через Int(...) и используем switch.
Вот компактный каркас «лаборатории рекурсии»: пользователь вводит режим и число n, а мы вызываем соответствующую функцию.
import Foundation
func runRecursionLab() {
print("Mode (1=countdown, 2=trace, 3=sumTo):", terminator: " ")
let mode = Int(readLine() ?? "") ?? 0
print("n:", terminator: " ")
let n = Int(readLine() ?? "") ?? 0
switch mode {
case 1: countdown(from: n)
case 2: trace(n)
case 3: print(sumTo(n)) // например, 6
default: print("Unknown mode") // Unknown mode
}
}
runRecursionLab()
Обратите внимание: мы не усложняем ввод. Если пользователь ввёл ерунду, мы берём 0. Это нормально для учебного каркаса: наша цель сегодня — рекурсия и порядок выполнения, а не идеальный UX консоли.
Если вы запускаете эту программу несколько раз с разными режимами, рекурсия перестаёт быть абстрактной: она становится инструментом, который вы реально контролируете входом.
Как читать рекурсивный код: «найди стоп» и «найди уменьшение»
Рекурсивный код пугает новичков не потому, что он сложный, а потому что мозг сначала пытается «представить всё сразу». А рекурсия работает иначе: она разворачивается шаг за шагом. Поэтому чтение рекурсии — это навык, который можно поставить на рельсы.
Самое практичное правило чтения такое: сначала найдите базовый случай (остановку), затем найдите, как уменьшается вход, и только потом смотрите, что делается до/после вызова.
Например, вот мини-функция, которая демонстрирует «до и после» более явно: она печатает "down" по пути вниз и "up" по пути вверх.
import Foundation
func downUp(_ n: Int) {
if n <= 0 { return }
print("down \(n)") // down 3, down 2, down 1
downUp(n - 1)
print("up \(n)") // up 1, up 2, up 3
}
downUp(3)
И вот здесь рекурсия буквально показывает вам структуру стека: сначала мы «проваливаемся» вниз, затем «поднимаемся» вверх. Если вы научитесь в голове разделять эти два направления, половина страха от рекурсии исчезает.
4. Типичные ошибки
Ошибка №1: базовый случай отсутствует или написан так, что до него нельзя дойти.
Самый распространённый сценарий: человек написал рекурсивный вызов, но забыл условие остановки, или условие есть, но оно никогда не срабатывает. Например, если вы уменьшаете n, но базовый случай проверяете n == 100, то вы туда не придёте. Практика, которая реально помогает: сначала написать базовый случай, и только потом добавлять рекурсивный шаг.
Ошибка №2: рекурсивный шаг не уменьшает задачу.
Классика жанра: countdown(from:) с аргументом n вместо n - 1. Визуально код похож, компилятор доволен, а программа либо зависает, либо падает по переполнению стека. Лекарство простое, хоть и скучное: в каждом рекурсивном вызове глазами проверяйте, что аргумент меняется в сторону остановки.
Ошибка №3: перепутаны действия “до” и “после” рекурсивного вызова.
Новички часто ожидают, что код после рекурсивного вызова выполнится сразу. Но он выполнится только тогда, когда «нижние» вызовы закончатся. Поэтому печать или сборка результата может получиться в обратном порядке. Если порядок важен, полезно временно добавить отладочную печать вроде "enter"/"exit" (как в trace(_:)) — она быстро показывает, что происходит на самом деле.
Ошибка №4: рекурсия используется там, где проще обычный цикл, и из-за этого сложнее понять код.
Иногда задача линейная: пройти от 1 до n, что-то посчитать, что-то распечатать. Для таких задач цикл for или while обычно читается проще и не требует держать в голове стек вызовов. Рекурсия не обязана быть «везде», она хороша там, где её структура делает решение яснее, а не страшнее.
Ошибка №5: рекурсивная функция “всё делает сразу”: и печатает, и считает, и ещё меняет какие-то глобальные переменные.
Когда рекурсия смешивает несколько целей, вы теряете контроль над тем, что происходит на каждом уровне. В учебных примерах лучше придерживаться простоты: либо функция демонстрирует порядок выполнения (печать), либо возвращает значение (сумма). Когда цель одна, рекурсивная структура читается гораздо спокойнее — и мозг не просит «давайте обратно в циклы, я передумал».
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ