Я заменил все циклы рекурсией — вот что произошло

В этом мире есть два типа разработчиков.

Здравомыслящие, которые используют циклы for и while, как нормальные люди. И… такие, как я, которые однажды утром просыпаются и решают: «А что, если я больше никогда не буду писать циклы?»

Хотелось бы сказать, что это началось как благородный эксперимент — вроде доказательства элегантности рекурсии или исследования функциональной чистоты. Но нет.

Правда гораздо глупее.

Мне было скучно.

И, как любой скучающий разработчик, я подумал: «Что самое худшее я могу сегодня сделать со своим кодом?». Ответ, по-видимому, был таким: заменить каждый цикл в Swift рекурсией.

Правила безумия

Я не хотел жульничать, поэтому записал несколько строгих правил:

1. Никаких циклов.
   • Если я набирал for, while или даже .forEach, я должен был немедленно это удалить.
   • Моя мышечная память меня за это ненавидела.
2. Рекурсия повсюду.
   • Нужно просуммировать массив? Рекурсия.
   • Вложенные циклы? Вложенная рекурсия.
   • Печать пяти чисел? О, конечно, это рекурсия.
3. Только Swift. Поскольку я iOS-разработчик, и если уж я собирался сжечь свой здравый смысл, я хотел сделать это на языке, который знаю лучше всего.

Шаг 1: печать чисел

Обычно вы бы написали:

for i in 1...5 {
    print(i)
}

Но в мире рекурсии это незаконно.

Вот моя версия:

func printNumbers(_ n: Int) {
    if n == 0 { return }
    printNumbers(n - 1)
    print(n)
}

И это сработало. Я почувствовал себя гением. Примерно на пять секунд. Потому что в глубине души я знал, что это рекурсивный эквивалент вспомогательных колёс у трехколесного велосипеда.

Шаг 2: суммирование массива

Обычный способ:

let numbers = [1, 2, 3, 4, 5]
var sum = 0

for num in numbers {
    sum += num
}
print(sum) // 15

Рекурсия:

func sumArray(_ numbers: [Int], _ index: Int = 0) -> Int {
    if index == numbers.count { return 0 }
    return numbers[index] + sumArray(numbers, index + 1)
}

print(sumArray([1, 2, 3, 4, 5])) // 15

Да, это работает.

Да, это выглядит «функционально» и «чисто».

Но если бы я добавил это в запрос на слияние, я гарантирую, что мой рецензент спросил бы меня, всё ли у меня в порядке дома.

Шаг 3: вложенные циклы = вложенная рекурсия

В обычном Swift вложенный цикл — это мило и безобидно:

for i in 1...3 {
    for j in 1...3 {
        print("(\(i), \(j))")
    }
}

А с рекурсией?

func nestedLoop(_ i: Int, _ maxI: Int, _ j: Int, _ maxJ: Int) {
    if i > maxI { return }
    if j > maxJ {
        nestedLoop(i + 1, maxI, 1, maxJ)
        return
    }
    print("(\(i), \(j))")
    nestedLoop(i, maxI, j + 1, maxJ)
}

Да, это работает. Но читать это — всё равно что смотреть на код, написанный разработчиком, который слишком долго сидел взаперти в подвале. На этом этапе даже автозаполнение Xcode начало колебаться, прежде чем что-либо предлагать.

Шаг 4: строки — почему бы и нет?

Мне понравились массивы. Потом я попробовал рекурсию со строками. Обычный способ переворачивания строки с помощью цикла:

let str = "hello"
var reversed = ""

for char in str {
    reversed = String(char) + reversed
}
print(reversed) // "olleh"

С помощью рекурсии:

func reverseString(_ str: String) -> String {
    if str.isEmpty { return "" }
    let firstChar = String(str.first!)
    let rest = String(str.dropFirst())
    return reverseString(rest) + firstChar
}

print(reverseString("hello")) // "olleh"

Этот вариант меня действительно порадовал. Он чистый. Он элегантный. И… он в 10 раз медленнее, чем версия с циклом.

Но, по крайней мере, на бумаге он выглядит хорошо.

Шаг 5: сортировка (сложный способ)

Знаете, что происходит, когда вы слишком глубоко погружаетесь в рекурсию?

Вы начинаете думать: «А что, если я реализую сортировку таким же образом?»

Обычный способ:

let numbers = [5, 3, 1, 4, 2]
let sorted = numbers.sorted()
print(sorted)

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

func mergeSort(_ numbers: [Int]) -> [Int] {
    if numbers.count <= 1 { return numbers }
    let mid = numbers.count / 2
    let left = mergeSort(Array(numbers[..<mid]))
    let right = mergeSort(Array(numbers[mid...]))
    return merge(left, right)
}

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    if left.isEmpty { return right }
    if right.isEmpty { return left }
    
    if left[0] < right[0] {
        return [left[0]] + merge(Array(left.dropFirst()), right)
    } else {
        return [right[0]] + merge(left, Array(right.dropFirst()))
    }
}
print(mergeSort([5, 3, 1, 4, 2]))

Красиво? Да. Излишне, учитывая, что метод .sorted() уже существует? Безусловно.

Но к этому моменту я уже потерял контроль над своей жизнью.

Шаг 6: обход иерархии представлений

Этот шаг действительно практичен. Представления UIKit образуют древовидную структуру. Рекурсивный обход? Это имеет смысл.

func printSubviews(of view: UIView) {
    for subview in view.subviews {
        print(subview)
        printSubviews(of: subview)
    }
}

Но помните — никаких циклов:

func printSubviewsRecursively(_ view: UIView, _ index: Int = 0) {
    if index >= view.subviews.count { return }
    let subview = view.subviews[index]
    print(subview)
    printSubviewsRecursively(subview)
    printSubviewsRecursively(view, index + 1)
}

Это работает, но какой ценой? На этом этапе мой проект напоминал неудачный экзамен по рекурсии в рамках курса CS101.

Первые трещины

Замена простых циклов была увлекательной. Но вскоре начали появляться трещины.

Проблема №1: ошибки переполнения стека повсюду

Если вы забудете базовый случай, рекурсия вас не простит.

func infiniteRecursion(_ n: Int) {
    print(n)
    infiniteRecursion(n + 1)
}
infiniteRecursion(1)

Это не функция — это обратный отсчет до сбоя из-за переполнения стека.

Я вызывал его так много раз, что «EXC_BAD_ACCESS» стало восприниматься не как ошибка, а как особенность.

Проблема №2: резкое падение производительности

Циклы в Swift работают невероятно быстро.

Рекурсивные вызовы? Не так быстро.

Я попытался обрабатывать большие массивы, и вдруг вентилятор моего MacBook зазвучал как Boeing 747, готовящийся к взлету.

Код работал… но ценой достоинства моего ноутбука.

Проблема №3: ​​отладка стала кошмаром

Точки останова в циклах? Легко. Точки останова в рекурсии? Удачи.

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

Проблема №4: читабельность умерла

Попытайтесь понять этот фрагмент:

func filterEven(_ numbers: [Int], _ index: Int = 0, _ result: [Int] = []) -> [Int] {
    if index == numbers.count { return result }
    let newResult = numbers[index] % 2 == 0 ? result + [numbers[index]] : result
    return filterEven(numbers, index + 1, newResult)
}

Вместо этого:

let evens = numbers.filter { $0 % 2 == 0 }

Реакция моих товарищей по команде:

• Почему… зачем ты это сделал?
• Ты что, издеваешься над нами?
• Кто тебя обидел?

Неожиданные победы

Но не всё было так уж плохо. На самом деле, я добился нескольких неожиданных успехов.

1. Рекурсивное мышление улучшило мои навыки работы с алгоритмами

Обход деревьев, метод «разделяй и властвуй», метод обратного поиска… рекурсия — это их естественный язык. Заставляя себя использовать рекурсию повсюду, я начал мыслить рекурсивно, что на самом деле помогло мне быстрее решать алгоритмические задачи.

2. Хвостовая рекурсия = скрытая суперсила

Swift поддерживает оптимизацию хвостовой рекурсии. Если вы тщательно пишете свои рекурсивные функции, компилятор «под капотом» может преобразовать их в эффективные циклы.

Пример:

func factorial(_ n: Int, _ acc: Int = 1) -> Int {
    if n == 0 { return acc }
    return factorial(n - 1, n * acc)
}

Этот вариант не взорвёт ваш стек.

3. Ценность циклов

После недели таких экспериментов я кое-что понял: циклы не скучны. Циклы милосердны. Циклы прекрасны.

Что я узнал

1. Рекурсия — мощный инструмент. Она лежит в основе множества алгоритмов.
2. Но циклы существуют не просто так. Они эффективны, читаемы и упрощают жизнь.
3. Использовать рекурсию повсюду — это как есть суп палочками. Да, это возможно. Нет, не стоит.

Заключительные мысли

Глубоко ли я изучил рекурсию? Да. Повторил бы я этот эксперимент? Только если бы я возненавидел своих товарищей по команде.

Если вы вынесете из этой истории что-то одно, пусть это будет следующее:

Знайте рекурсию. Уважайте рекурсию. Но ради всего святого, не заменяйте ею свои циклы.

Если, конечно, вам не доставляет удовольствия наблюдать за тем, как ваш код медленно саморазрушается.

Источник