Рекурсия в функциях — Функции

Рекурсивно определенные функции
Аргументы в рекурсивно определенной функции
Рекурсивная формула для арифметической последовательности
Сумма первых членов
Гармоническая последовательность
Первые значения функции
Выводы

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

Обычно мы узнаем об этой функции на примере арифметико-геометрической последовательности, которая имеет члены с общей разницей между ними. Еще рекурсия широко используется в языках программирования — например, C, Java, Python или PHP.

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

Рекурсивно определенные функции

Если функция определена формулой, мы можем найти значение на любом элементе ее области. При этом мы не знаем ее значения на любом другом элементе ее области.

Рассмотрим такой пример:

Функция , которая задана правилом
Попробуем вычислить, что

Однако функции не всегда определяются таким простым способом.

Рассмотрим функцию , которая определена как :

Для
Тогда

Следующее вычисление показывает, как будет определено :

Если бы нам теперь понадобилось , то сначала нужно было бы вычислить . В этой ситуации мы говорим, что определено рекурсивно или задано рекурсивным определением.

Из вычисления можно сделать вывод, что две функции и одинаковы, то есть для каждого . Такую функцию называют закрытой формой.

Аргументы в рекурсивно определенной функции

Любая рекурсивно определенной функции состоит из двух частей:

Определение наименьшего аргумента (обозначается как или )
Определение -го члена (обозначается как )

Теперь давайте разберем рекурсивно определенную функцию на примере.

Рассмотрим функцию , которая определена как :

Также она может быть определена рекурсивно как и
При этом для

Рекурсивная формула для арифметической последовательности

Рассмотрим сумму первых из элементов :

может быть определена как , где
Рекурсивно ту же функция можно определить как и для

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

Шаг 1. Определим, является ли данная последовательность арифметической. Складываем или вычитаем два последовательных члена. Если из одного члена в следующий член получается одинаковая сумма, то последовательность арифметическая.

Шаг 2. Находим общую разность заданной последовательности.

Шаг 3. Сформулируем рекурсивную формулу, указав первый член, а затем создайте формулу «предыдущий член + общая разность».

В итоге рекурсивная формула для арифметической последовательности имеет такой вид:

Сумма первых членов

Переходим к сумме первых членов:

Сумма первых членов геометрического ряда
Она может быть определена как две функции:
- для

Гармоническая последовательность

Также рассмотрим гармоническую последовательность:

Она состоит из членов
Она может иметь сумму первых членов, определяемую как функции и для

Еще как пример можно рассматривать последовательность Фибоначчи. Эта последовательность значений была определена рекурсивно — не было дано прямой формулы для нахождения -го элемента последовательности Фибоначчи.

Одна специальная рекурсивно определенная функция, которая не имеет простого явного определения, дает числа Фибоначчи:

Значениями этой функции являются:

Таким образом, последовательность чисел Фибоначчи такова:

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

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

Шаг 1. Определим, является ли данная последовательность геометрической. Умножим или разделим каждый член на число. Если от одного члена к другому получается одинаковая сумма, то последовательность геометрическая.

Шаг 2. Найдем общее отношение данной последовательности.

Шаг 3. Сформулируем рекурсивную формулу, указав первый член. Затем создадим формулу общего отношения к предыдущему члену.

В итоге формула для геометрической последовательности имеет такой вид:

Первые значения функции

Попробуем найти первые шесть значений функции, заданной на N функциями:

для

Решение будет выглядеть так:

Выводы

В этом уроке мы изучили рекурсивную функцию — это функция, которая использует предыдущий член для нахождения следующего члена в последовательности. Еще мы узнали, что рекурсивная функция состоит из двух частей: определения наименьшего аргумента и определения -го члена.