Алгоритмы. Рекурсия

По предыдущему посту я понял, чтобы объяснить более менее детально какую-либо тему, приходится расписывать все куда детальнее, чем во многих гайдах и обзорах. Поэтому посты по алгоритмам будут большие, но оно того стоит. Сегодня мы поговорим о рекурсии простым языком.

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

Для корректной работы любой рекурсивной функции необходимы два фундаментальных компонента. Во-первых, это базовый случай — условие остановки, которое предотвращает бесконечный цикл вызовов. Его можно сравнить с последней ступенькой лестницы: достигнув её, вы прекращаете движение. Во-вторых, требуется рекурсивный шаг — вызов функцией самой себя, но с изменёнными входными данными, которые должны гарантированно приближать выполнение к базовому случаю. Это подобно каждому следующему шагу вниз по лестнице, который сокращает оставшееся до низа расстояние.

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

def count_down(n):
    # Базовый случай: когда достигли 0, останавливаемся
    if n == 0:
        print("Готово!")
        return
    
    # Выводим текущее число
    print(n)
    
    # Рекурсивный шаг: вызываем функцию с n-1
    count_down(n - 1)

count_down(5)

Вывод этой программы будет последовательным:

5
4
3
2
1
Готово!

Внутри этого процесса происходит следующее: вызов count_down(5) приводит к выводу числа 5 и новому вызову count_down(4). Этот процесс вкладывается, подобно матрёшкам, пока вызов count_down(0) не достигнет базового случая, выведет "Готово!" и не начнёт возвращать управление обратно по цепочке предыдущих вызовов.

Классическим примером, раскрывающим суть рекурсивного мышления, является вычисление факториала числа n, обозначаемого как n!. По определению, факториал — это произведение всех натуральных чисел от 1 до n, при этом 0! и 1! равны 1 (вообще не так чтобы равны, просто принято такое равенство для удобства расчетов). Ключевое наблюдение здесь — рекурсивная природа операции: факториал любого числа n можно выразить через факториал меньшего числа, а именно n! = n * (n-1)!. Это и становится основой для алгоритма.

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

print(factorial(5))  # 120

# Для значения 3

factorial(3)
│
├─ factorial(2)  ← добавляется в стек
│  │
│  ├─ factorial(1)  ← добавляется в стек
│  │  └─ возвращает 1  ← снимается со стека
│  │
│  └─ возвращает 2  ← снимается со стека
│
└─ возвращает 6  ← снимается со стека

# Стек вызовов для factorial(3):

Шаг 1: [factorial(3)]
Шаг 2: [factorial(3), factorial(2)]
Шаг 3: [factorial(3), factorial(2), factorial(1)]
Шаг 4: [factorial(3), factorial(2)]  ← factorial(1) вернул результат
Шаг 5: [factorial(3)]  ← factorial(2) вернул результат
Шаг 6: []  ← factorial(3) вернул результат

Пошаговое выполнение функции для factorial(5) раскладывается в цепочку отложенных умножений: 5 * factorial(4), затем 5 * (4 * factorial(3)), и так далее, пока вычисление не дойдёт до базового случая factorial(1), который возвращает 1. После этого цепочка начинает сворачиваться, производя последовательные умножения: 2 * 1 = 2, 3 * 2 = 6, 4 * 6 = 24 и, наконец, 5 * 24 = 120.

Эта же логика применима ко множеству других задач. Например, для вычисления суммы всех чисел от 1 до n.

def sum_numbers(n):
    # Базовый случай
    if n == 0:
        return 0
    
    # Рекурсивный шаг
    return n + sum_numbers(n - 1)

print(sum_numbers(5))  # 15 (5+4+3+2+1)

Аналогично работает возведение числа в натуральную степень.