Рекуррентное соотношение — это уравнение, согласно которому n-й член последовательности чисел равен некоторой комбинации предыдущих членов. 1

Другими словами, это соотношение между элементами последовательности, в котором следующий элемент выражается через несколько предыдущих. 3

От других типов соотношений рекуррентное соотношение отличается тем, что выражает каждый элемент последовательности как функцию предыдущих. 1

В информатике рекуррентные соотношения также имеют фундаментальное значение при анализе алгоритмов. 1 Если алгоритм разработан таким образом, что он разбивает задачу на более мелкие подзадачи, время его выполнения описывается рекуррентным соотношением. 1

Ещё одно отличие рекуррентного соотношения от других типов соотношений в том, что оно должно быть определено для всех допустимых значений аргументов, поэтому должны быть определены значения функций при начальных значениях параметров. 2