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

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

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

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

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

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

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

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

• Функция F : N → N, которая задана правилом F(n) = 3n + 2
• Попробуем вычислить, что F(100) = 3
• 100 + 2 = 302
• F(3112) = 3.3112 + 2 = 9338

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

Рассмотрим функцию G:N → N, которая определена как G(0) = 2:

• Для n > 0, G(n) = G(n - 1) + 3
• Тогда G(1) = G(0) + 3 = 2 + 3 = 5

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

G(5) = G(4) + 3
= G(3) +3+3
= G(2)+3+3+3
= G(1)+3+3+3+3
= G(0)+3+3+3+3+3
= 2+3*5
=17

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

Из вычисления G(5) можно сделать вывод, что две функции F и G одинаковы, то есть F(n) = G(n) для каждого n ∈ N. Такую функцию G называют закрытой формой.

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

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

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

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

Рассмотрим функцию F : N → N, которая определена как F(n) = 3f:

• Также она может быть определена рекурсивно как F(0) = 1 и F(n) = 3
• При этом F(n - 1) для n >= 1

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

Рассмотрим сумму первых k из n элементов al, a2:

• an может быть определена как SUM(k) = a_l + a_2 + ... + a_k, где 1 >= k >= n
• Рекурсивно ту же функция можно определить как S(1) = al и S(k) = S(k- 1)+ak для > 1

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

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

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

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

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

a_n = a_(n-1) + d

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

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

• Сумма первых n членов геометрического ряда a + ac + ac^2 + ac^3 + - ... + ac^n-1
• Она может быть определена как две функции:
  • gs(0) = a
  • gs(k) = gs(k - 1) + ac^k для k > 1

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

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

• Она состоит из членов 1, 1/2, 1/3 ... 1/n, ...
• Она может иметь сумму первых k членов, определяемую как функции H(1) = 1 и H(k) = H(k - 1) + l/k для > 1

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

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

f(1)=1 f(2)=1 f(n)=f(n-2)+f(n-1)

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

f(1)=1
f(2)=1
f(3)=1+1=2
f(4)=1+2=3
f(5)=2+3=5
f(6)=3+5=8
f(7)=5+8=13
f(8)=8+13=21
f(9)=13+21=34
...

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

1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

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

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

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

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

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

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

b_n = b_1 * q^(n-1)

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

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

F(O) = 2 F(1) = 3 F(2) = 5 F(n) = 2F(n - 1) + 3F(n - 2) + F(n - 3) для n >= 3

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

F(3) = 2F(2) + 3F(l) pm F(O) = 10 + 9 pm 2 = 21 F(4) = 2F(3) + 3F(2) + F(l) = 42 + 15 + 3 = 60 F(5) = 2F(4) + 3F(3) + F(2) = 120+ 63 + 5 = 188

Выводы

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

Самостоятельная работа

Вопрос №1

Что подразумевается под рекурсивной функцией?

Вопрос №2

Укажите две части, используемые в формуле рекурсивной функции?

Вопрос №3

Что такое рекурсивная функция последовательности Фибоначчи?

Вопрос №4

Какова формула рекурсивной функции для последовательности 1, 1, 2, 6, 24, 120?

Вопрос №5

Как записать рекурсивную формулу?