Что такое рекурсия в программировании?

Question

Что такое рекурсия в программировании?

Тип вопроса: Other Вероятность: 27% Категория: AQA / Automation

Ответ

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

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

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

Пример вычисления факториала на Python:

def factorial(n: int) -> int:
    if n <= 1:          # Базовый случай
        return 1
    return n * factorial(n - 1)  # Рекурсивный шаг

print(factorial(5))  # Вывод: 120

Практические применения:

Обход древовидных структур (файловая система, DOM, AST)
Решение задач типа «Ханойские башни» или генерации комбинаций
Алгоритмы «разделяй и властвуй» (быстрая сортировка, бинарный поиск)

Критические ограничения:

Переполнение стека при глубокой рекурсии (например, factorial(10000))
Накладные расходы на вызовы функций и потребление памяти
Сложность отладки по сравнению с итеративными решениями

Оптимизация: Для устранения ограничений используйте:

Хвостовую рекурсию (где компилятор может оптимизировать вызовы)
Мемоизацию (кэширование результатов через @lru_cache)
Итеративные алгоритмы для задач с большой глубиной рекурсии.

Ответ 18+ 🔞

Вот, смотри, объясняю тебе про рекурсию, как будто я тебе в баре на салфетке рисую, а ты уже пятый стакан кофе выдуваешь.

Представь, что ты — функция. И тебе надо посчитать, сколько будет, например, пять факториал. Ты такой: «Окей, 5! — это 5 умножить на 4!». А чтобы посчитать 4!, тебе надо знать, сколько будет 4 умножить на 3! И так далее, пока не дойдёшь до единички. Вот это, блядь, и есть рекурсия — когда функция сама себя вызывает, чтобы решить кусок задачи, пока не упрётся в какой-то простой, ебаный, базовый случай.

Из чего эта штука состоит, чтобы не сломаться:

Базовый случай. Это твой спасательный круг, стоп-кран, хуй с горы. Условие, при котором ты говоришь: «Всё, пиздец, дальше не иду, возвращаю ответ». Без него ты улетишь в бесконечный цикл вызовов самого себя, пока компьютер не скажет «накрылся медным тазом» от переполнения стека.
Рекурсивный шаг. А вот тут-то и магия. Ты берёшь свою здоровенную, страшную задачу, откусываешь от неё маленький кусочек, а оставшуюся биг-мак-проблему суёшь... самому себе же, но чуть попроще. И так раз за разом.

Смотри, как это выглядит в коде, на примере факториала:

def factorial(n: int) -> int:
    if n <= 1:          # Базовый случай: факториал 1 это 1, дальше не паримся
        return 1
    return n * factorial(n - 1)  # Рекурсивный шаг: n! = n * (n-1)!

print(factorial(5))  # Вывод: 120

Работает это так: factorial(5) зовёт factorial(4), тот зовёт factorial(3), и так до единицы. А потом, как цепочка домино, всё схлопывается назад, возвращая результаты.

Где эта хуйня реально полезна?

Когда надо обойти что-то древовидное. Файловую систему, где папки в папках, или HTML-страницу (DOM). Идеально, ёпта.
Классические головоломки вроде «Ханойских башен» — там без рекурсии просто пиши пропало.
Умные алгоритмы типа «быстрой сортировки», которые работают по принципу «разделяй и властвуй».

Но не всё так гладко, есть подводные, блядь, камни:

Переполнение стека. Это главная страшилка. Если рекурсия слишком глубокая (попробуй factorial(100000)), стек вызовов, где хранятся твои «несделанные делá», просто лопнет. И тебе покажут большую, жирную ошибку.
Тормоза и прожорливость. Каждый вызов функции — это затраты. Память, время. Иногда цикл (for, while) будет в разы эффективнее.
Отладка. Попробуй отследить, что происходит на 532-м вызове функции, которая вызывает саму себя. Удивление пиздец, волнение ебать.

Как с этим бороться, если очень надо?

Хвостовая рекурсия. Это такой особый вид, когда рекурсивный вызов — последнее, что делает функция. Умные компиляторы (но не стандартный Python, увы!) могут это оптимизировать, превратив в цикл.
Мемоизация. Проще говоря, кэширование. Если функция с одними и теми же аргументами вызывается много раз, зачем считать заново? Запоминаем результат и вуаля. В Python для этого есть декоратор @lru_cache.
Итеративный подход. Иногда надо просто признать — рекурсия здесь не королева. И переписать алгоритм на обычные циклы. Это часто бывает самым здравым решением, чтобы не ебать себе мозг и память компа.

Короче, инструмент мощный, но как молоток: если гвоздь — то в самый раз, а если шуруп — то можно и по пальцам получить, да и стену разворотить.