Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

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

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

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

4 <h2>Рекурсивно определенные функции</h2>

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

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

7 <ul><li>Функция F : N → N, которая задана правилом F(n) = 3n + 2</li>

8 <li>Попробуем вычислить, что F(100) = 3</li>

9 <li>100 + 2 = 302</li>

10 <li>F(3112) = 3.3112 + 2 = 9338</li>

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

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

13 <ul><li>Для n > 0, G(n) = G(n - 1) + 3</li>

14 <li>Тогда G(1) = G(0) + 3 = 2 + 3 = 5</li>

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

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

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

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

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

20 <ol><li>Определение наименьшего аргумента (обозначается как f(0) или f(1))</li>

21 <li>Определение n-го члена (обозначается как f(n))</li>

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

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

24 <ul><li>Также она может быть определена рекурсивно как F(0) = 1 и F(n) = 3</li>

25 <li>При этом F(n - 1) для n >= 1</li>

26 </ul><h2>Рекурсивная формула для арифметической последовательности</h2>

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

28 <ul><li>an может быть определена как SUM(k) = a_l + a_2 + ... + a_k, где 1 >= k >= n</li>

29 <li>Рекурсивно ту же функция можно определить как S(1) = al и S(k) = S(k- 1)+ak для > 1</li>

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

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

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

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

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

35 a_n = a_(n-1) + d

36 <h2>Сумма первых членов</h2>

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

38 <ul><li>Сумма первых n членов геометрического ряда a + ac + ac^2 + ac^3 + - ... + ac^n-1</li>

39 <li>Она может быть определена как две функции:<ul><li>gs(0) = a</li>

40 <li>gs(k) = gs(k - 1) + ac^k для k > 1</li>

41 </ul></li>

42 </ul><h2>Гармоническая последовательность</h2>

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

44 <ul><li>Она состоит из членов 1, 1/2, 1/3 ... 1/n, ...</li>

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

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

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

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

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

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

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

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

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

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

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

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

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

58 b_n = b_1 * q^(n-1)

59 <h2>Первые значения функции</h2>

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

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

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

63 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

64 <h2>Выводы</h2>

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