Что такое рекурсия?

Рекурсия — это процесс, в котором функция вызывает саму себя напрямую или косвенно. Это мощный инструмент для решения задач, которые можно разбить на более мелкие подзадачи того же типа.

Базовый пример рекурсии :

func factorial(_ n: Int) -> Int {
    guard n > 1 else { return 1 }  // Базовый случай
    return n * factorial(n - 1)    // Рекурсивный случай
}

Ключевые компоненты рекурсии

1. Базовый случай (Base case):

   • Условие выхода из рекурсии
   • Препятствует бесконечной рекурсии
   • Пример: if n <= 1 { return 1 }

2. Рекурсивный случай (Recursive case):

   • Часть, где функция вызывает саму себя
   • Должен приближаться к базовому случаю
   • Пример: return n * factorial(n - 1)

Правила использования рекурсии

1. Всегда определяйте базовый случай: Без него рекурсия будет бесконечной, что приведет к переполнению стека.

2. Рекурсивный вызов должен приближать к базовому случаю: Каждый вызов должен уменьшать проблему.

3. Учитывайте глубину рекурсии: В Swift глубина стека ограничена (```64K вызовов).

Практические примеры в iOS разработке

1. Обход дерева :

extension UIView {
    func findAllSubviews<T: UIView>(ofType type: T.Type) -> [T] {
        var result = subviews.compactMap { $0 as? T }
        for subview in subviews {
            result += subview.findAllSubviews(ofType: type)
        }
        return result
    }
}

2. Работа с файловой системой:

func listFiles(in directory: String, indent: String = "") {
    let fileManager = FileManager.default
    guard let files = try? fileManager.contentsOfDirectory(atPath: directory) else { return }

    for file in files {
        print(indent + file)
        let path = directory + "/" + file
        var isDir: ObjCBool = false
        if fileManager.fileExists(atPath: path, isDirectory: &isDir), isDir.boolValue {
            listFiles(in: path, indent: indent + "  ")  // Рекурсивный вызов
        }
    }
}

Нюансы и оптимизации

1. Хвостовая рекурсия :

Swift оптимизирует хвостовую рекурсию через tailrec (в некоторых случаях).

func factorial(_ n: Int, _ accumulator: Int = 1) -> Int {
    guard n > 1 else { return accumulator }
    return factorial(n - 1, n * accumulator)  // Хвостовая рекурсия
}

2. Мемоизация :

Для избежания повторных вычислений.

var memo = [Int: Int]()
func fibonacci(_ n: Int) -> Int {
    if let result = memo[n] { return result }
    guard n > 1 else { return n }
    let result = fibonacci(n - 1) + fibonacci(n - 2)
    memo[n] = result
    return result
}

3. Ограничения iOS:

• Глубина стека вызовов ограничена
• Может вызвать crash при глубокой рекурсии
• Для сложных задач лучше использовать итеративные решения

Когда использовать рекурсию?

Хорошие кандидаты:

• Древовидные структуры (UIView, FileSystem)
• Задачи "разделяй и властвуй" (сортировка, поиск)
• Математические последовательности

Плохие кандидаты:

• Линейные обработки больших данных
• Когда важна производительность
• В реальном времени (UI обновления)

Альтернативы рекурсии

1. Итерации (циклы):

   func factorialIterative(_ n: Int) -> Int {
       var result = 1
       for i in 1...n {
           result *= i
       }
       return result
   }
   

2. Стек + цикл (имитация рекурсии): Полезно для глубокой рекурсии.

Резюмируем

Рекурсия — это элегантный способ решения задач, которые естественным образом можно разделить на подобные подзадачи. В iOS разработке она полезна для работы с иерархическими структурами, но требует осторожности из-за ограничений стека. Всегда проверяйте:

1. Наличие базового случая
2. Приближение к базовому случаю
3. Глубину рекурсии
4. Возможности оптимизации (хвостовая рекурсия, мемоизация)

Для production-кода с большими данными часто предпочтительнее итеративные решения.