Рекурсивная функция

Рекурсивная функция

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

Примеры

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

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

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

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

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

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

Например, рекурсивная функция:

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

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

Приложения

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



Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Полезное


Смотреть что такое "Рекурсивная функция" в других словарях:

  • Рекурсивная функция — в информатике функция, которая в своем определении содержит обращение к самой себе. См. также: Подпрограммы Финансовый словарь Финам …   Финансовый словарь

  • рекурсивная функция — Функция, которая в своем определении содержит обращение к самой себе. В математике и информатике рекурсивной называют такую функцию или процедуру, которая при своей работе обращается к себе самой, прямо или косвенно. Соответственно говорят о… …   Справочник технического переводчика

  • Рекурсивная функция (значения) — Рекурсивная функция: Рекурсивная функция  числовая функция числового аргумента, которая в своём определении содержит себя же. Рекурсивная функция функция, принадлежащая одному из следующих классов: примитивно рекурсивные функции,… …   Википедия

  • Рекурсивная функция (теория вычислимости) — У этого термина существуют и другие значения, см. Рекурсивная функция (значения). Термин рекурсивная функция в теории вычислимости используется для обозначения трёх классов функций примитивно рекурсивные функции; общерекурсивные функции; …   Википедия

  • РЕКУРСИВНАЯ ФУНКЦИЯ — ч а с т и ч н о р е к у р с и в н а я ф у н к ц и я, одно из математич. уточнений интуитивного понятия вычислимой функции, определяемое следующим образом. Рассматриваются функции, заданные на натуральных числах и с натуральными значениями.… …   Математическая энциклопедия

  • рекурсивная функция — (< лат. recursio возвращение)    Функция, значение которой для данного аргумента вычисляется с помощью значений для предшествующих аргументов …   Термины и понятия лингвистики: Лексика. Лексикология. Фразеология. Лексикография

  • рекурсивная функция — (< лат. recursio возвращение) Функция, значение которой для данного аргумента вычисляется с помощью значений для предшествующих аргументов …   Словарь лингвистических терминов Т.В. Жеребило

  • ЧАСТИЧНО РЕКУРСИВНАЯ ФУНКЦИЯ — рекурсивная функция, одно из эквивалентных уточнений понятия вычислимой функции. В. Е. Плиско …   Математическая энциклопедия

  • Примитивно рекурсивная функция — Термин рекурсивные функции в теории вычислимости используют для обозначения трёх множеств функций примитивно рекурсивные функции; общерекурсивные функции; частично рекурсивные функции. Последние совпадают с множеством вычислимых по Тьюрингу… …   Википедия

  • Частично рекурсивная функция — Термин рекурсивные функции в теории вычислимости используют для обозначения трёх множеств функций примитивно рекурсивные функции; общерекурсивные функции; частично рекурсивные функции. Последние совпадают с множеством вычислимых по Тьюрингу… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»