РЕКУРРЕНТНАЯ ФОРМУЛА

РЕКУРРЕНТНАЯ ФОРМУЛА (от лат. recurrcns,
род. падеж recurrentis - возвращающийся), формула приведения, формула,
сводящая вычисление га-го члена к.-л. последовательности (чаще всего числовой)
к вычислению нескольких предыдущих её членов. Обычно эти члены находятся
в рассматриваемой последовательности "недалеко" от её n-го члена, число
их от п не зависит, а n-й член выражается через них достаточно просто.
Однако возможны Р. ф. и более сложной структуры. Общая проблематика рекуррентных
вычислений является предметом теории рекурсивных функций.

Примеры. 1) Последовательность ф- т. н. чисел Фибоначчи - задаётся формулами:

ф= ф 0).

Последняя из них является Р. ф.; она позволяет
вычислить ф

2) Пусть

Нетрудно показать, что для n>= 2 выполняется
соотношение

Это - Р. ф., сводящая вычисление Iвычислению Iп.

Р. ф. обычно даёт удобную вычислительную
схему для нахождения членов последовательности друг за другом. Однако иногда,
исходя из Р. ф., стремятся получить "явное" выражение для n-го члена последовательности,
описываемой этой Р. ф. Так, в случае чисел Фибоначчи

А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я