Тема 16. Программирование: Циклы и Рекурсия

🏠 Главная / Теория / Тема 16. Программирование: Циклы и Рекурсия

На ОГЭ эта тема проверяет умение трассировать (выполнять вручную) программы с циклами, рекурсивными функциями и найти результат или нужное начальное значение.

---

## 1. Цикл WHILE (Пока)

Выполняется, пока условие истинно. Количество итераций неизвестно заранее.

```python
x = 100
while x > 1:
    x = x // 2    # целочисленное деление на 2
print(x)
```

**Трассировка (выполнение вручную):**

| Итерация | x до | Условие x > 1 | x после |
|----------|------|---------------|---------|
| 1 | 100 | Да | 50 |
| 2 | 50 | Да | 25 |
| 3 | 25 | Да | 12 |
| 4 | 12 | Да | 6 |
| 5 | 6 | Да | 3 |
| 6 | 3 | Да | 1 |
| 7 | 1 | **Нет** | — |

Вывод: `print(1)` → **1**

> **Совет:** При трассировке рисуйте таблицу. Каждая строка — одна итерация цикла.

---

## 2. Цикл FOR (Для)

Выполняется фиксированное количество раз или по диапазону.

```python
for i in range(1, 6):   # i = 1, 2, 3, 4, 5
    print(i * i)
```

Вывод: 1, 4, 9, 16, 25

### Параметры range:

| Вызов | Числа |
|-------|-------|
| `range(5)` | 0, 1, 2, 3, 4 |
| `range(1, 6)` | 1, 2, 3, 4, 5 |
| `range(2, 10, 2)` | 2, 4, 6, 8 |
| `range(10, 0, -1)` | 10, 9, 8, ..., 1 |

> **Совет:** `range(a, b)` включает `a`, но **не включает** `b`. Часто ловушка для невнимательных.

---

## 3. Рекурсия

Функция, которая вызывает саму себя. Обязательно должно быть **базовое условие** (когда остановиться).

```python
def F(n):
    if n <= 1:
        return 1      # базовый случай
    return n + F(n-1)  # рекурсивный случай
```

### Ручная трассировка рекурсии:

Чтобы вычислить `F(5)`, разворачиваем:

```
F(5) = 5 + F(4)
F(4) = 4 + F(3)
F(3) = 3 + F(2)
F(2) = 2 + F(1)
F(1) = 1  ← база, начинаем собирать обратно
F(2) = 2 + 1 = 3
F(3) = 3 + 3 = 6
F(4) = 4 + 6 = 10
F(5) = 5 + 10 = 15
```

**Ответ: `F(5) = 15`** (это $1 + 2 + 3 + 4 + 5$)

> **Совет:** Начните с самых маленьких значений (базовые случаи) и идите вверх.

---

## 4. Типовые задачи ОГЭ

### Тип 1: Найти значение, которое выведет программа

Трассируйте код шаг за шагом:
1. Запишите начальные значения переменных.
2. Выполняйте тело цикла, обновляя переменные.
3. Проверяйте условие после каждой итерации.
4. Когда условие стало ложным — цикл закончился.

### Тип 2: Найти наибольший/наименьший X при котором программа выводит Y

```python
x = ?
while x > 1:
    x = x // 3
print(x)
```
"При каком наибольшем начальном x программа выведет 1?"

**Метод:** Проверяйте значения x от большего к меньшему, пока не найдёте нужный результат. Или используйте "обратный" анализ.

Если финальный x = 1, значит на последнем шаге x // 3 = 1, то есть x было от 3 до 8 (3//3=1, 4//3=1, ..., 8//3=2≠1). Значит перед последним шагом x был 3, 4 или 5 (все дают 1 после //3). И так далее...

---

## 5. Целочисленные операции

Эти операции очень важны для понимания алгоритмов:

| Операция | Символ | Пример | Результат |
|----------|--------|--------|-----------|
| Целочисленное деление | `//` | `17 // 5` | 3 |
| Остаток от деления | `%` | `17 % 5` | 2 |
| Обычное деление | `/` | `17 / 5` | 3.4 |

> **Совет:** `n // 2` — "сдвиг" числа вправо в двоичной записи. Это быстрый способ "срезать" последний бит.

---

## 6. Работа с цифрами числа

Частые операции в задачах:

```python
n = 1234
last_digit = n % 10       # 4 (последняя цифра)
n_without_last = n // 10  # 123 (число без последней цифры)
first_digit = n // 1000   # 1 (первая цифра — если число 4-значное)

# Сумма цифр
def digit_sum(n):
    s = 0
    while n > 0:
        s += n % 10
        n //= 10
    return s
```

---

## 7. Типичные ошибки

- **Перепутать `//` и `/`.** В Python 3 оба работают, но дают разный результат: `7/2 = 3.5`, `7//2 = 3`.
- **Неверное базовое условие рекурсии.** Если забыть base case — бесконечная рекурсия и ошибка.
- **Не обновить переменную в цикле.** Если `x` не изменяется — бесконечный цикл.
- **Перепутать `=` и `==`.** В условии всегда `==`, в присваивании `=`.
- **Неверная граница range.** `range(1, 10)` — числа от 1 до 9 (10 не входит!).

---

## 8. Лайфхаки для ОГЭ

> **Совет:** При трассировке сложного алгоритма нарисуйте таблицу: строки — итерации, столбцы — переменные. Обновляйте каждую ячейку.

> **Совет:** Если в задаче просят "наибольшее X, при котором вывод равен Y" — попробуйте запустить код в голове для нескольких значений рядом с граничным.

> **Совет:** Рекурсию удобно считать "снизу вверх": сначала вычислите F(1), потом F(2), F(3)... до нужного значения.

> **Совет:** Если на экзамене есть компьютер — вы можете запустить Python и проверить свой ответ! Это официально разрешено для задач 15 и 16.

Назад к списку