Значение РЕКУРРЕНТНАЯ ФОРМУЛА в Большой советской энциклопедии, БСЭ

Что такое РЕКУРРЕНТНАЯ ФОРМУЛА

формула (от лат. recurrens, родительный падеж recurrentis - возвращающийся), формула приведения, формула, сводящая вычисление n- го члена какой-либо последовательности (чаще всего числовой) к вычислению нескольких предыдущих её членов. Обычно эти члены находятся в рассматриваемой последовательности 'недалеко' от её n -го члена, число их от n не зависит, а n- й член выражается через них достаточно просто. Однако возможны Р. ф. и более сложной структуры. Общая проблематика рекуррентных вычислений является предметом теории рекурсивных функций .

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

j0 0, j1 1,jn+2 jn+1 + jn ( n > 0)

Последняя из них является Р. ф.; она позволяет вычислить j2, j3 и дальнейшие члены этой последовательности.

2) Пусть

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

.

Это - Р. ф., сводящая вычисление I nк вычислению /0 или l 1 в зависимости от чётности n.

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

.

Большая советская энциклопедия, БСЭ.