WikiSort.ru - Не сортированное

Эту страницу предлагается объединить со страницей Рекуррентная формула. Пояснение причин и обсуждение — на странице Википедия:К объединению/27 апреля 2016. Обсуждение длится не менее недели (подробнее). Не удаляйте шаблон до подведения итога обсуждения.

Рекурси́вная фу́нкция (от лат. recursio — возвращение) — это числовая функция ${\displaystyle f(n)}$ числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения ${\displaystyle f(n)}$ на основе значений ${\displaystyle f(n-1),f(n-2),\ldots }$ , подобно рассуждению по индукции. Чтобы вычисление завершалось для любого ${\displaystyle n}$ , необходимо, чтобы для некоторых ${\displaystyle n}$ функция была определена нерекурсивно (например, для ${\displaystyle n=0,1}$ ).

Примеры

Пример рекурсивной функции, дающей n-ое число Фибоначчи:

${\displaystyle F={\begin{cases}F(0)=1;\\F(1)=1;\\F(n)=F(n-1)+F(n-2),\quad n>1.\end{cases}}}$

Руководствуясь этой записью, мы можем вычислить ${\displaystyle F(n)}$ для любого натурального n за конечное число шагов. Правда, по пути придётся дополнительно вычислить значения ${\displaystyle F(n-1),F(n-2),\ldots ,F(2)}$ .

Замкнутая форма

В связи с накладными расходами полезно знать, есть ли у рекурсивной функции нерекурсивная (замкнутая) форма.

Замкнутая форма может быть найдена не для всех рекурсивных функций (соотношений). Для некоторых из них найдены лишь приближенные замкнутые формы. Некоторые рекурсивные соотношения, такие как факториал, считаются элементарными математическими операциями.

Например, рекурсивная функция, описывающая сумму чисел натурального ряда:

${\displaystyle f={\begin{cases}f(0)=0;\\f(n)=n+f(n-1),\quad n>0\end{cases}}}$

может быть переведена в замкнутую форму: ${\displaystyle f={\frac {n(n+1)}{2}}}$ .

Приложения

Рекурсивные функции играют важную роль в теории алгоритмов, так как многие алгоритмы имеют рекурсивную структуру.

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 11 января 2018 года.