Изменения

'''Рекуррентная формула''' (англ. ''Recurrence relation'') — формула вида <tex>a_n=f(n, a_{n-1}, a_{n-2}, \dots, a_{n-p} ) </tex>, выражающая каждый член последовательности <tex>a_n</tex> через <tex>p</tex> предыдущих членов и возможно номер члена последовательности <tex>n</tex>.

Во многих задачах полезно знать, есть ли у рекурсивной функции нерекурсивная или как еще говорят «замкнутая» замкнутая (англ. ''Closed-form'') форма, т.е. получение <tex>f(n)</tex> в виде аналитически заданной функции. Например, рекурсивная функция, описывающая сумму чисел натурального ряда:

может быть переведена в замкнутую форму: <tex>f = \dfrac{n(n+1)}{2}</tex>. Для этого можно использовать метод производящих функций(англ. ''Generating Function Method'').