Рекуррентная формула

Рекуррентная формула — формула вида $a_n=f(n, a_{n-1}, a_{n-2}, \dots, a_{n-p} )$, выражающая каждый член последовательности $a_n$ через p предыдущих членов.

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

Примеры

• Вычисление факториала натурального числа:

  $n!=(n-1)!\cdot n,$ причём $0!=1.$

• Вычисление чисел Фибоначчи задаётся формулами:

  $F_n = \begin{cases} 0, & n=0;\\ 1, & n=1; \\ F_{n-1} + F_{n-2}, & n\geqslant 2.\end{cases}$

• Значение интеграла $\textstyle I_n=\int\sin ^n x\,dx$ удовлетворяет рекуррентной формуле:

  $I_n=\frac{-\cos x\cdot \sin^{n-1} x}{n}+\frac{n-1}{n}I_{n-2}.$

• Решение дифференциального уравнения Бесселя $y'' +(1/x)y' +(1-\nu^2/x^2)y=0$ может быть записано в виде степенного ряда:

  $y=\sum\limits_{n=0}^{\infty}a_n x^{2n+\nu}.$

Чтобы определить коэффициенты $a_n$, достаточно установить, что $4n(n+\nu)a_n +a_{n-2}=0$ для всех n ⩾ 1. После чего сразу получается известный результат:

$a_n =\frac{(-1)^n a_0}{2^{2^n}n! (1+\nu) (2+\nu ) \cdots (n+\nu)}.$

• Длина стороны при удвоении числа сторон вписанного правильного многоугольника:

  $a_n=\sqrt{2R^2- 2R\sqrt{ R^2-\frac{a^2_{n-1}}{4}} }, \qquad n\ge 2,$

где R — радиус описанной окружности.

• Существует формула, выражающая общий член линейной рекуррентной последовательности через корни её характеристического многочлена. Например, для последовательности Фибоначчи такой формулой является формула Бине.

Приложения

Рекуррентные формулы используются для описания времени работы алгоритма, рекурсивно обращающегося к самому себе. В такой формуле время, требуемое для решения задачи объемом ввода n, выражается через время решения вспомогательных подзадач.^[1]

См. также

• Линейная рекуррентная последовательность
• Рекурсивная функция
• Рекурсия

Примечания

1. ↑ Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн Алгоритмы. Построение и анализ = Introduction To Algorithms / И. Красиков. — Издательский дом "Вильямс", 2005. — С. 79. — 1296 с.