Что такое рекурсия, какие у неё достоинства и недостатки, и какими способами можно избавиться от рекурсии в реализации?

Question

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

YeaHub · Accepted Answer

Рекурсия часто используется для описания задач, которые естественно делятся на более простые версии самих себя.ОпределениеОпределение: Рекурсия — это подход, при котором функция решает задачу, вызывая саму себя с более простыми входными данными, пока не будет достигнуто базовое условие.Из чего состоит рекурсивная функцияЛюбая корректная рекурсия включает:Базовый случай — условие, при котором рекурсивные вызовы прекращаютсяРекурсивный шаг — переход к более простой подзадачеПример факториала:def factorial(n):
    if n == 0:        # базовый случай
        return 1
    return n * factorial(n - 1)  # рекурсивный шаг
Достоинства рекурсииРекурсия удобна в задачах со вложенной структурой:Деревья и графыРазбор выраженийАлгоритмы «разделяй и властвуй»Плюсы:Код часто короче и читаемееЛогика близка к математическому описаниюНедостатки рекурсииРекурсия имеет и серьёзные минусы:Каждый вызов занимает место в стекеВ Python есть ограничение глубины рекурсии (RecursionError)Иногда сложнее отлаживатьКак избавиться от рекурсииКогда рекурсия становится проблемой, есть несколько подходов.1) Использовать циклМногие рекурсивные алгоритмы легко переписываются в итеративные:def factorial_iter(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result
2) Использовать собственный стекПодходит для обхода деревьев или графов:stack = [root]
while stack:
    node = stack.pop()
    # обработка node
    # добавление детей в stack
3) Хвостовая рекурсия (ограниченно)В Python она не оптимизируется, но иногда упрощает логику:def fact_tail(n, acc=1):
    if n == 0:
        return acc
    return fact_tail(n - 1, acc * n)
ВыводРекурсия удобна для задач с естественной вложенной структурой.В Python для больших входных данных чаще используют итеративные решения или собственный стек.