Функции
2026-02-26 16:50 Diff
https://ru.hexlet.io/courses/functions/lessons/recursively/theory_unit

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

Обычно мы узнаем об этой функции на примере арифметико-геометрической последовательности, которая имеет члены с общей разницей между ними. Еще рекурсия широко используется в языках программирования — например, 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(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)

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

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

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-го члена.