Рекурсивний обхід вкладених даних: обхід і агрегація

1. Ідея обходу та модель даних

Коли ви чуєте слово «обхід», мозок малює щось на кшталт «обійти квартал» або «обійти боса на роботі» — обидва варіанти вимагають стратегії. У програмуванні обхід — це перегляд усіх елементів структури даних у певному порядку. Для масиву все просто: ви йдете зліва направо. А от із вкладеними даними починається магія: в одного елемента можуть бути «діти», а в тих — свої «діти», і так далі.

Найприємніше тут ось що: для вкладеності рекурсія — це не просто «ще один спосіб», а найчастіше найпряміший і найчитабельніший. Код починає повторювати форму даних: «якщо це листок — робимо одне, якщо це вузол — ідемо всередину».

Щоб візуально зафіксувати структуру, ми використовуватимемо прості схеми, зокрема Mermaid-діаграми. Такий формат схем трапляється навіть у технічній документації екосистеми Swift.

Міні-модель списку справ

Нам потрібен приклад вкладеної структури, який зрозумілий на побутовому рівні. Нехай це буде список справ, де є звичайні завдання і є групи завдань (проєкт → підзавдання). Це майже як папки й файли, тільки замість файлів — справи, а замість папок — «групи справ». Ми не будемо ускладнювати все термінами з CS, просто запам’ятаємо: елемент може бути простим або таким, що містить інші елементи.

Створімо ескіз типу через enum (як у лекції 98): один варіант — завдання, інший — група. Група має зберігати всередині елементи того самого типу, тому потрібен indirect.

import Foundation

enum TodoNode {
    case task(title: String, isDone: Bool)
    indirect case group(title: String, items: [TodoNode])
}

Зверніть увагу на стиль: ми зберігаємо тільки те, що потрібно для прикладів обходу. Жодних дат, пріоритетів і дедлайнів — інакше це перетвориться на «менеджер завдань», а ми сьогодні тренуємо патерн обходу.

Тепер створимо маленьке «дерево» вручну, просто в коді:

let todos: TodoNode =
    .group(title: "Субота", items: [
        .task(title: "Купити хліб", isDone: true),
        .group(title: "Навчання", items: [
            .task(title: "Рекурсія", isDone: false),
            .task(title: "Масиви", isDone: true)
        ])
    ])

Щоб стало зовсім зрозуміло, ось та сама структура як схема:

flowchart TD
    A["Група: Субота"] --> B["Завдання: Купити хліб ✅"]
    A --> C["Група: Навчання"]
    C --> D["Завдання: Рекурсія ⏳"]
    C --> E["Завдання: Масиви ✅"]

(Позначки — це просто візуальна підказка, у коді в нас isDone: Bool.)

2. Патерн «обхід + агрегація»

Якщо сказати зовсім просто, обхід відповідає на запитання «як пройти по структурі», а агрегація — «що зібрати по дорозі». Наприклад, «порахувати елементи», «знайти щось», «зібрати список», «обчислити глибину вкладеності». Це різні цілі, але форма коду буде підозріло схожою — і це добре: мозку легше.

У цього патерну є майже універсальна форма:

1) Якщо вузол простий (листок) — повертаємо відповідь для нього.

2) Якщо вузол складений — рекурсивно отримуємо відповіді від вкладених елементів і об’єднуємо їх.

У Swift це майже завжди виглядає як switch по enum і два case.

Ось «скелет» функції, який компілюється, де ResultType — це те, що ми хочемо отримати:

func visit(_ node: TodoNode) -> Int {
    switch node {
    case .task:
        return 1
    case .group(_, let items):
        var total = 1
        for item in items {
            total += visit(item)
        }
        return total
    }
}

Так, це вже «агрегація»: ми накопичуємо значення в total. Але поки не чіпляйтеся до сенсу числа — важливіше побачити форму.

Таблиця: мета агрегації і тип результату

Іноді допомагає зафіксувати, що результат обходу може бути різного типу:

Int

0

Bool

false

nil

[String]

[]

String

""

Слово «нейтральне» тут означає «те, що не заважає об’єднанню». Наприклад, порожній масив не заважає + (склеюванню масивів), а 0 не заважає сумі.

3. Приклади агрегатів на одному дереві

Зараз буде найкорисніша частина: кілька функцій, які обходять одну й ту саму структуру TodoNode, але збирають різні результати. Ваше завдання під час читання — не запам’ятати все, а побачити: «о, форма одна й та сама, змінюється лише те, що повертаємо і як об’єднуємо».

Порахувати кількість завдань

Почнімо з простого і зрозумілого. Група — це контейнер, вона не є завданням. Тому в .group ми просто підсумовуємо результати дітей.

func taskCount(_ node: TodoNode) -> Int {
    switch node {
    case .task:
        return 1
    case .group(_, let items):
        var total = 0
        for item in items { total += taskCount(item) }
        return total
    }
}

Перевірка на нашому прикладі:

print(taskCount(todos)) // 3

Порахувати, скільки завдань виконано

Тепер листок .task несе трохи більше сенсу: якщо isDone == true, додаємо 1, інакше 0. Група й далі підсумовує результати дітей.

func doneCount(_ node: TodoNode) -> Int {
    switch node {
    case .task(_, let isDone):
        return isDone ? 1 : 0
    case .group(_, let items):
        var total = 0
        for item in items { total += doneCount(item) }
        return total
    }
}

Перевірка:

print(doneCount(todos)) // 2

Знайти перше невиконане завдання

Тут важливо чесно визнати: «може не знайтися». Отже, результат — Optional. Це дуже природно лягає на патерн обходу: якщо листок — або це наша мета, або ні; якщо група — шукаємо в дітях, і щойно знайшли потрібне, далі не переглядаємо решту.

func firstUndoneTitle(_ node: TodoNode) -> String? {
    switch node {
    case .task(let title, let isDone):
        return isDone ? nil : title
    case .group(_, let items):
        for item in items {
            if let found = firstUndoneTitle(item) { return found }
        }
        return nil
    }
}

Перевірка:

print(firstUndoneTitle(todos) ?? "усе зроблено") // Рекурсія

Зверніть увагу: тут ми вперше використовуємо ранній вихід у рекурсивному обході — щойно знайшли потрібне, далі не шукаємо.

Зібрати всі назви завдань у плоский список

Це класичний приклад «зібрати все». Листок повертає масив з одного елемента, група склеює масиви дітей.

func allTaskTitles(_ node: TodoNode) -> [String] {
    switch node {
    case .task(let title, _):
        return [title]
    case .group(_, let items):
        var result: [String] = []
        for item in items { result += allTaskTitles(item) }
        return result
    }
}

Перевірка:

print(allTaskTitles(todos)) // ["Купити хліб", "Рекурсія", "Масиви"]

Так, result += ... виглядає дуже зручно. Водночас варто пам’ятати: склеювання масивів має свою ціну. Але глибоко обговорювати продуктивність сьогодні не будемо — це не мета лекції 99.

4. Контекст обходу: глибина і шлях

Іноді мало просто «ходити» й «збирати». Хочеться розуміти, де саме ми перебуваємо: на якій глибині вкладеності або яким «шляхом» ми дійшли до завдання. Це схоже на ситуацію: «я знайшов шкарпетки, але в якій коробці вони лежали?». У таких випадках ми додаємо параметр у функцію і передаємо його в рекурсивні виклики, оновлюючи по дорозі.

Максимальна глибина вкладеності

Домовимося: завдання .task має глибину 1. Група має глибину 1 + максимальна глибина серед дітей. Якщо в групи немає дітей, тобто вона порожня, її глибина — 1.

func maxDepth(_ node: TodoNode) -> Int {
    switch node {
    case .task:
        return 1
    case .group(_, let items):
        var best = 1
        for item in items { best = max(best, 1 + maxDepth(item)) }
        return best
    }
}

Перевірка:

print(maxDepth(todos)) // 3

Чому 3? Бо в нас: "Субота" (1) → "Навчання" (2) → "Рекурсія" (3).

Зібрати шляхи до кожного завдання

Тут ми передаватимемо поточний шлях униз. Це дуже схоже на обхід файлової системи, тільки без справжніх файлів. Зверніть увагу: ми знову агрегуємо результат, але тепер це масив шляхів.

func taskPaths(_ node: TodoNode, prefix: String) -> [String] {
    switch node {
    case .task(let title, _):
        return ["\(prefix)/\(title)"]
    case .group(let title, let items):
        let nextPrefix = prefix.isEmpty ? title : "\(prefix)/\(title)"
        var result: [String] = []
        for item in items { result += taskPaths(item, prefix: nextPrefix) }
        return result
    }
}

Перевірка:

let paths = taskPaths(todos, prefix: "")
print(paths)
// ["Субота/Купити хліб", "Субота/Навчання/Рекурсія", "Субота/Навчання/Масиви"]

Тут важливо відчути ідею: частину інформації ми не обчислюємо на зворотному шляху, а несемо вниз як контекст.

5. Практика: міні-інтеграція в застосунок

Давайте зробимо простий приклад: друкуємо дерево і рахуємо агрегати. Ми не будуємо повноцінний парсер команд — це буде значно пізніше в курсі, — але базовий split + switch у нас уже є, і цього досить, щоб main.swift не перетворився на музей print().

import Foundation

let root = todos

let command = readLine() ?? "stats"
switch command {
case "stats":
    print("завдання =", taskCount(root))       // завдання = 3
    print("виконано =", doneCount(root))       // виконано = 2
    print("глибина =", maxDepth(root))         // глибина = 3
case "first":
    print(firstUndoneTitle(root) ?? "усе зроблено") // Рекурсія
default:
    print("Команди: stats | first")
}

Якщо хочеться зробити це трохи більш «командним», можна дозволити введення на кшталт "paths":

case "paths":
    for p in taskPaths(root, prefix: "") {
        print(p)
    }

Важливо: ми не ускладнюємо введення аргументами, прапорцями і лапками. Наша мета — показати, як рекурсивний обхід стає корисною підпрограмою, яку можна викликати з «головного» коду.

6. Типові помилки під час рекурсивного обходу вкладених даних

Помилка №1: «Я обробив task, а про group забув» (або навпаки).
Коли структура вкладена, switch має бути вичерпним. Якщо ви в обході обробляєте лише .task, ви по суті ігноруєте дітей і отримуєте неправильний результат. Виправляється це просто: спочатку пишете switch, додаєте обидва case, а вже потім наповнюєте їх логікою.

Помилка №2: базовий випадок є, але він не повертає «правильний тип нейтралі».
Наприклад, ви збираєте список рядків [String], а в порожньому або «непридатному» випадку повертаєте [""] замість []. Потім раптово отримуєте «порожні елементи» у виведенні. У рекурсивній агрегації базовий випадок — це не просто «зупинитися», а зупинитися так, щоб об’єднання результатів працювало чесно.

Помилка №3: змішування цілей в одній функції.
Новачки часто намагаються зробити «універсальний обхід», який і друкує дерево, і рахує кількість завдань, і збирає назви — усе одразу. Такий код швидко перетворюється на кашу з print і return. Краще тримати кожну функцію з одним сенсом: одна рахує, інша шукає, третя форматує рядок. Обхід однаковий — мета різна.

Помилка №4: неправильний «ранній вихід» під час пошуку.
У firstUndoneTitle ми робили ранній вихід: щойно знайшли — одразу повернули. Типова поломка тут — продовжувати обхід після того, як уже знайшли, і в підсумку «перший знайдений» перетворюється на «останній знайдений» (бо ви перезаписали змінну). Для пошуку корисно читати код як людську інструкцію: «знайшов — іди додому, не стій під дощем».

Помилка №5: плутанина «глибина вузла» vs «глибина дерева».
У функції maxDepth легко помилитися на одиницю: десь забути додати 1, десь додати двічі. Це та сама класична помилка off-by-one, тільки на деревах. Лікується контрольними прикладами: дерево з одного завдання має давати глибину 1, а група з одним завданням усередині — глибину 2.