Рекурсия вместо циклов

В Haskell нет for и while. Повторение выражается рекурсией — функцией, которая вызывает саму себя.

Рекурсия пугает, пока вы не увидите рецепт: один случай, который останавливает (базовый), и один, который сводит задачу к меньшей (рекурсивный). Всё.

Циклы — это про изменяемый счётчик, который растёт, пока условие истинно. Но в чистом языке нет изменяемых счётчиков. Значит, повторение строится иначе: функция решает маленький кусочек задачи и зовёт себя для остатка.

Рецепт из двух случаев

Любая рекурсивная функция состоит из двух частей. Базовый случай — когда задача настолько мала, что ответ очевиден. Рекурсивный случай — когда мы делаем шаг и зовём себя для уменьшенной задачи.

factorial :: Integer -> Integer
factorial 0 = 1                       -- базовый случай
factorial n = n * factorial (n - 1)   -- рекурсивный

len :: [a] -> Int
len []     = 0                        -- базовый
len (_:xs) = 1 + len xs               -- рекурсивный

factorial 3
= 3 * factorial 2
= 3 * (2 * factorial 1)
= 3 * (2 * (1 * factorial 0))
= 3 * (2 * (1 * 1))
= 6

Главное правило: рекурсивный вызов обязан получать «меньший» аргумент, иначе функция не остановится. Здесь n - 1 и xs (хвост короче списка) приближают нас к базовому случаю.

Аккумуляторы

Иногда удобно накапливать результат в дополнительном аргументе — аккумуляторе. Это часто эффективнее:

sumAcc :: [Int] -> Int -> Int
sumAcc []     acc = acc
sumAcc (x:xs) acc = sumAcc xs (acc + x)

total :: [Int] -> Int
total xs = sumAcc xs 0

Аккумулятор несёт «промежуточный итог» сквозь вызовы. Когда список кончился, в нём готовый ответ.

На Python та же мысль: рекурсия буквально заменяет цикл.

# Та же идея на Python: рекурсия вместо цикла
def factorial(n):
    if n == 0:
        return 1                 # базовый случай
    return n * factorial(n - 1)  # рекурсивный

print(factorial(5))   # 120

# С аккумулятором
def sum_acc(xs, acc=0):
    if not xs:
        return acc
    return sum_acc(xs[1:], acc + xs[0])

print(sum_acc([1, 2, 3, 4]))   # 10

От страха к рецепту

Рекурсия пугает, пока её представляют как «функцию, бесконечно прыгающую саму в себя». Стоит переключиться на рецепт «база плюс шаг» — и страх уходит. Секрет в доверии: когда вы пишете рекурсивный случай, считайте, что функция уже умеет решать задачу на размер меньше, и просто воспользуйтесь этим результатом. Не нужно держать в голове весь стек вызовов — достаточно убедиться в двух вещах: база даёт правильный ответ для самого маленького входа, а шаг честно приближает к базе. Со временем вы заметите повторяющиеся узоры: «обработать голову и рекурсивно — хвост» встречается так часто, что его вынесли в библиотечные функции вроде map и foldr. Поэтому ручную рекурсию стоит освоить как фундамент, но в реальном коде предпочитать готовые свёртки — они выражают те же узоры короче и безопаснее.

Как это мыслить

Доверьтесь рекурсии. Когда пишете рекурсивный случай, считайте, что функция уже умеет решать задачу поменьше — и просто воспользуйтесь этим. Не пытайтесь «прокрутить» все вызовы в голове; задайте базовый случай, задайте шаг — и вычисление сложится само.

Полезно знать про одну важную разновидность — хвостовую рекурсию, когда рекурсивный вызов стоит самым последним действием функции. Аккумуляторный вариант суммы как раз такой: результат целиком вычисляется в накопителе, и после рекурсивного вызова делать уже нечего. Такую рекурсию компилятор может выполнять без роста стека, фактически превращая её в цикл под капотом. Понимать это полезно, но в повседневном коде ещё важнее другое: подавляющее большинство рекурсивных задач уже выражено в стандартной библиотеке через map, filter, foldr и foldl'. Поэтому ручную рекурсию стоит освоить, чтобы понимать механику, но в реальном проекте предпочитать готовые комбинаторы — они короче, безопаснее и сразу сообщают читателю о ваших намерениях.

Частые ошибки

• Забыть базовый случай. Тогда рекурсия бесконечна и программа зависнет.
• Рекурсивный вызов не уменьшается. Если аргумент не «меньше», остановки не будет.
• Глубокая нехвостовая рекурсия на огромных данных. Может расти память — спасает аккумулятор или библиотечные свёртки.

Best practices

• Сначала напишите базовый случай — он якорь всей функции.
• Убедитесь, что каждый рекурсивный вызов приближает к базе.
• Часто вместо ручной рекурсии лучше взять map, filter, foldr — о них в следующих разделах.

Итог. Циклы заменяет рекурсия: базовый случай останавливает, рекурсивный сводит задачу к меньшей. Аккумулятор помогает копить результат. Освойте этот рецепт — и повторение в Haskell перестанет быть загадкой.