Рекуррентные соотношения и их решение

Учимся описывать последовательности через предыдущие члены и находить для них замкнутые формулы.

Рекуррентное соотношение — формула, выражающая член последовательности через один или несколько предыдущих членов.

Зачем нужны рекурренты

Рекуррентные соотношения — это математика рекурсии. Время работы рекурсивного алгоритма, количество шагов «разделяй и властвуй», число способов что-то составить, рост популяции — всё описывается рекуррентами. Когда вы анализируете сложность сортировки слиянием и пишете T(n) = 2·T(n/2) + n — это рекуррентное соотношение. Умение его «решить» (найти явную формулу) — это умение сказать, насколько быстр алгоритм, не запуская его.

Что такое рекуррента

Рекуррента задаёт последовательность в два приёма: начальные условия (первые члены) и правило, как получить следующий член из предыдущих. Самый знаменитый пример — числа Фибоначчи:

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

Каждое число — сумма двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13, 21... Рекуррента — это «рецепт»: чтобы узнать F(10), нужно знать F(9) и F(8), для которых, в свою очередь, нужны предыдущие. Прямой расчёт «в лоб» по определению — это рекурсия, и она может быть медленной (экспоненциальной), если не запоминать промежуточные результаты.

Считаем рекурренту на Python

Сравним наивную рекурсию с запоминанием (мемоизацией) — и убедимся, что результат тот же.

# Числа Фибоначчи с мемоизацией (быстро)
def fib(n, memo={0: 0, 1: 1}):
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

print("Первые 11 чисел Фибоначчи:", [fib(i) for i in range(11)])

# Формула Бине (замкнутый вид через золотое сечение)
phi = (1 + 5 ** 0.5) / 2
binet = round((phi ** 10 - (-1 / phi) ** 10) / 5 ** 0.5)
print("F(10) по рекурренте:", fib(10))
print("F(10) по формуле Бине:", binet)

Вывод:

Первые 11 чисел Фибоначчи: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
F(10) по рекурренте: 55
F(10) по формуле Бине: 55

Удивительно: у чисто целочисленной последовательности Фибоначчи есть замкнутая формула с иррациональным золотым сечением φ — формула Бине. И она даёт точное целое 55. Откуда такая формула берётся? Её даёт метод характеристического уравнения, к которому мы сейчас перейдём.

Линейные рекурренты и характеристическое уравнение

Линейная однородная рекуррента второго порядка имеет вид a(n) = c1·a(n-1) + c2·a(n-2). Для её решения есть красивый рецепт:

Ищем решение в виде a(n) = x^n и подставляем. После сокращения получаем характеристическое уравнение: x² = c1·x + c2, то есть x² − c1·x − c2 = 0.
Находим его корни x1 и x2 (как обычное квадратное уравнение).
Общее решение — a(n) = A·x1^n + B·x2^n (если корни разные). Константы A и B находим из начальных условий.

Почему это работает? Потому что рекуррента линейна: сумма двух решений — снова решение. Степенные функции x^n — «собственные» для такого правила, а их комбинацией можно подогнать любые начальные условия.

Полный разбор на примере

Решим a(n) = a(n-1) + 2·a(n-2) с условиями a(0)=2, a(1)=1.

Характеристическое уравнение: x² = x + 2, то есть x² − x − 2 = 0. Раскладываем: (x−2)(x+1) = 0. Корни: x1 = 2, x2 = −1.
Общий вид: a(n) = A·2^n + B·(−1)^n.
Подставляем условия: при n=0 → A + B = 2; при n=1 → 2A − B = 1. Складывая, получаем 3A = 3, значит A = 1, B = 1.
Ответ: a(n) = 2^n + (−1)^n.

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

def a_closed(n):
    return 2 ** n + (-1) ** n        # найденная формула

def a_rec(n):
    seq = [2, 1]                     # a(0)=2, a(1)=1
    for i in range(2, n + 1):
        seq.append(seq[i - 1] + 2 * seq[i - 2])
    return seq[n]

print("n:      ", list(range(8)))
print("рекур:  ", [a_rec(n) for n in range(8)])
print("формула:", [a_closed(n) for n in range(8)])
print("Совпадают для n=0..19:", all(a_rec(n) == a_closed(n) for n in range(20)))

Вывод:

n:       [0, 1, 2, 3, 4, 5, 6, 7]
рекур:   [2, 1, 5, 7, 17, 31, 65, 127]
формула: [2, 1, 5, 7, 17, 31, 65, 127]
Совпадают для n=0..19: True

Замкнутая формула 2^n + (−1)^n идеально воспроизводит последовательность, заданную рекуррентой. Это и есть «решить рекурренту»: вместо того чтобы считать все предыдущие члены, мы подставляем n в формулу и получаем ответ за один шаг.

Индукция в деле: доказываем корректность цикла

Покажем, ради чего программисту индукция, на живом примере. Пусть мы суммируем числа от 1 до n циклом, и хотим строго доказать, что после цикла в переменной лежит правильная сумма. Секрет — в инварианте цикла: утверждении, которое верно перед каждой итерацией.

def suma(n):
    s = 0
    for k in range(1, n + 1):
        # ИНВАРИАНТ: перед обработкой k в s лежит сумма 0+1+...+(k-1)
        s += k
    return s

print("suma(100) =", suma(100), "| формула n(n+1)/2 =", 100 * 101 // 2)

Вывод:

suma(100) = 5050 | формула n(n+1)/2 = 5050

Доказательство инварианта — это индукция по итерациям. База: до цикла s = 0 — сумма пустого набора, верно. Шаг: если перед итерацией в s сумма 0+...+(k−1), то после s += k там 0+...+k — инвариант сохранился. Когда цикл закончится, k пройдёт до n, и в s окажется полная сумма. Вот так индукция превращается из абстрактного метода в инструмент, доказывающий, что ваш код действительно делает то, что задумано, — а не просто «вроде работает на тестах».

Типичные ошибки

Забыть начальные условия. Рекуррента без начальных значений задаёт не одну последовательность, а целое семейство. Условия «закрепляют» константы A и B.
Перепутать знаки в характеристическом уравнении. Для a(n) = c1·a(n-1) + c2·a(n-2) уравнение это x² − c1·x − c2 = 0 (коэффициенты переносятся со знаком минус).
Считать наивную рекурсию по рекурренте быстрой. Прямой рекурсивный расчёт Фибоначчи без мемоизации экспоненциально медленный — он пересчитывает одно и то же много раз.

Итог

Рекуррента задаёт член через предыдущие плюс начальные условия.
Числа Фибоначчи — канонический пример: F(n) = F(n-1) + F(n-2).
Линейные рекурренты решают через характеристическое уравнение: корни дают замкнутую формулу A·x1^n + B·x2^n.
Замкнутая формула считает любой член за один шаг, без перебора предыдущих.