Неделя 4

Лекция. Рекурсия. Бинарный поиск

скачать .ipynb

Лекция 4. Рекурсия. Бинарный поиск

Сначала разберём, как функции вызывают друг друга и самих себя. Затем увидим рекурсивное построение фракталов и перейдём к бинарному поиску.

План

  1. Синхронный вызов: сказка про репку.
  2. Рекуррентное задание функции, рекурсия и стек вызовов.
  3. Матрёшка: действия до и после рекурсивного вызова.
  4. Кривые Коха и дракона в ColabTurtle.
  5. Генерация двоичных последовательностей и перестановок.
  6. Корень делением пополам, бинарный поиск в массиве и поиск по ответу.

На семинаре 4 — бинарный поиск. Сортировки слиянием и Хоара разберём позднее.

Синхронный вызов: репка

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

Пример из МФК: сначала прочитайте программу и предскажите порядок сообщений. Кто начнёт тянуть первым? Когда выполнится строка после grandmother()?

In [1]:
def grandfather():
    print('Дедка зовёт бабку.')
    grandmother()
    print('Дедка за репку!')

def grandmother():
    print('Бабка зовёт внучку.')
    granddaughter()
    print('Бабка за дедку.')

def granddaughter():
    print('Внучка зовёт жучку.')
    dog()
    print('Внучка за бабку!')

def dog():
    print('Жучка зовёт кошку.')
    cat()
    print('Жучка за внучку!')

def cat():
    print('Кошка зовёт мышку.')
    mouse()
    print('Кошка за жучку!')

def mouse():
    print('Мышка никого не зовёт. Мышка просто тянет за кошку.')

Все функции описаны, но ещё не вызваны. Запускаем сказку:

In [2]:
grandfather()
print("Ура! И вытянули репку!")

Дедка зовёт бабку.
Бабка зовёт внучку.
Внучка зовёт жучку.
Жучка зовёт кошку.
Кошка зовёт мышку.
Мышка никого не зовёт. Мышка просто тянет за кошку.
Кошка за жучку!
Жучка за внучку!
Внучка за бабку!
Бабка за дедку.
Дедка за репку!
Ура! И вытянули репку!

Вызовы идут от дедки к мышке, а возвраты — от мышки к дедке. Пока работает mouse(), предыдущие вызовы ещё не завершены.

Здесь нет рекурсии: каждая функция вызывает другую, и цепочка заканчивается. Но механизм ожидания и возврата уже тот, который нам понадобится.

Рекуррентное задание функции и рекурсия

Можно определить значение функции через её значение на меньшем аргументе:

$$F(0)=1, \qquad F(n)=n\cdot F(n-1),\quad n\geq 1.$$

Это рекуррентное задание факториала. Например, $F(3)=3\cdot F(2)=3\cdot2\cdot F(1)=3\cdot2\cdot1\cdot F(0)=6$.

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

Чтобы рекурсивное вычисление завершилось, нужны:

  • базовый случай, который решается без нового вызова;
  • рекурсивный шаг, сводящий задачу к меньшей;
  • уменьшение неотрицательного целого параметра, гарантирующее достижение базы.

Стек вызовов

У каждого вызова свои параметры и локальные переменные. Кроме них нужно помнить, где продолжить выполнение после возврата.

Представим вызов карточкой: «какая функция, с какими данными, где продолжить». Новый вызов кладёт карточку сверху; возврат снимает верхнюю карточку. Эта последовательность незавершённых вызовов называется стеком вызовов.

Для репки карточки разные по имени функции. При рекурсии имя повторяется, но карточки и значения параметров остаются отдельными. Реализацию стека как структуры данных рассмотрим позднее.

Матрёшка

Вместо разных персонажей — одна функция с параметром n: число матрёшек, включая внешнюю. Договор: n — целое число, n ≥ 1.

Открываем внешнюю матрёшку, разбираемся с вложенной, затем закрываем внешнюю. Самая маленькая не открывается.

In [3]:
def matryoshka(n):
    """Открыть и закрыть n вложенных матрёшек; n — целое, n >= 1."""
    if n == 1:
        print("Самая маленькая матрёшка: 1")
        return
    print("Открываем матрёшку:", n)
    matryoshka(n - 1)
    print("Закрываем матрёшку:", n)


matryoshka(3)

Открываем матрёшку: 3
Открываем матрёшку: 2
Самая маленькая матрёшка: 1
Закрываем матрёшку: 2
Закрываем матрёшку: 3

Предскажите результат перед запуском:

Открываем матрёшку: 3
Открываем матрёшку: 2
Самая маленькая матрёшка: 1
Закрываем матрёшку: 2
Закрываем матрёшку: 3
МоментАктивные вызовы от внешнего к внутреннему
Открываем 3matryoshka(3)
Открываем 2matryoshka(3) → matryoshka(2)
Самая маленькаяmatryoshka(3) → matryoshka(2) → matryoshka(1)
Закрываем 2matryoshka(3) → matryoshka(2)
Закрываем 3matryoshka(3)

Вызов matryoshka(n - 1) не меняет n внешнего вызова. После возврата он продолжает работу со своим прежним значением.

Вопросы. Что будет, если убрать базовый случай? Если передавать n вместо n-1? Если перенести последнее сообщение перед вызовом?

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

Рекурсивное рисование в ColabTurtle

Теперь меньшая задача — нарисовать меньшую копию фигуры. На экране будут конечные приближения фракталов; параметр depth задаёт число уровней построения.

Подключение черепашки взято из МФК. Установочную ячейку достаточно выполнить при подготовке окружения. В Google Colab рисунок появляется прямо под ячейкой.

Документация ColabTurtle.

In [ ]:
%pip install -q ColabTurtle
In [4]:
from ColabTurtle.Turtle import *

Кривая Коха: koch_curve

При глубине 0 рисуем отрезок длины length. На следующем уровне заменяем его четырьмя отрезками длины length / 3: первый прямо, второй под углом 60°, третий под углом −60°, четвёртый снова прямо.

В рекурсивном шаге каждый из этих отрезков заменяется меньшей кривой Коха. Четыре вызова выполняются по очереди: следующий начнётся только после возврата предыдущего.

Договор: length > 0, depth — целое неотрицательное. После выполнения направление черепашки такое же, как до вызова; конец находится на расстоянии length прямо от начала.

In [5]:
def koch_curve(length, depth):
    if depth == 0:
        forward(length)
        return
    koch_curve(length / 3, depth - 1)
    left(60)
    koch_curve(length / 3, depth - 1)
    right(120)
    koch_curve(length / 3, depth - 1)
    left(60)
    koch_curve(length / 3, depth - 1)
In [6]:
# Сначала depth = 0, затем 1 и 3. Перезапуск очищает рисунок.
initializeTurtle(initial_speed=13, initial_window_size=(800, 500))
penup()
goto(80, 350)
right(90)  # после инициализации черепашка смотрит вверх
pendown()
koch_curve(630, 3)

Для depth=1 на доске четыре вызова с depth=0. Для depth=2 каждый из них заменяется ещё четырьмя.

Число нарисованных отрезков — $4^d$, а глубина стека функции koch_curve — всего $d+1$. Дерево всех вызовов и текущая цепочка активных вызовов — разные объекты.

Кривая дракона: dragon_curve

При глубине 0 снова рисуем отрезок. Иначе заменяем его двумя меньшими копиями с разной ориентацией. Параметр sign равен +1 или −1 и определяет зеркальный выбор поворотов.

Каждая половина имеет расстояние между концами length / √2. Повороты перед первой половиной, между половинами и после второй: sign · 45°, −sign · 90°, sign · 45°.

Договор такой же: после вызова направление восстановлено, конец находится на расстоянии length прямо от начала. Разбираем глубину 1 как два отрезка с прямым углом между ними, затем смотрим несколько уровней.

In [7]:
def dragon_curve(length, depth, sign=1):
    """length > 0; depth — целое >= 0; sign равен +1 или -1."""
    if depth == 0:
        forward(length)
        return
    left(sign * 45)
    dragon_curve(length / 2**0.5, depth - 1, 1)
    right(sign * 90)
    dragon_curve(length / 2**0.5, depth - 1, -1)
    left(sign * 45)
In [8]:
# Для первого разбора замените 8 на 1. sign=-1 отражает рисунок.
initializeTurtle(initial_speed=13, initial_window_size=(800, 500))
penup()
goto(240, 330)
right(90)
pendown()
dragon_curve(300, 8)

Здесь два рекурсивных вызова вместо четырёх: отрезков $2^d$, глубина стека функции dragon_curve — $d+1$.

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

Проверка понимания. Где база в каждом примере? Какой параметр уменьшается? Какая команда выполняется после первого рекурсивного вызова? Почему число отрезков растёт гораздо быстрее глубины?

Генерация двоичных последовательностей: gen_bin

Строим последовательность длины n (целое n ≥ 0). К готовому началу prefix приписываем сначала 0, затем 1. Печатаем только в базовом случае, когда длина достигла n.

In [ ]:
def gen_bin(n, prefix=""):
    if len(prefix) == n:
        print(prefix)
        return
    gen_bin(n, prefix + "0")
    gen_bin(n, prefix + "1")


gen_bin(3)

000
001
010
011
100
101
110
111

Генерация перестановок: gen_permutations

Переставляем числа от 1 до n (целое n ≥ 0). На очередное место пробуем каждое ещё не использованное число. Готовое начало храним в кортеже prefix; (number,) — кортеж из одного числа. Печатаем только готовую перестановку в базовом случае.

In [ ]:
def gen_permutations(n, prefix=()):
    if len(prefix) == n:
        print(*prefix)
        return
    for number in range(1, n + 1):
        if number not in prefix:
            gen_permutations(n, prefix + (number,))


gen_permutations(3)

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

От рекурсии к бинарному поиску

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

Непрерывная функция и корень

Пусть $f$ задана на отрезке $[a, b]$ и непрерывна: график можно нарисовать не отрывая карандаш, без скачков.

Лемма о промежуточных значениях. Непрерывная $f$ принимает на $[a, b]$ все значения между $f(a)$ и $f(b)$. В частности, если $f(a)$ и $f(b)$ разных знаков, на отрезке есть корень: $f(x)=0$ для некоторого $x\in[a, b]$.

На доске: концы по разные стороны оси, график ось пересекает. Без непрерывности это неверно: функция может перепрыгнуть через ноль.

Лемма говорит, что корень есть. Как его найти с заданной точностью — другой вопрос.

Классический бинпоиск по вещественной оси

Границы, где функция точно больше нуля и точно меньше. Смотрим середину. По знаку $f$ в середине одну границу двигаем в эту точку: отрезок короче вдвое, знаки на концах по-прежнему разные, корень никуда не делся.

Стоп, когда длина отрезка меньше удвоенной допустимой ошибки $\varepsilon$. Тогда середина оставшегося отстоит от любого конца меньше чем на $\varepsilon$, и её можно выдать как ответ.

Это отрезок на $\mathbb{R}$ и порог $\varepsilon$, не полуинтервал из целых индексов. Полный цикл с float не пишем: идея и одна картинка. На семинаре 4 пишете целые $[l, r)$.

Пример: $f(x)=x^2-2$ на $[1, 2]$. $f(1)=-1<0$, $f(2)=2>0$, корень — $\sqrt{2}$. Один шаг:

In [9]:
def f(x):
    return x * x - 2


left, right = 1.0, 2.0
print("знаки на концах:", f(left), f(right))

mid = (left + right) / 2
print("середина:", mid, "  f(mid) =", f(mid))
if f(mid) > 0:
    right = mid
else:
    left = mid
print("отрезок после шага:", left, right)
print("длина:", right - left)

знаки на концах: -1.0 2.0
середина: 1.5   f(mid) = 0.25
отрезок после шага: 1.0 1.5
длина: 0.5

После шага корень всё ещё внутри, длина вдвое меньше. Повторять, пока длина больше $2\varepsilon$; ответ — середина того, что осталось.

Ту же идею «отрезать половину по знаку / сравнению» переносим на индексы массива. Там нет $\varepsilon$: кандидаты дискретные, и договор про границы другой.

Бинпоиск в массиве

Массив уже неубывает. Вопрос «есть ли ключ / где граница» не обязан смотреть все элементы: сравнение с серединой выбрасывает половину индексов.

Инвариант. Держим полуинтервал $[l, r)$: $l$ входит, $r$ не входит. Кандидаты — целые $l, l+1, \ldots, r-1$.

  • на всех индексах строго левее $l$ предикат ложен;
  • на всех индексах от $r$ до $n-1$ предикат истинен.

Непроверенные индексы находятся в $[l,r)$, а искомая граница — в $[l,r]$, включая правый конец. Ответ $n$ означает, что истинных значений нет.

Середина $m = (l + r)//2$ лежит в $[l, r)$. Одним сравнением отбрасываем одну сторону.

Ищем первый индекс, где предикат стал истинным (и дальше не становится ложным):

  • если предикат на $m$ истинен — ответ не правее $m$, поэтому $r = m$;
  • иначе $l = m + 1$.

Цикл, пока $l < r$. Когда остановились, $l = r$, и $l$ — первый истинный (если истинных не было, вернётся исходный правый конец).

Отрезок $[l, r]$ на этой неделе не используем. После каждой итерации полуинтервал строго короче. Если при ложном предикате оставить $m$ в диапазоне ($l = m$), при $r = l+1$ получится $m = l$, и цикл не сузится.

На каждом шаге сокращаем диапазон индексов вдвое. Основная запись — итеративная, не рекурсия: на семинаре 4 пишете while.

In [10]:
a = [1, 2, 4, 4, 7]
l, r = 0, len(a)  # ищем первый индекс с a[i] >= 4
print("старт: полуинтервал [%d, %d)" % (l, r), "массив", a)

m = (l + r) // 2
print("m =", m, "  a[m] =", a[m])
if a[m] >= 4:
    r = m
else:
    l = m + 1
print("после шага: [%d, %d)" % (l, r))

старт: полуинтервал [0, 5) массив [1, 2, 4, 4, 7]
m = 2   a[m] = 4
после шага: [0, 2)

Дальше тем же правилом: $m = 1$, $a[1]=2$ ещё меньше $4$, поэтому $l = 2$. Полуинтервал $[2, 2)$ пуст — ответ $2$.

В худшем случае линейный просмотр требует $\Theta(n)$ сравнений, а бинарный поиск — $\Theta(\log n)$ при $n \ge 2$: каждый шаг длина диапазона падает вдвое. Память итеративной версии — несколько переменных.

lower_bound и upper_bound

Неубывающий массив — частный случай: $f(i) = a[i]$, шкала $[0, n)$.

  • lower_bound$(a, x)$ — первый индекс, где $a[i] \ge x$. Если все элементы меньше $x$, ответ $n$ (куда вставлять за концом).
  • upper_bound$(a, x)$ — первый индекс, где $a[i] > x$.

«Есть ли ключ» — следствие: если lower_bound вернул $i < n$ и $a[i] = x$, ключ есть. Диапазон равных $x$ — полуинтервал $[\mathrm{lower}, \mathrm{upper})$.

индекс     0  1  2  3  4   5
значение   1  2  4  4  7
                  ^        lower_bound(., 4) = 2
                        ^  upper_bound(., 4) = 4

Равные четвёрки лежат в $[2, 4)$. Для $x=3$ оба конца те же $2$: ключа нет, вставка перед первой четвёркой. Для $x=8$ ответ $5$: все меньше, вставка за концом. Пустой массив, один элемент, все равны — те же два вопроса про первый $\ge$ и первый $>$.

bisect в стандартной библиотеке делает то же самое, но на зачёте нужен инвариант, не имя модуля.

Поиск по ответу

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

Предикат $P(t)$: «с этим $t$ уже можно». Он ложный на префиксе шкалы и истинный начиная с некоторого места (или наоборот — тогда ищем первое ложное, то же самое с отрицанием). Стоимость вычисления $P(t)$ зависит от задачи: бывает постоянной, бывает линейной по входу. Бинпоиск идёт по $t$.

Схема: придумать $P$ и границы $l,r$, для которых левее $l$ всё ложно, а начиная с $r$ всё истинно. Ответ может совпасть с $r$; сам индекс $l$ не обязан быть ложным. Дальше тот же цикл, что для массива.

Целый квадратный корень. Максимальное $x\ge 0$ с $x^2 \le n$. Предикат «$t^2 > n$» ложен, пока $t$ ещё не больше корня, и истинен после. Первый такой $t$ минус единица — ответ. Можно взять $[0,n+1)$: индекс $n+1$ заведомо удовлетворяет предикату и может быть ответом. При $n=0$ первый истинный равен 1, поэтому целый корень равен 0.

Скорость обработки кучек. Кучки размеров $a_i>0$ нужно обработать за $H$ часов, $H$ не меньше числа кучек. При целой скорости $v>0$ нужно $\sum_i \lceil a_i/v \rceil$ часов. Предикат «сумма не больше $H$» монотонен: большая скорость не увеличивает время. Одна проверка стоит $O(n)$, число проверок — $O(\log M)$, где $M=\max a_i$ (для $M\ge2$). Итого $O(n\log M)$.

Полный предикат здесь не пишем. На семинаре 4 предикат и цикл соберёте сами; в контесте акцент на монотонную функцию, не на «найти ключ в массиве».

К семинару 4

Бинарный поиск: собственный цикл, lower_bound / upper_bound, граничные случаи, поиск по ответу. Ноутбук служит для разбора; зачёт — задачи контеста на algo.ai.msu.ru.

Для самопроверки: проследите matryoshka(3) без запуска и объясните разницу между деревом вызовов и глубиной рекурсии.

Материалы

Пример с репкой и подключение ColabTurtle адаптированы из МФК, MSU2024/lec01_2024.ipynb. Матрёшка и функции фракталов добавлены для этой лекции. Блок бинарного поиска сохранён из предыдущей версии конспекта с уточнением инварианта границ.