Рекурсивные алгоритмы

Пусть известно, что F(1) = 1, а каждое следующее значение получается по правилу F(n) = 2·F(n − 1) + 1 при n > 1. Формула сама по себе ничего не считает — чтобы найти F(n), сначала нужно знать F(n − 1). Найдём F(5), поднимаясь от того, что уже известно.

Рекурсивное определение работает только потому, что в нём одновременно есть два условия. Первое — начальное значение (его называют базовым случаем): F(1) = 1 просто дано, вычислять его не нужно. Второе — правило перехода: F(n) = 2·F(n − 1) + 1 при n > 1, которое показывает, как получить следующее значение из предыдущего.

Работает это как ряд костяшек домино: F(1) — костяшка, которую толкнули вручную, а правило перехода — то, что заставляет каждую следующую костяшку падать от предыдущей. Без первого толчка (без базового случая) ни одна костяшка не упадёт, и цепочка F(5) → F(4) → F(3) → … никогда не остановится.

На первый взгляд определение через саму себя похоже на логический круг: чтобы найти F(5), нужно знать F(4), а чтобы найти F(4) — знать F(3), и так далее. Круга здесь на самом деле нет.

Раз F(1) известно без всяких вычислений, из него однозначно находится F(2). Раз известно F(2), точно так же находится F(3). Раз известно F(3) — находится F(4), и так далее для любого n. Каждое следующее значение опирается только на уже найденное, поэтому вся последовательность F(1), F(2), F(3), … определена целиком, без пропусков и без противоречий — тот же принцип, что и математическая индукция: база плюс шаг, работающий для любого n, задают значение сразу для всех n.

Ту же идею можно записать программой, где функция обращается сама к себе:

def F(n):    if n == 1:        return 1  # Базовый случай: значение уже известно    return 2 * F(n - 1) + 1  # Шаг: сначала находим F(n - 1) print(F(5))

Вызов F(5) не может сразу вернуть число — сначала нужно узнать F(4), для которого нужно F(3), и так далее, пока не будет достигнут базовый случай F(1). После этого каждый вызов возвращает своё значение туда, откуда был вызван, и подъём происходит в обратном порядке.

return делает две вещи одновременно: завершает текущий вызов и передаёт вычисленное число туда, откуда функция была вызвана. В строке return 2 * F(n - 1) + 1 выражение F(n - 1) — это не текст и не номер, а конкретное число, которое вернул вложенный вызов.

У рекурсивной записи есть практическая цена: каждый незавершённый вызов остаётся в стеке вызовов, ожидая результата вложенного. Для F(2024) это значит две тысячи с лишним вложенных вызовов одновременно — на Python это упирается в ограничение глубины рекурсии и завершается ошибкой ещё до того, как будет достигнут базовый случай:

def F(n):    if n == 1:        return 1    return n * F(n - 1) print(F(2024))  # RecursionError: превышена глубина рекурсии

В каждый момент нужно только последнее найденное значение, поэтому тот же результат надёжнее получить циклом, который перезаписывает одну переменную, ничего не откладывая в стек:

f = 1  # Начинаем с известного F(1) for n in range(2, 2025):    f = n * f  # Новое значение заменяет предыдущее print(f)

Общий шаблон для функции с одним предыдущим значением:

f = base_value for n in range(first_n, target + 1):    f = ...  # Формула через предыдущее значение f print(f)

Иногда следующее значение зависит не от одного, а от двух предыдущих: F(n) = F(n − 1) + F(n − 2). Тогда одного базового значения недостаточно — уже для F(3) нужны сразу F(2) и F(1), поэтому определение обязано задать оба сразу: F(1) = 2, F(2) = 3.

Если функцию с двумя предыдущими значениями записать рекурсивно, у неё появляется собственная проблема — не с глубиной, а с повторами:

def F(n):    if n == 1:        return 2    if n == 2:        return 3    return F(n - 1) + F(n - 2)

Вызов F(6) запускает F(5) и F(4). Но F(5), в свою очередь, снова запускает F(4) — то же самое значение считается заново, хотя уже вычислялось. При больших n количество повторных вычислений растёт очень быстро. Решение — не пересчитывать, а один раз сохранить каждое найденное значение, например списком:

target = 6F = [0] * (target + 1) # Два базовых значения нужны до первого шагаF[1] = 2F[2] = 3 for n in range(3, target + 1):    F[n] = F[n - 1] + F[n - 2]  # Сохраняем один раз print(F[target])

Хранить весь список не обязательно — для следующего значения нужны только два последних:

f_prev2, f_prev1 = 2, 3 for n in range(3, 7):    # Правая часть использует оба старых значения до присваивания    f_prev2, f_prev1 = f_prev1, f_prev1 + f_prev2 print(f_prev1)

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

Если аргумент огромный — 2024, 100 000 — а нужен не сам F(n), а отношение или разность двух соседних значений, считать всю последовательность необязательно. Обычно достаточно раскрыть только несколько последних шагов и что-то сократить.

Разные задания линии 16 сводятся к одному и тому же алгоритму: