Что значит "рекуррентная формула"

РЕКУРРЕНТНАЯ ФОРМУЛА (формула приведения) формула, связывающая значения p + 1 соседних членов uk, uk-1,..., uk-p (k ? p + 1) некоторой последовательности {un} (n = 1, 2,...): uk = f(k, uk-1,..., uk-p). Рекуррентная формула позволяет шаг за шагом определить любой член последовательности, если известны p первых ее членов u1, u2,..., up.

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

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

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

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

2. Пусть

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

   .

   Это ≈ Р. ф., сводящая вычисление In к вычислению /0 или l1 в зависимости от чётности n.

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

   .

Рекуррентная формула — формула вида a = f(n, a, a, …, a), выражающая каждый член последовательности a через p предыдущих членов и возможно номер члена последовательности n.

Общая проблематика вычислений с использованием рекуррентных формул является предметом теории рекурсивных функций .

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