Подпрограммы и рекурсия — Информатика, 11 класс

Вспомогательные алгоритмы и функции на Питоне, параметры и локальные переменные, рекурсивные функции, деревья вызовов и число вызовов. 100 заданий на отработку.

Простыми словами

Подпрограмма — это готовый рецепт с названием. Повар не расписывает каждый раз, как варить бульон, а пишет «сварить бульон» — и рецепт выполняется. Рекурсия — рецепт, который ссылается сам на себя: «чтобы разобрать матрёшку, открой её и разбери ту, что внутри».

def f(a, b):
c = a + b
return c * 8
$a, b$ — параметры; при вызове f(17, 3) в них подставляются аргументы 17 и 3. return завершает функцию и отдаёт результат: $(17 + 3) \cdot 8 = 160$ .

Всё, что записано после сработавшего return, не выполняется. Переменная c локальная: снаружи функции её нет, и её изменение не влияет на одноимённую переменную вне функции.

Композиция функций

В записи g(f(x)) сначала вычисляется внутренняя функция, её результат становится аргументом внешней.

def f(a): return a * 2
def g(b): return b - 4
x = 22; print(g(f(x)))

$f (22) = 44$ .
$g (44) = 44 - 4 = 40$ .

Читайте вызовы изнутри наружу, как скобки в математике: $g (f (x))$ — «сначала $f$ , потом $g$ ».

Рекурсия

База рекурсииусловие, при котором функция сразу возвращает ответ, не вызывая себя (if n <= 1: return 1).

Рекурсивный шагсведение задачи к такой же задаче меньшего размера (return 2 * F(n - 1) + 1).

Без базы вызовы вкладываются бесконечно, пока не переполнится стек вызовов (в Python — ошибка RecursionError).

def F(n):
if n <= 1: return 1
return 2 * F(n - 1) + 1
Найдём $F (5)$ .

Спускаемся до базы: $F (5) \to F (4) \to F (3) \to F (2) \to F (1) = 1$ .
Поднимаемся снизу вверх: $F (2) = 2 \cdot 1 + 1 = 3$ , $F (3) = 7$ , $F (4) = 15$ , $F (5) = 31$ .

F(n) = F(n - 1) + n * n, $F (1) = 0$ . Тогда $F (8) = 2^{2} + 3^{2} + \dots + 8^{2} = 204 - 1 = 203$ .

Удобно заполнять таблицу $n ∣ F (n)$ от базы вверх: $F (1), F (2), \dots$ — так не нужно держать в голове цепочку вызовов.

Дерево вызовов и число вызовов

Если функция вызывает себя дважды, вызовы ветвятся. Число узлов дерева вызовов — общее число вызовов функции.

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

F (1) = F (2) = 1

: при вызове

F (5)

функция вызывается 9 раз

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

C (n)

— число вызовов при запуске

F (n)

;

C (1) = C (2) = 1

$C (3) = 1 + 1 + 1 = 3$ , $C (4) = 1 + 3 + 1 = 5$ , $C (5) = 1 + 5 + 3 = 9$ — совпадает с деревом.

Не забывайте « $+ 1$ » — сам вызов $F (n)$ тоже считается. А в вопросе «сколько раз вызвана $F (2)$ » считают только узлы F(2): здесь их 3.

Примеры заданий

Это несколько заданий из тренажёра, остальные — в тренажёре в начале страницы.

Что будет напечатано на экране после выполнения этой программы на Питоне?

def f(a, b):
c = a + b
return c * 8
print(f(17, 3))

Параметр	Значение при вызове
a	17
b	3
результат	?

Показать ответ

Ответ: 160
Решение. При вызове f(17, 3) параметры получают значения a = 17, b = 3; функция возвращает 160.

Что будет напечатано на экране после выполнения этой программы на Питоне?

def f(a, b):
c = a + b
return c * 7
print(f(8, 19))

Параметр	Значение при вызове
a	8
b	19
результат	?

Показать ответ

Ответ: 189
Решение. При вызове f(8, 19) параметры получают значения a = 8, b = 19; функция возвращает 189.

Что будет напечатано на экране после выполнения этой программы на Питоне?

def f(a):
return a * 2
def g(b):
return b - 4
x = 22
print(g(f(x)))

Выражение	Значение
f(22)	?
g(f(22))	?

Показать ответ

Ответ: 40
Решение. Сначала f(22) = 44, затем g(44) = 40.