Численный анализ изобилует примерами использования рекурсий: решение СЛАУ методом исключения Гаусса и любым из итерационных методов; большинство методов интегрирования обыкновенных дифференциальных уравнений; многие методы решения дифференциальных уравнений в частных производных.
Рекурсия, по своей сути, задает последовательность вычислений и, поэтому, представляет собой определенную проблему для распараллеливания.
Ограничимся рассмотрением линейных рекурсий первого порядка

 (1)

где - заданные константы. Положим, что (этого легко добиться, если принять ). В этом предположении информационные связи рекурсии (1) имеют вид, представленный на рис. 1.
Рис. 1.  Структура информационных связей рекурсии (1): n=4.
Алгоритм параллельного каскадного суммирования.
Положим, что . В этом случае формула (1) представляет собой рекуррентную запись алгоритма суммирования чисел .
Структура информационных связей алгоритма параллельного каскадного суммирования для случая представлена на рис. 2.
Алгоритм каскадного суммирования позволяет получить наряду с величиной все промежуточные величины . Если необходимо только значение величины , то достаточно выполнить только те сложения, которые выделены на рис. 2. В этом случае алгоритм превращается в алгоритм сдваивания (см. параграф 2).
Легко видеть, что высота ЯПФ алгоритма каскадного суммирования равна , а ширина каждого из его ярусов ЯПФ равна . Отметим (еще раз), что алгоритм увеличивает общее количество операций с ой до .
Рис. 2.  Структура информационных связей алгоритма каскадного суммирования для случая: n=8.
Алгоритм циклической редукции.
Положим теперь, что 1, 1,...,1.
Основная идея алгоритма циклической редукции заключается в объединении смежных членов рекурсии таким образом, чтобы получить соотношение между членами рекурсии , . В результате получается новая линейная рекурсия с числом членов , связывающая каждую вторую переменную исходной рекурсии. В этой новой рекурсии опять объединим смежные члены – получим рекурсию с числом членов , связывающую каждую четвертую переменную исходной рекурсии. И.т.д. После редукций получим формулу для вычисления .
Рассмотрим описанную схему более детально.
Редукция 1. Из (1) следует, что . Подставив это выражение в (1), получим линейную рекурсию первого порядка между перемежающимися членами исходной последовательности


где =, =+.
Редукция 2. По той же схеме из предыдущей рекурсии получим линейную рекурсию первого порядка между каждым четвертым членом исходной рекурсии


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

 (2)

где Если формуле (2) индексы выходят за диапазон , то соответствующую компоненту рекурсии (2) следует положить равной нулю.
Редукция n. По рассмотренной схеме из рекурсии получим


Таким образом, в соответствие с алгоритмом циклической редукции вычисление рекурсии сводится к вычислению коэффициентов Вычисление этих коэффициентов производится с помощь параллельного каскадного суммирования (см. рис. 3, рис. 4).
Рис. 3.  Схема каскадного суммирования при вычислении коэффициентов aj(k). Показаны только фактически используемые коэффициенты. n=8.
Высота ЯПФ алгоритма вычисления коэффициентов с помощью каскадного суммирования равна , а ширина ярусов изменяется от до .
Высота ЯПФ алгоритма вычисления коэффициентов с помощью каскадного суммирования равна , а ширина ярусов изменяется от до .
Алгоритм сдваивания.
Исходная рекурсия (1), очевидно, равносильна равенству


и, следовательно, может быть записана в виде

 (3)

Для вычисления произведения (3) можно использовать алгоритм сдваивания.
Рис. 4.  Схема каскадного суммирования при вычислении коэффициентов dj(k). n=8.
Утверждение. Методом сдваивания линейная рекурсия может быть вычислена на процессорах PRAM за время .
Примечание 1
Метод сдваивания может быть использован для вычисления рекурсии -го порядка за время .