302
правки
Изменения
Нет описания правки
Во многих задачах полезно знать, есть ли у рекурсивной функции нерекурсивная или как еще говорят замкнутая форма (англ. ''Closed-form''), то есть получение <tex>f(n)</tex> в виде аналитически заданной функции. Например, рекурсивная функция, описывающая сумму чисел натурального ряда:
<tex> f = \begin{cases} f(0)=0; \\ f(n) = n + f(n-1),\quad n > \gt 0 \end{cases}</tex>
может быть переведена в замкнутую форму: <tex>f = \dfrac{n(n+1)}{2}</tex>. Для этого можно использовать метод производящих функций (англ. ''Generating Function Method'').
