Значение рекуррентных соотношений в информатике и анализе алгоритмов заключается в следующем:

• Анализ временной сложности. 1 Рекуррентные соотношения обеспечивают систематический способ выражения временной сложности рекурсивных алгоритмов. 1
• Обобщение алгоритмов типа «разделяй и властвуй». 1 Например, при оценке времени их выполнения. 2
• Определение состояния и переходов для динамического программирования. 1
• Построение длинной последовательности чисел. 3 Если нужен только последний член последовательности, заданной рекуррентным соотношением, то можно обойтись без таблиц и сэкономить память ЭВМ. 3

Основная теорема о рекуррентных соотношениях используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений, часто возникающих при анализе алгоритмов типа «разделяй и властвуй», например, при оценке времени их выполнения. 2