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

Для новичков:

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

Пример рекурсивной функции для вычисления факториала:

def factorial(n):
    if n == 0:  # базовый случай
        return 1
    else:
        return n * factorial(n - 1)  # рекурсивный вызов

print(factorial(5))  # Выведет 120

В этом примере, чтобы вычислить факториал числа `5, функция вызывает саму себя с аргументом `4, затем `3, и так далее, пока не дойдет до `0, что является базовым случаем.

Для опытных:

Рекурсия часто используется в алгоритмах, таких как сортировка и поиск. Например, алгоритм QuickSort использует рекурсивный подход для сортировки массивов:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

В этом примере `quicksort` разбивает массив на более мелкие части (левую, среднюю и правую) и рекурсивно сортирует их.

Несмотря на мощь рекурсии, следует помнить о её недостатках. Каждый рекурсивный вызов добавляет новый уровень на стек, и если уровень рекурсии слишком велик, это может привести к переполнению стека. Поэтому для больших входных данных лучше использовать итеративные подходы, если это возможно.

Использование рекурсии делает код более выразительным и может значительно упрощать решение задач, которые могут быть описаны рекурсивно.