Некоторые методы, которые используются для анализа и решения рекуррентных последовательностей:

• Метод подстановки. 34 Предполагают решение, а затем используют математическую индукцию, чтобы доказать, правильное ли это предположение. 3
• Метод рекуррентного дерева. 3 Рисуют дерево повторений, вычисляют время, затраченное на каждый уровень дерева, и суммируют работу, проделанную на всех уровнях. 3
• Метод декомпозиции (или метод разбиения). 4 Исходную задачу разбивают на подзадачи, которые решаются рекурсивно, а затем результаты объединяют. 4
• Метод математической индукции. 5 Начальное значение вычисляемой величины — база индукции, а рекуррентное соотношение — шаг индукции. 5
• Метод производящих функций. 5
• Методы решения однородных и неоднородных рекуррентных соотношений. 5

Для обработки рекуррентных последовательностей также используют методы, основанные на свойстве рекуррентности, например, рекуррентный опознаватель по методу Р. Уорда и метод безошибочного «зачётного» участка. 2