1. Дерево данных
Перед тем как говорить о рекурсивных структурах данных, полезно познакомиться с одной простой моделью — деревом. Дерево — это структура, где элементы могут содержать другие элементы того же типа. Из-за этого структура получается вложенной.
Самый знакомый пример — файловая система. Папка может содержать файлы и другие папки. А внутри каждой папки снова могут быть файлы и папки. Если нарисовать такую структуру, она выглядит примерно так:
flowchart TD
A["Documents"] --> B["report.pdf"]
A --> C["Projects"]
C --> D["code.swift"]
C --> E["Archive"]
E --> F["old.txt"]
Такие структуры называют деревьями, потому что они действительно напоминают дерево:
- есть корень — верхний элемент
- есть ветви — элементы, которые содержат другие элементы
- есть листья — элементы без вложенных элементов
В нашем примере:
- Documents, Projects, Archive — узлы
- report.pdf, code.swift, old.txt — листья
В программировании подобные структуры встречаются очень часто: файловые системы, комментарии с ответами, меню с подменю, математические выражения. Во всех этих случаях элементы могут содержать другие элементы того же типа.
2. Рекурсивные структуры данных
Когда данные имеют такую вложенную форму, их называют рекурсивными структурами данных. Это означает, что тип данных может содержать значения того же типа. Например, математическое выражение:
2 + (3 + 4)Снаружи это сложение. Но справа снова находится сложение.
Если изобразить структуру выражения, получится дерево:
flowchart TD
A["+"] --> B["2"]
A --> C["+"]
C --> D["3"]
C --> E["4"]
Здесь:
- числа — листья
- операции — узлы, которые соединяют подвыражения
Получается интересная ситуация: выражение может состоять из других выражений. Именно в этот момент возникает естественный вопрос: как в Swift описать тип, который может содержать самого себя?
Обычные структуры и перечисления так писать нельзя напрямую — компилятор должен понимать размер значения в памяти. Поэтому Swift использует специальный механизм для таких случаев. В следующих разделах я познакомлю вас с инструментом, который позволяет описывать такие структуры: рекурсивный enum с ключевым словом indirect.
3. Быстрый обзор enum и case с данными
enum как «один вариант из нескольких»
Слово enum (enumeration) звучит серьёзно, но на базовом уровне это просто тип, который может хранить одно из нескольких состояний. По смыслу это очень похоже на switch: там вы выбираете ветку по значению, а enum позволяет заранее сказать «вот какие варианты вообще бывают».
Важно: мы еще не изучаем enum полноценно (это будет отдельный уровень позже). Сегодня — только столько, сколько нужно, чтобы понять рекурсивную структуру.
Самый простой enum выглядит так:
import Foundation
enum LampState {
case on
case off
}
let state: LampState = .on
print(state) // on
Обратите внимание на точку .on: Swift часто позволяет не писать имя типа слева (LampState.on), если компилятор и так понимает контекст.
И типичный способ “раскрыть” enum — это switch:
import Foundation
enum LampState { case on, off }
func describe(_ state: LampState) -> String {
switch state {
case .on: return "Лампа светит"
case .off: return "Лампа отдыхает"
}
}
print(describe(.off)) // Лампа отдыхает
case с полезной нагрузкой
До этого case on/off были просто метками. Но у enum есть особенность: case может хранить данные. Это похоже на то, как если бы вы сказали: «Сообщение бывает двух типов: текст или число», и тогда у “текста” будет строка внутри, а у “числа” — число.
Пример:
import Foundation
enum Input {
case number(Int)
case text(String)
}
let x: Input = .number(42)
print(x) // number(42)
Достаём данные через switch — и это выглядит почти как аккуратная распаковка “контейнера”:
import Foundation
enum Input { case number(Int), text(String) }
func printInput(_ value: Input) {
switch value {
case .number(let n):
print("Число: \(n)") // Число: 42
case .text(let s):
print("Строка: \(s)")
}
}
printInput(.number(42))
Вот это case .number(let n) — фундаментальная техника. И она же будет главным инструментом, когда мы начнём обходить рекурсивную структуру: каждый узел “раскрывается” через switch, мы смотрим, что внутри, и решаем, что делать дальше.
3. Рекурсивный enum и ключевое слово indirect
Проблема: как описать вложенность в типах
Теперь к сути. Хотим описать выражение (очень упрощённо):
- выражение может быть числом
- или суммой двух выражений
То есть тип выглядит примерно так:
- number(Int)
- add(Expr, Expr) — слева выражение и справа выражение
И тут у мозга возникает маленькая паника: «Подождите… Expr содержит Expr… значит Expr содержит Expr, который содержит Expr… это же бесконечно!»
Если бы компилятор попытался хранить такое значение “целиком внутри”, ему понадобилась бы бесконечная память. Поэтому Swift требует явного механизма, который скажет: «Рекурсивная часть хранится не напрямую, а через специальную косвенность».
И вот тут появляется ключевое слово indirect. Оно буквально про это: хранить “косвенно”.
indirect enum: минимальная рабочая модель дерева
Теперь соберём наш “тип выражения”. Синтаксис запоминать наизусть не надо — важна форма: лист и узел.
import Foundation
enum Expr {
case number(Int)
indirect case add(Expr, Expr)
}
Читаем человеческим языком:
- Expr.number(5) — это лист дерева: внутри просто число.
- Expr.add(left, right) — это узел дерева: внутри два подвыражения.
Ключевое слово indirect стоит на кейсе add, потому что именно он “ссылается” на Expr снова.
Создадим значение:
import Foundation
enum Expr {
case number(Int)
indirect case add(Expr, Expr)
}
let expr: Expr = .add(.number(2), .add(.number(3), .number(4)))
print(expr) // add(number(2), add(number(3), number(4)))
И вот это важно: мы уже получили вложенную структуру данных. Мы пока её не вычисляем и не “обходим” глубоко — просто научились описывать и строить.
Лист и узел как способ думать
Чтобы не путаться, держите простую “табличку смысла”:
| Роль в дереве | Как выглядит в Expr | Что внутри |
|---|---|---|
| Лист дерева | |
Простой Int |
| Узел дерева | |
Два Expr |
Вложенность получается автоматически: раз left/right — это тоже Expr, то они могут быть и листами, и узлами, и узлами из узлов (и так далее).
Два способа написать indirect
Когда структура небольшая, чаще пишут indirect на конкретном кейсе (как мы сделали). Но Swift позволяет объявить косвенность “сразу для всего перечисления”, если вы заранее знаете, что там будет рекурсия много где.
Выглядит так:
import Foundation
indirect enum Expr {
case number(Int)
case add(Expr, Expr)
}
Оба варианта подходят, но смысл у них чуть разный:
- indirect case add(...) — точечно: “вот этот кейс рекурсивный”.
- indirect enum Expr — глобально: “вообще этот enum может быть рекурсивным”.
Для учебных примеров точечный indirect case часто читается проще: вы сразу видите, где начинается “магия вложенности”.
4. Мини-проект: Expression Playground
Встраиваем в консольное приложение
Чтобы не оставлять Expr как музейный экспонат “посмотрите и не трогайте”, добавим его в маленькое консольное приложение: читаем ввод, выбираем сценарий, печатаем результат. Это будет тот же стиль top‑level кода, который вы уже использовали раньше, только теперь данные будут вложенными.
Сделаем выбор из двух готовых выражений: простое и вложенное.
import Foundation
enum Expr {
case number(Int)
indirect case add(Expr, Expr)
}
let choice = Int(readLine() ?? "") ?? 1
let expr: Expr = (choice == 1)
? .add(.number(2), .number(3))
: .add(.number(2), .add(.number(3), .number(4)))
print(expr)
// choice=1 -> add(number(2), number(3))
// choice=2 -> add(number(2), add(number(3), number(4)))
Здесь мы специально не делаем парсер выражений из строки — потому что “разбор текста” (кавычки, приоритеты, токены) — отдельная большая тема, и мы туда сегодня не лезем. Наша цель: увидеть, что данные уже имеют форму дерева.
Почему без indirect нельзя
Частая реакция новичка: «Ну и зачем это ключевое слово? Почему Swift сам не догадается?»
Потому что если бы Expr.add(Expr, Expr) хранил Expr напрямую, то размер Expr в памяти должен был бы включать размер двух Expr, каждый из которых включает размер двух Expr, и так далее до бесконечности. Компилятор не может выбрать конечный размер для значения.
indirect говорит компилятору: «Рекурсивная часть будет храниться косвенно (через отдельную коробочку/ссылку)». Вам не нужно сейчас запоминать, как именно это сделано внутри — достаточно знать, что это способ разрешить рекурсию в данных, а не в коде.
Микро-расширение: добавим ещё один узел
Чтобы почувствовать, что indirect enum — это не “трюк ради трюка”, расширим выражение ещё одним вариантом, например умножением. Смысл тот же: лист и узлы.
import Foundation
enum Expr {
case number(Int)
indirect case add(Expr, Expr)
indirect case mul(Expr, Expr)
}
let expr: Expr = .mul(.add(.number(2), .number(3)), .number(4))
print(expr) // mul(add(number(2), number(3)), number(4))
Заметьте, что модель стала богаче, а код создания значения остался понятным: мы просто собираем дерево, как конструктор из кубиков.
5. Типичные ошибки
Ошибка №1: попытка “понять рекурсивный enum”, не выделяя лист и узел.
Если вы не договорились сами с собой, какой кейс является “простым” (листом), а какой — “составным” (узлом), то тип начинает выглядеть как каша: “везде всё”. В таких моделях почти всегда нужно явно иметь хотя бы один базовый вариант вроде .number, .text, .file — то, что не содержит внутри себя self.
Ошибка №2: забыли indirect и удивились ошибке компилятора.
Это классика: написали case add(Expr, Expr) без indirect и получили сообщение, похожее на recursive enum is not marked ‘indirect’. Это не придирка Swift и не “сломанный компилятор”, а защита от бесконечного размера значения. Либо ставьте indirect на рекурсивные кейсы, либо делайте indirect на весь enum.
Ошибка №3: попытка сразу парсить выражение из строки.
Как только вы пытаетесь превратить "2 + (3 + 4)" во внутреннюю структуру, вы внезапно упираетесь в токены, пробелы, приоритет операторов, скобки и “а что если пользователь ввёл ерунду”. Это отдельная задача. В учебной модели сегодня лучше честно строить дерево вручную или выбирать из нескольких предзаготовок через readLine().
Ошибка №4: смешивание структуры данных и логики обработки.
Очень хочется сделать enum Expr и тут же внутри написать всё подряд: и печать, и вычисление, и подсчёт узлов, и проверку корректности. На первом знакомстве это перегружает и мешает увидеть главное: indirect enum — это прежде всего форма данных (лист/узел), а “что мы с ней делаем” — отдельный слой.
Ошибка №5: ожидание, что print(expr) будет выводить красиво.
По умолчанию вывод enum — это скорее диагностическая строка, а не математическая запись. Увидеть add(number(2), add(...)) — нормально. “Человеческое” форматирование — отдельная задача, и она становится понятной как раз тогда, когда вы уже уверенно различаете лист и узел и можете их обходить через switch.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ