Рекуррентные соотношения в математике применяют в различных областях и задачах. 1 Вот некоторые типичные области:

• Анализ алгоритмов. 1 Рекуррентные соотношения часто отражают временную сложность рекурсивных алгоритмов. 1 Например, алгоритм быстрой сортировки приводит к рекуррентному соотношению T(n) = 2T(n/2) + n. 1
• Динамическое программирование. 1 Многие решения динамического программирования основаны на рекуррентных соотношениях. 1 Например, с их помощью решают задачи о наибольшей общей подпоследовательности, о рюкзаке и другие. 1
• Задачи счёта. 1 Многие задачи счёта используют рекуррентные соотношения, например подсчёт количества двоичных деревьев с n узлами. 1 Эти задачи можно вывести рекурсивно, а затем решить для замкнутых решений. 1

Для решения рекуррентных соотношений применяют один из двух основных способов: метод производящих функций и метод характеристического уравнения. 3