Трассировка рекурсивного алгоритма

Зачем это в ЕГЭ. Задание 16 проверяет умение анализировать работу рекурсивных алгоритмов. Даёт 2 первичных балла. Встречается в 80% реальных вариантов, требует понимания стека вызовов и состояния переменных.

Главная идея. Рекурсия — это вызов функцией самой себя. Ключ — отслеживать параметры каждого вызова и возвращаемые значения, записывая их в таблицу или дерево вызовов. Важно найти условие выхода из рекурсии.

Алгоритм (чеклист).
1. Выписать сигнатуру функции и начальные параметры.
2. Построить дерево вызовов до выполнения условия выхода.
3. Для каждого вызова записать локальные переменные и параметры.
4. Вычислить возвращаемые значения «снизу вверх».
5. Проверить, что глубина рекурсии не превышает 10-15 вызовов (предел ЕГЭ).

Опоры (кратко).
- Базовый случай: условие if для выхода из рекурсии
- Рекуррентный случай: вызов с изменёнными параметрами
- Стек вызовов: LIFO (последний пришёл — первый вышел)
- Формула глубины: $d = \log_k(n)$ для деления на $k$

Пример 1 (вычисление значения).
Дана функция:

pythondef F(n):
    if n <= 2: return n
    return F(n-1) + 2*F(n-2) + 3*F(n-3)
*Шаг 1.* Базовый случай: F(1)=1, F(2)=2.  
*Шаг 2.* F(3) = F(2) + 2F(1) + 3F(0) → но F(0) не определён → ошибка в условии.  
*Шаг 3.* Корректируем: при n ≤ 0 возвращаем 0.  
*Шаг 4.* F(3) = 2 + 2×1 + 3×0 = 4.  
*Шаг 5.* F(4) = 4 + 2×2 + 3×1 = 11.  

**Пример 2 (количество вызовов).**  
Для функции:  

python
def G(n):
if n == 1: return 1
return G(n-1) + G(n-1)
Шаг 1. Базовый случай: G(1) = 1 вызов.
Шаг 2. G(2) = 2 вызова (G(1) дважды).
Шаг 3. G(3) = 2×G(2) = 4 вызова.
Шаг 4. Общая формула: $2^{n}-1$ вызовов.

Типичные ошибки.
1. Пропуск базового случая — забывают проверить условие выхода.
2. Неправильный порядок вычислений — начинают «сверху», а не «снизу».
3. Переполнение стека — не учитывают экспоненциальный рост вызовов.
4. Арифметические ошибки — путают операции при подсчёте.

Дальше. Разбери задачи на рекурсивные алгоритмы с возвратом (backtracking) и мемоизацию.