Занятие 3.1 Рекурсия

1. Рекурсия

2. Функция

• Функция — это мини-программа внутри вашей
программы. Это именованный блок кода, который
выполняет определенную задачу.
• Зачем они нужны?
• 1. Избежать повторов. Если вам нужно 10 раз посчитать
площадь треугольника, лучше 1 раз написать функцию,
чем 10 раз копировать формулу.
• 2. Разделение задач. Проще искать ошибки, когда код
разбит на логические куски.

3. Синтаксис

• def имя_функции(параметры):
# Тело функции
# Код, который что-то делает

4. return

Возврат результата из функции.
def calc_sum(a, b):
result = a + b
return result # ВЕРНУЛИ результат в программу
# Мы можем сохранить результат в переменную
x = calc_sum(5, 10)
# И использовать его дальше
final = x * 2
print(final) # Выведет 30
• Правило: В месте вызова функции код как бы заменяется на то, что
вернул return.
• x = calc_sum(5, 10) превращается компьютером в x = 15.

5. Функция без return

• def say_hello(a, b):
result = a + b
print(result) # ПРОСТО ПОКАЗАЛИ на экране
• # Попытка сохранить результат
• x = say_hello(5, 10) # На экране появится 15
• # Но что внутри x?
• print(x) # Выведет None
• В Python, если в функции нет return, она неявно
возвращает специальное значение None (пустоту).
Математику с None делать нельзя.

6. Сравнение

7. Рекурсия

• Рекурсия — это когда функция вызывает сама себя.
• Чтобы рекурсия не была бесконечной (как while True), у
неё должны быть две части:
• 1. Базовый случай (Условие остановки): Ситуация, когда
функция выдает готовый ответ без новых вызовов
(например, if n == 0: return 0).
• 2. Рекурсивный шаг: Вызов функции с измененным
аргументом, приближающим нас к базовому случаю
(например, return n + F(n-1)).

8. Пример 1

• Задача:
• F(n) = 1, при n = 1
• F(n) = n + F(n-1), при n > 1
• Чему равно F(5)?
• def F(n):
if n == 1:
return 1
if n > 1:
return n + F(n - 1)
• print(F(5))

9. Задача 1

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = 1 при n < 3;
• F(n) = F(n − 2) − F(n − 1), если n > 2 и при этом n
чётно;
• F(n) = 2 × F(n − 1) − F(n − 2), если n > 2 и при этом n
нечётно.
• Чему равно значение функции F(15)?

10. Задача 1

• def f(n):
if n<3: return 1
elif n%2==0: return f(n-2) - f(n-1)
return 2*f(n-1) - f(n-2)
• print(f(15))

11. Порядок выполнения

• def F(n):
print(f"Спуск: я зашел в F({n})") # Действие ДО вызова (Прямой ход)
if n == 1:
print("ДНО! Базовый случай")
return 1
# Рекурсивный вызов
res = F(n - 1)
print(f"Подъем: я вернулся в F({n}), мне принесли результат {res}") #
ПОСЛЕ вызова (Обратный ход)
return n + res # Возвращаем результат еще выше
• print("Ответ:", F(3))

12. Порядок выполнения

• def G(n):
if n >= 1:
G(n-1)
print(n)
• Что выведет G(3)?

13. Задача 2

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан
• следующими соотношениями:
• F(n) = 1 при n = 1;
• F(n) = n + F(n − 1), если n > 1.
• Чему равно значение выражения F(2023) – F(2020)?

14. Глубина рекурсии

• По умолчанию Python по умолчанию ограничивает
глубину рекурсии (~1000 вызовов).
• Для увеличения глубины рекурсии можно использовать:
• import sys
• sys.setrecursionlimit(...)

15. Задача 2

• import sys
• sys.setrecursionlimit(3000)
• def f(n):
if n==1: return 1
return n + f(n-1)
• print(f(2023) - f(2020))

16. Задача 3

• Условие:
• Алгоритм вычисления функции F(n) задан
соотношениями:
• F(n) = 1, при n <=2
• F(n) = F(n-1) + F(n-2), при n > 2
• Чему равно значение функции F(2024)?

17. Мемоизация

• Мы считаем одно и то же миллионы раз.
• Чтобы найти F(5), мы считаем F(4) и F(3).
• Чтобы найти F(4), мы снова считаем F(3) и F(2).
• В итоге F(3) считается для каждого родителя заново.
Дерево вызовов растет в ширину очень быстро.
• Чтобы не считать одно и тоже, нужно позволить функции
запоминать уже рассчитанные значения. Для этого нужно
добавить в начале кода следующее:
• from functools import lru_cache
• @lru_cache(None)

18. Прогрев кэша

• Перед решением основной задачи пишем:
• for i in range(1, 2025):
F(i)
• Благодаря циклу for, рекурсия никогда не углубляется
больше чем на 1 шаг. В процессе мы постепенно
заполняем кэш.

19. Задача 3

• from functools import lru_cache
• @lru_cache(None)
• def F(n):
if n <= 2:
return 1
return F(n - 1) + F(n - 2)
• for i in range(1, 2025):
F(i)
• print(F(2024))

20. Задача 4

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = 6 при n < 7;
• F(n) = n + F(n − 1), если n ≥ 7.
• Чему равно значение выражения F(2023) – F(2021)?

21. Задача 5

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = 10 при n < 11;
• F(n) = n + F(n − 1), если n ≥ 11.
• Чему равно значение выражения F(2024) – F(2021)?

22. Задача 6

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = 1 при n < 3;
• F(n) = F(n − 2) − F(n − 1), если n > 2 и при этом n
чётно;
• F(n) = 2 × F(n − 1) − F(n − 2), если n > 2 и при этом n
нечётно.
• Чему равно значение функции F(31)?

23. Задача 7

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = 3 при n < 3;
• F(n) = n + F(n − 2), если n ≥ 3.
• Чему равно значение выражения F(2022) – F(2018)?

24. Задача 8

• Алгоритм вычисления значения функции F(n), где n –
целое неотрицательное число, задан следующими
соотношениями:
• F(n) = 0 при n ≤ 1; F(n) = 2 × n + F(n − 1), если n > 1 и
при этом n нечётно;
• F(n) = 2 × F(n − 1) , если n > 1 и при этом n чётно.
• Чему равно значение функции F(24)?

25. Задача 9

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = 1 при n < 3; F(n) = F(n − 2) − F(n − 1), если n > 2
и при этом n чётно;
• F(n) = 2 × F(n − 1) − F(n − 2), если n > 2 и при этом n
нечётно.
• Чему равно значение функции F(19)?

26. Задача 10

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = 1 при n < 3; F(n) = F(n − 1) + n − 1, если n > 2 и
при этом n чётно;
• F(n) = F(n − 2) + 2 × n − 2, если n > 2 и при этом n
нечётно.
• Чему равно значение функции F(36)?

27. Задача 11

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = 1 при n = 1; F(n) = n + F(n − 1), если n чётно;
• F(n) = 2 × F(n − 2), если n > 1 и при этом n нечётно.
• Чему равно значение функции F(24)?

28. Задача 12

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = 1 при n < 3; F(n) = F(n − 2) − F(n − 1), если n > 2
и при этом n чётно;
• F(n) = 2 × F(n − 1) − F(n − 2), если n > 2 и при этом n
нечётно.
• Чему равно значение функции F(18)?

29. Задача 13

• Алгоритм вычисления значения функции F(n), где n –
целое неотрицательное число, задан следующими
соотношениями:
• F(n) = 0 при n ≤ 1; F(n) = 2 × n + F(n − 1), если n > 1 и
при этом n нечётно;
• F(n) = 2 × F(n − 1) , если n > 1 и при этом n чётно.
• Чему равно значение функции F(22)?

30. Задача 14

• Алгоритм вычисления значения функции F(n), где n –
целое неотрицательное число, задан следующими
соотношениями:
• F(n) = 0 при n ≤ 1;
• F(n) = 2 × F(n − 1) + 2, если n > 1 и при этом n
нечётно;
• F(n) = n / 2 + F(n − 1), если n > 1 и при этом n чётно.
• Чему равно значение функции F(26)?
• Примечание. При вычислении значения F(n)
используется операция целочисленного деления.

31. Задача 15

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = 1 при n = 1; F(n) = n + F(n − 1), если n чётно;
• F(n) = 2 × F(n − 2), если n > 1 и при этом n нечётно.
• Чему равно значение функции F(24)?

32. Задача 16

• Алгоритм вычисления значения функции F(n), где n –
целое неотрицательное число, задан следующими
соотношениями:
• F(n) = 0 при n ≤ 1; F(n) = 2 × F(n − 1) + 2, если n > 1 и
при этом n нечётно;
• F(n) = n / 2 + F(n − 1), если n > 1 и при этом n чётно.
• Чему равно значение функции F(28)? Примечание.
При вычислении значения F(n) используется
операция целочисленного деления.

33. Задача 17

• Алгоритм вычисления значения функции F(n), где n –
целое неотрицательное число, задан следующими
соотношениями:
• F(n) = 0 при n ≤ 1; F(n) = 2 × F(n − 1) + 2, если n > 1 и
при этом n нечётно;
• F(n) = n / 2 + F(n − 1), если n > 1 и при этом n чётно.
• Чему равно значение функции F(30)?
• Примечание. При вычислении значения F(n)
используется операция целочисленного деления.

34. Задача 18

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = 2 при n < 3;
• F(n) = F(n − 2) + F(n − 1) – n, если n > 2 и при этом n
чётно;
• F(n) = F(n − 1) − F(n − 2) + 2 × n, если n > 2 и при этом
n нечётно.
• Чему равно значение функции F(32)?

35. Задача 19

• Алгоритм вычисления значения функции F(n), где n –
целое неотрицательное число, задан следующими
соотношениями:
• F(n) = 0 при n ≤ 1; F(n) = (n + 1) / 2 + F(n − 1), если n >
1 и при этом n нечётно;
• F(n) = 2 × F(n − 1) + 1, если n > 1 и при этом n чётно.
• Чему равно значение функции F(33)?
• Примечание. При вычислении значения F(n)
используется операция целочисленного деления

36. Задача 20

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = 1 при n = 1;
• F(n) = n – 2 + F(n − 1), если n > 1.
• Чему равно значение выражения F(2024) – F(2022)?

37. Задача 21

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = 3 при n = 1;
• F(n) = n + 2 + F(n − 1), если n > 1.
• Чему равно значение выражения F(2023) – F(2021)?

38. Задача 22

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = n при n >= 2025;
• F(n) = n + F(n + 2), если n < 2025.
• Чему равно значение выражения F(2022) – F(2023)?

39. Задача 23

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = n при n >= 2025;
• F(n) = n + 3 + F(n + 3), если n < 2025.
• Чему равно значение выражения F(2018) – F(2022)?

40. Задача 24

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = n при n >= 2025;
• F(n) = n + 3 + F(n + 3), если n < 2025.
• Чему равно значение выражения F(23) – F(21)?

41. Задача 25

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = 5 при n = 1;
• F(n) = 2n + 1 + F(n - 1), если n > 1.
• Чему равно значение выражения F(2024) – F(2022)?

42. Задача 26

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = 3 при n = 1;
• F(n) = 3n + 2 · F(n - 1), если n > 1.
• Чему равно значение выражения
• F(2024) – 4 · F(2022)?

43. Задача 27

• Алгоритм вычисления значения функции F(n), где n –
натуральное число, задан следующими
соотношениями:
• F(n) = 1 при n = 1;
• F(n) = 2 при n = 2;
• F(n) = n · (n-1) + F(n - 1) + F(n - 2), если n > 2.
• Чему равно значение выражения F(2024) – F(2022) –
2 · F(2021) – F(2020)?

44. Ответы

• 4) 4045
• 5) 6069
• 6) 114243
• 7) 4042
• 8) 40852
• 9) 577
• 10) 648
• 11) 2072
• 12) 169
• 13) 20380
• 14) 24559
• 15) 2072

45. Ответы

• 16) 49134
• 17) 98285
• 18) 3194
• 19) 262124
• 20) 4043
• 21) 4049
• 22) 2024
• 23) 4049
• 24) 1338
• 25) 8096
• 26) 18210
• 27) 12271520