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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Примеры[править | править вики-текст]

  • Значение интеграла \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}.
Чтобы определить коэффициенты 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)}.
где R — радиус описанной окружности.

Приложения[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

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