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

---

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

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

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

Здесь ${\displaystyle n}$ — неотрицательные целые числа, ${\displaystyle f_{n}}$ — последовательность чисел, ${\displaystyle a_{1},a_{2},\ldots ,a_{r}}$ — постоянные числа, ${\displaystyle a_{r}\neq 0}$, ${\displaystyle \varphi (n)}$ — заданная функция от ${\displaystyle n}$.

---