Рекурсия — значения функций и порядок вызовов в 11 классе

Как читать рекурсивную функцию

Разберём на примерах

11 класс, базовый уровень: простые рекурсивные алгоритмы, функции, трассировка и оценка числа операций. Соответствие конкретным заданиям ЕГЭ не заявляется.

Что именно считают

Код Python 3. Все короткие задачи используют небольшие аргументы и имеют достижимую базу. Кэширование результатов не предполагается, если оно не показано в коде.

Задания с ответами и объяснениями

Сначала реши задание, затем открой ответ. Для печати выбери группу или смешанный набор: задания выбранного набора на листе ученика и отдельный ключ с объяснениями.

Две письменные работы

Покажи базу, промежуточные вызовы и обоснование результата.

1. Дано F(0)=3, F(1)=1, F(n)=F(n−1)+2·F(n−2) при целом n≥2. Напиши функцию Python, возвращающую F(n) для неотрицательного n, с двумя базовыми случаями. Вычисли F(5), составив таблицу F(0)…F(5). Покажи непосредственные вызовы внутри F(3) и объясни, почему они завершаются. Готовые значения в функцию не подставляй.

   Разбор и ориентиры для проверки

   Таблица: 3,1,7,9,23,41; F(5)=41. Пример функции: def F(n): if n == 0: return 3 if n == 1: return 1 return F(n - 1) + 2 * F(n - 2) Внутри F(3) непосредственно вызываются F(2) и F(1); F(2) вызывает F(1) и F(0). В каждом небазовом вызове аргумент уменьшается на 1 или 2 и остаётся неотрицательным до достижения 0 или 1.

   Проверь: По одному баллу за функцию с двумя базами, правильную таблицу и F(5), непосредственные вызовы F(3), объяснение уменьшения аргумента до базы. Равноправный синтаксис Python и другой точный порядок трассировки принимаются.

2. Для вызова p(10) запиши вывод, цепочку аргументов, число всех вызовов и максимальное число одновременно незавершённых вызовов, включая начальный. Объясни расположение print и достижение базы. def p(n): if n <= 1: print(n, end=" ") return print(n, end=" ") p(n // 2) print(n, end=" ")

   Разбор и ориентиры для проверки

   Вывод: 10 5 2 1 2 5 10. Цепочка 10,5,2,1; всего четыре вызова, максимальная глубина четыре. Небазовый вызов печатает до обращения и после возврата; базовый печатает один раз и сразу заканчивается. Положительное целое n//2 уменьшается при n>1 и достигает 1, поэтому цепочка завершается.

   Проверь: По одному баллу за точный вывод, цепочку аргументов с обоими счётчиками, объяснение порядка print, объяснение достижимой базы. Допустим рисунок стека или таблица вызовов.

Для самостоятельной работы и урока

Начни с уже изученной группы, пройди выбранный набор и разбери ошибки. Репетитор может изменить набор, сохранить его и выдать приватное ДЗ. Автопроверка оценивает ответ; способ рассуждения полезно обсудить на уроке.

Повторить основы

• Повторить списки и циклы Python