Рекурсія на масивах і рядках: «розбий і збери»

1. Патерн «розбий і збери»

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

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

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

Уявімо, що в нас є «послідовність» — масив або рядок. Тоді типова форма виглядає так:

solve(sequence):
  якщо sequence порожня → повернути базовий результат
  інакше:
     head = перший елемент
     tail = все, крім першого
     partial = solve(tail)
     повернути combine(head, partial)

Для наочності — невелика блок-схема:

flowchart TD
    A[Вхід: масив/рядок] --> B{Порожньо?}
    B -- так --> C[Повернути базовий результат]
    B -- ні --> D[Взяти перший елемент]
    D --> E[Взяти хвіст]
    E --> F[Рекурсивно розв'язати для хвоста]
    F --> G[Зібрати підсумок із head + partial]
    G --> H[Повернути результат]

Щоб не плутатися, корисно тримати в голові мінітабличку «що де лежить»:

Тепер перейдемо до практики — спочатку на масивах, тому що на старті вони психологічно простіші за рядки.

2. Масиви: рекурсія через ArraySlice

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

Ключовий прийом: пишемо рекурсивну функцію, яка приймає ArraySlice, а для зручності робимо «обгортку», що приймає звичайний [Int].

Приклад: сума елементів

Почнемо з функції суми. Вона ідеально показує «розбий і збери»: базовий випадок — порожньо, збирання — first + ....

import Foundation

func sum(_ slice: ArraySlice<Int>) -> Int {
    guard let first = slice.first else { return 0 }
    return first + sum(slice.dropFirst())
}

Тепер обгортка, щоб зручно викликати на масиві:

import Foundation

func sum(_ numbers: [Int]) -> Int {
    return sum(numbers[...])
}

І мініперевірка:

import Foundation

let nums = [10, 20, 30]
print(sum(nums)) // 60

Зверніть увагу: ми ніде не використовували індекси. Це не випадковість: індекси у ArraySlice — річ із характером.

ArraySlice не можна індексувати з нуля

Коли ви берете numbers[1...], ви отримуєте зріз, але він не зобов’язаний починатися з індексу 0. Це несподівано, але логічно: ArraySlice зберігає посилання на «базовий масив» і діапазон. Тому вираз slice[0] може бути просто неправильним індексом для цього зрізу.

Ось приклад помилки, яку майже кожен робить хоча б раз — і це нормально:

import Foundation

func brokenSum(_ slice: ArraySlice<Int>) -> Int {
    if slice.isEmpty { return 0 }
    return slice[0] + brokenSum(slice.dropFirst()) // часто ламається
}

Проблема не в рекурсії, а в припущенні, що перший елемент завжди лежить за індексом 0. Для ArraySlice правильніше мислити так: «у мене є first і є dropFirst()».

Якщо вам дуже потрібно працювати за індексами, то безпечний стиль виглядає так: працювати через startIndex і index(after:). Але для сьогоднішньої лекції нам частіше вистачить пари first/dropFirst(), тому що вони ідеально підходять під «розбий і збери».

3. Масиви: максимум і підрахунок за умовою

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

Максимум: результат може бути відсутнім

import Foundation

func maxValue(_ slice: ArraySlice<Int>) -> Int? {
    guard let first = slice.first else { return nil }
    let rest = slice.dropFirst()
    guard let restMax = maxValue(rest) else { return first }
    return max(first, restMax)
}

Невелика обгортка:

import Foundation

func maxValue(_ numbers: [Int]) -> Int? {
    return maxValue(numbers[...])
}

Перевірка:

import Foundation

print(maxValue([3, 10, 7]) ?? -1) // 10
print(maxValue([]) ?? -1)         // -1

Ми використали ?? -1 як «значення за замовчуванням для виведення», але важливо не плутати: сама функція чесно повернула nil, якщо вхід був порожній.

Підрахунок додатних: логіка збирання через «+1 або +0»

import Foundation

func countPositive(_ slice: ArraySlice<Int>) -> Int {
    guard let first = slice.first else { return 0 }
    let add = first > 0 ? 1 : 0
    return add + countPositive(slice.dropFirst())
}

Простий тест:

import Foundation

print(countPositive([-2, 0, 5, 9])) // 2

Тут ми вже відчуваємо ритм патерну: базовий випадок → head → tail → partial → збирання.

Тепер перейдемо до рядків, де є два «маршрути» рекурсії.

4. Рядки: рекурсія через Substring і String.Index

Рядки у Swift живуть у світі Unicode, тому поводитися з ними як із масивом байтів не можна. На практиці для рекурсії по рядку найчастіше використовують один із двох підходів: або працювати з Substring і відкушувати dropFirst(), або йти по індексах String.Index від startIndex до endIndex.

Зараз ми розглянемо обидва підходи, тому що вони корисні в різних ситуаціях. А ще це чудовий спосіб зрозуміти, чому в Swift взагалі існує Substring.

Підхід 1: Substring — «як із масивом, тільки для символів»

Substring — це «зріз рядка». У нього є first і dropFirst(). Тобто він майже ідеально повторює стиль роботи з ArraySlice. Це найпростіший шлях до рекурсивних задач на рядках: «перший символ + хвіст».

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

Розворот рядка через «збирання під час повернення»

Дуже показова задача: розгортаємо рядок, додаючи поточний символ у кінець результату.

import Foundation

func reversedString(_ s: Substring) -> String {
    guard let first = s.first else { return "" }
    return reversedString(s.dropFirst()) + String(first)
}

Перевірка:

import Foundation

let word = "Swift"
print(reversedString(word[...])) // tfiwS

Зверніть увагу на «збирання»: ми додаємо String(first) після рекурсивного виклику, тому символи й «перевертаються».

Видаляємо цифри з рядка

Зробимо функцію, яка викидає цифри. Це корисно для нашого мінізастосунку: «очищення тексту».

import Foundation

func removeDigits(_ s: Substring) -> String {
    guard let first = s.first else { return "" }
    let rest = removeDigits(s.dropFirst())
    return first.isNumber ? rest : String(first) + rest
}

Перевірка:

import Foundation

print(removeDigits("a1b2c3"[...])) // abc

Тут збирання вже умовне: якщо символ — цифра, ми його не додаємо.

Підхід 2: String.Index — коли потрібно бути точним

Підхід із Substring простий і приємний, але іноді вам потрібно не створювати нові зрізи або зручніше явно керувати позицією в рядку. Наприклад, ви хочете стартувати не з початку. Тоді використовується рекурсія з індексом: функція приймає рядок і поточний String.Index.

Базовий випадок: індекс дійшов до endIndex. Рекурсивний крок: index(after:).

Підрахунок цифр через індекс

import Foundation

func countDigits(in s: String, from idx: String.Index) -> Int {
    if idx == s.endIndex { return 0 }
    let add = s[idx].isNumber ? 1 : 0
    let next = s.index(after: idx)
    return add + countDigits(in: s, from: next)
}

Обгортка «для зручного виклику»:

import Foundation

func countDigits(in s: String) -> Int {
    return countDigits(in: s, from: s.startIndex)
}

Перевірка:

import Foundation

print(countDigits(in: "Room 101")) // 3

Паліндром: порівняння символів із двох кінців

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

import Foundation

func isPalindrome(_ s: String, left: String.Index, right: String.Index) -> Bool {
    if left >= right { return true }
    if s[left] != s[right] { return false }
    return isPalindrome(s, left: s.index(after: left), right: s.index(before: right))
}

І обгортка:

import Foundation

func isPalindrome(_ s: String) -> Bool {
    guard !s.isEmpty else { return true }
    return isPalindrome(s, left: s.startIndex, right: s.index(before: s.endIndex))
}

Перевірка:

import Foundation

print(isPalindrome("level")) // true
print(isPalindrome("swift")) // false

Так, це паліндром «в лоб» — без нормалізації регістру й пробілів. Це нормально: ми тренуємо рекурсивну структуру, а не робимо ідеальну перевірку «А рожа упала на лапу Азора».

5. Мінізастосунок: «RecursionTextLab» в одному файлі

Щоб приклади не виглядали як розрізнені заклинання, зберемо невеликий консольний інструмент, який виконує кілька операцій із масивами та рядками. Він житиме в одному файлі, як ми робили раніше, а користувачеві ми просто запропонуємо меню: вибрати операцію, ввести дані, отримати результат.

Парсимо рядок чисел у масив Int

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

import Foundation

func readIntArray() -> [Int] {
    let line = readLine() ?? ""
    return line.split(separator: " ").compactMap { Int($0) }
}

Підключаємо рекурсивні функції

Зробимо акуратні обгортки:

import Foundation

func sum(_ numbers: [Int]) -> Int { sum(numbers[...]) }
func maxValue(_ numbers: [Int]) -> Int? { maxValue(numbers[...]) }

(Функції sum(_ slice: ArraySlice<Int>) і maxValue(_ slice: ArraySlice<Int>) вважаємо вже оголошеними вище в цьому самому файлі.)

Меню й запуск

Скелет main (top-level code) тримаємо максимально простим:

import Foundation

print("1 — сума, 2 — максимум, 3 — розворот, 4 — підрахунок цифр, 5 — паліндром")
let choice = Int(readLine() ?? "") ?? 0

switch choice {
case 1:
    print("Введіть числа:")
    print(sum(readIntArray())) // наприклад: 6
case 2:
    print("Введіть числа:")
    print(maxValue(readIntArray()) ?? 0) // наприклад: 10
default:
    print("Інші випадки — нижче...")
}

Продовжимо switch для рядкових операцій окремим шматком, щоб не робити громіздкий блок на 40 рядків:

import Foundation

switch choice {
case 3:
    print("Введіть текст:")
    let s = readLine() ?? ""
    print(reversedString(s[...])) // "Swift" → "tfiwS"
case 4:
    print("Введіть текст:")
    let s = readLine() ?? ""
    print(countDigits(in: s)) // "Room 101" → 3
case 5:
    print("Введіть текст:")
    let s = readLine() ?? ""
    print(isPalindrome(s)) // "level" → true
default:
    break
}

Так, тут два switch підряд по одній змінній — не найвитонченіший стиль. Але для новачка це часто читається легше, ніж один величезний switch, особливо коли ми поступово нарощуємо застосунок. На наступних кроках курсу ви все одно навчитеся краще структурувати програми, а зараз нам важливіша ясність, ніж естетика.

6. Типові помилки

Помилка №1: «забули базовий випадок», і рекурсія поїхала в закат.
На масивах і рядках це виглядає особливо підступно: ви начебто пишете dropFirst(), але не перевіряєте порожнечу. У підсумку first береться в порожнього значення, або ви намагаєтеся індексувати рядок за межами, і програма падає. Лікується це дуже буденно: насамперед у рекурсивній функції пишемо guard або if на порожнечу/endIndex, і лише потім — усе інше.

Помилка №2: індексування ArraySlice так, ніби це [Int] із нулем на початку.
Зріз масиву — це не «новий масив із нульовою індексацією». Через це slice[0] може бути неправильним індексом. Найбезпечніший стиль для нашої теми — first + dropFirst(). Якщо дуже хочеться індексів, використовуйте startIndex і index(after:), але тоді стежте за межами подвійно уважно.

Помилка №3: спроба індексувати String через Int.
Це одна з найпоширеніших «свіжих» помилок: після масивів рука тягнеться написати s[0]. У Swift так не можна, і це не шкідливість мови, а захист від некоректної роботи з Unicode. Для рекурсії по рядку беріть або Substring і працюйте як із послідовністю (first/dropFirst()), або використовуйте String.Index і просувайтеся через index(after:).

Помилка №4: зберігати Substring «на потім», ніби це String.
Substring спеціально зроблений як зріз, який може посилатися на пам’ять вихідного рядка, тому маленький Substring може утримувати великий вихідний рядок у пам’яті. Якщо вам потрібно зберегти результат надовго, зазвичай варто перетворити його на String через String(substring) або зібрати новий String у процесі обчислення. Ця мотивація прямо закладена в модель Substring як окремого типу.

Помилка №5: змішування логіки «розбити» і «збирати» в один нечитаємий ком.
Рекурсивні функції сильно виграють від ритму: базовий випадок → взяти first → зробити rest → рекурсивний виклик → збирання. Коли ви намагаєтеся написати все в один рядок із трьома тернарними операторами й двома ??, виходить код, який формально компілюється, але психологічно саботує супровід. Краще трохи довше, зате зрозуміліше: рекурсія й так достатньо «особлива», не треба штучно ускладнювати їй життя.