Занятие 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