Модуль 2 · Лекция 5 · Левитин, §2.4–2.5

Анализ рекурсивных алгоритмов

Как по рекурсивному алгоритму составить рекуррентное соотношение, решить его и не попасться на экспоненциальную ловушку.

Цели и результаты обучения

Цель модуля — научиться анализировать алгоритмы, которые вызывают сами себя. Вместо сумм здесь появляются рекуррентные соотношения. Модуль опирается на план анализа и формулы сумм из модуля 1.

После модуля вы сможете:

применять общий план анализа к рекурсивному алгоритму;
составлять рекуррентное соотношение и находить начальное условие по строке выхода из рекурсии;
решать рекуррентности методом обратных подстановок и проверять ответ математической индукцией;
строить дерево рекурсивных вызовов и считать по нему вызовы;
решать рекуррентности с $\lfloor n/2\rfloor$ для $n = 2^k$ и переносить ответ на все $n$ по правилу гладкости;
распознавать повторные подзадачи и устранять их мемоизацией или итерацией;
оценивать память рекурсии через глубину стека и объяснять, что даёт хвостовая рекурсия.

Общий план для рекурсивных алгоритмов

План отличается от плана модуля 1 четвёртым и пятым шагами (Левитин, §2.4):

Выбрать параметр размера входа.
Определить базовую операцию.
Проверить, может ли число её выполнений различаться на входах одного размера. Если может — исследовать худший, средний и лучший случаи отдельно.
Составить рекуррентное соотношение с начальным условием для числа выполнений базовой операции.
Решить рекуррентность или хотя бы установить порядок роста решения.

Рекуррентное соотношение выражает $M(n)$ через значения при меньших аргументах. Например, $M(n) = M(n-1) + 1$: «работа для $n$ = работа для $n-1$ плюс одна операция». Таких последовательностей бесконечно много: $n$, $n + 5$, $n - 3$… Выбрать одну позволяет начальное условие — значение при наименьшем аргументе. Его берут из строки, на которой рекурсия останавливается: она показывает и наименьшее $n$, и число базовых операций при нём.

Метод обратных подстановок

Основной метод модуля — метод обратных подстановок. Порядок действий:

Запишите рекуррентность для $x(n)$.
Замените в ней $n$ на $n-1$, чтобы выразить $x(n-1)$ через $x(n-2)$, и подставьте в исходное уравнение.
Повторите для $x(n-2)$, затем для $x(n-3)$. Обычно трёх строк хватает, чтобы увидеть закономерность.
Запишите общую формулу после $i$ подстановок: $x(n)$ через $x(n-i)$ и $i$.
Выберите $i$ так, чтобы $n - i$ совпало с аргументом начального условия, и подставьте его значение.
Упростите (часто нужна формула суммы) и проверьте результат: подстановкой в уравнение и начальное условие или индукцией.

Строго говоря, закономерность из шага 4 сама требует доказательства индукцией по $i$. Левитин отмечает, что проще сначала получить ответ, а потом доказать его правильность. Так и поступим.

Пример: $x(n) = x(n-1) + n$, $x(0) = 0$ (Приложение B).

$$\begin{aligned} x(n) &= x(n-1) + n = [x(n-2) + (n-1)] + n = [x(n-3) + (n-2)] + (n-1) + n \\ &= x(n-i) + (n-i+1) + \dots + (n-1) + n \\ &\overset{i=n}{=} x(0) + 1 + 2 + \dots + n = \frac{n(n+1)}{2}. \end{aligned}$$

Проверка результата индукцией

Ответ, найденный по закономерности, — пока гипотеза. Математическая индукция превращает её в теорему. Докажем, что решение задачи о Ханойской башне $M(n) = 2M(n-1) + 1$, $M(1) = 1$ (вывод — ниже) равно $M(n) = 2^n - 1$ для всех $n \ge 1$.

Утверждение $P(n)$: $M(n) = 2^n - 1$.

База, $n = 1$: по начальному условию $M(1) = 1$, по формуле $2^1 - 1 = 1$. Совпадает.

Шаг. Пусть $n \ge 2$ и $P(n-1)$ верно: $M(n-1) = 2^{n-1} - 1$. Тогда по рекуррентности $$M(n) = 2M(n-1) + 1 = 2\left(2^{n-1} - 1\right) + 1 = 2^n - 2 + 1 = 2^n - 1,$$ то есть $P(n)$ верно.

Вывод. По принципу математической индукции $M(n) = 2^n - 1$ для всех $n \ge 1$.

Шаг индукции — это просто подстановка формулы в правую часть рекуррентности, база — проверка начального условия. Для рекуррентностей с $\lfloor n/2\rfloor$ используют сильную индукцию: предполагают верность для всех меньших значений (задачи C1 и C2).

Разбор 1. Факториал

$n! = 1\cdot2\cdot\ldots\cdot n = (n-1)!\cdot n$ при $n \ge 1$ и $0! = 1$. Отсюда рекурсивный алгоритм:

ALGORITHM F(n)
//Вычисляет n! рекурсивно
//Input: неотрицательное целое n
//Output: значение n!
if n = 0 return 1
else return F(n − 1) ∗ n

1. Размер входа

Для простоты — само число $n$, а не число битов в его записи.

2. Базовая операция

Умножение. Его число обозначим $M(n)$.

3. Случаи

Не различаются: всё определяет $n$.

4. Рекуррентность

Чтобы вычислить $F(n)$, нужно $M(n-1)$ умножений на $F(n-1)$ и ещё одно — умножить результат на $n$: $$M(n) = M(n-1) + 1 \ \text{ при } n > 0.$$ Начальное условие из строки if $n = 0$ return 1: рекурсия останавливается при $n = 0$ и умножений не делает, поэтому $M(0) = 0$.

5. Решение

$M(n) = M(n-1) + 1 = M(n-2) + 2 = M(n-3) + 3 = \dots = M(n-i) + i$. Начальное условие при $0$, берём $i = n$: $M(n) = M(0) + n = n$.

Класс

$M(n) = n \in \Theta(n)$.

Две разные рекурсии. Не путайте рекурсию значений $F(n) = F(n-1)\cdot n$, $F(0) = 1$ (что вычисляется) и рекурсию числа умножений $M(n) = M(n-1) + 1$, $M(0) = 0$ (сколько работы). Значения растут как $n!$, а работа линейна. Эту путаницу разбирает задача Ф2.

Простой цикл, накапливающий произведение, делает те же $n$ умножений, но без затрат времени и памяти на стек рекурсии. Это видно в визуализации: стек растёт до $n + 1$ записей, а умножения выполняются только на обратном пути.

Стек вызовов рекурсивного факториала: при спуске записи добавляются, при возврате снимаются, и на каждом возврате (кроме $F(0)$) выполняется одно умножение.

Разбор 2. Ханойская башня

Есть $n$ дисков разного размера и три стержня. Сначала все диски на первом стержне, самый большой внизу. Нужно перенести их на третий стержень, используя второй как вспомогательный. За один ход переносится один диск; класть больший диск на меньший нельзя.

Рекурсивное решение: чтобы перенести $n > 1$ дисков с A на C, нужно (1) перенести $n-1$ диск с A на B, используя C; (2) переложить самый большой диск с A на C; (3) перенести $n-1$ диск с B на C, используя A. При $n = 1$ диск просто перекладывается.

ALGORITHM Hanoi(n, from, to, aux)
//Переносит n дисков со стержня from на стержень to, aux — вспомогательный
if n = 1
    переложить диск с from на to
else
    Hanoi(n − 1, from, aux, to)
    переложить диск с from на to
    Hanoi(n − 1, aux, to, from)

1. Размер входа

Число дисков $n$.

2. Базовая операция

Перенос одного диска. Число ходов — $M(n)$.

3. Случаи

Не различаются: $M(n)$ зависит только от $n$.

4. Рекуррентность

Два переноса башни из $n-1$ диска и один ход: $$M(n) = M(n-1) + 1 + M(n-1) = 2M(n-1) + 1 \ \text{ при } n > 1, \qquad M(1) = 1.$$ Начальное условие очевидно: один диск — один ход.

5. Решение

Обратными подстановками ниже: $M(n) = 2^n - 1$.

Класс

$M(n) = 2^n - 1 \in \Theta(2^n)$ — экспоненциальный алгоритм.

Вывод по шагам

Нажимайте на последнюю строку или на кнопку, чтобы открыть следующий шаг.

$M(n) = 2M(n-1) + 1$ — подставим $M(n-1) = 2M(n-2) + 1$
$\phantom{M(n)} = 2[2M(n-2) + 1] + 1 = 2^2M(n-2) + 2 + 1$ — подставим $M(n-2) = 2M(n-3) + 1$
$\phantom{M(n)} = 2^2[2M(n-3) + 1] + 2 + 1 = 2^3M(n-3) + 2^2 + 2 + 1$ — видна закономерность
$\phantom{M(n)} = 2^iM(n-i) + 2^{i-1} + \dots + 2 + 1 = 2^iM(n-i) + 2^i - 1$ — после $i$ подстановок; сумма — геометрическая прогрессия $\sum_{j=0}^{i-1}2^j = 2^i - 1$
Начальное условие задано при $n = 1$, то есть нужно $n - i = 1$: $i = n - 1$ — не $i = n$: значения $M(0)$ нет в условии
$M(n) = 2^{n-1}M(1) + 2^{n-1} - 1 = 2^{n-1} + 2^{n-1} - 1 = 2^n - 1$ — ответ
Проверка: $M(1) = 2 - 1 = 1$; $2(2^{n-1} - 1) + 1 = 2^n - 1$. Строгое доказательство индукцией — выше.

Дерево рекурсивных вызовов

Если алгоритм вызывает себя больше одного раза, полезно построить дерево рекурсивных вызовов: узлы — вызовы, подписанные параметром, дети — вызовы, сделанные изнутри. У Ханоя корень $n$, у каждого узла $m > 1$ два ребёнка $m - 1$. На уровне $l$ находится $2^l$ узлов, уровни нумеруются от $0$ до $n-1$. Общее число вызовов:

$$C(n) = \sum_{l=0}^{n-1} 2^l = 2^n - 1.$$

Число вызовов совпадает с числом ходов, и это не случайность: каждый вызов делает ровно один ход «своим» диском. В визуализации ниже $k$-й ход делает $k$-й узел дерева при чтении слева направо.

Алгоритм экспоненциальный, но он не плох: можно доказать, что меньшим числом ходов задачу не решить. Сложность заложена в самой задаче. Общий урок Левитина:

С рекурсивными алгоритмами нужно быть осторожным: их краткость может скрывать неэффективность.

Интерактивная модель

Режим «Алгоритм» проигрывает рекурсию по ходам. Слева — диски и счётчик ходов. Справа — дерево вызовов (при $n \le 5$): синим залит текущий вызов, контуром выделены вызовы в стеке, бледным — вызовы, которые уже сделали свой ход. Ниже — стек вызовов: его глубина никогда не превышает $n$. Режим «Попробуй сам» позволяет переложить диски вручную и сравнить своё число ходов с минимумом $2^n - 1$.

Ханойская башня: $n$ от 1 до 8, ход $k$ из $2^n - 1$, дерево вызовов, стек и таблица $M(n)$.

Таблица под моделью показывает удвоение: $M(n)/M(n-1) = 2 + \frac{1}{M(n-1)} \to 2$. Каждый новый диск удваивает работу. При одном ходе в секунду 64 диска потребовали бы $2^{64} - 1 \approx 1{,}8\cdot10^{19}$ секунд — сотни миллиардов лет.

Разбор 3. Число двоичных цифр: BinRec

Рекурсивная версия алгоритма Binary из модуля 1:

ALGORITHM BinRec(n)
//Input: положительное целое n
//Output: число цифр в двоичной записи n
if n = 1 return 1
else return BinRec(⌊n/2⌋) + 1

1. Размер входа

Число $n$.

2. Базовая операция

Сложение «$+1$». Число сложений — $A(n)$.

3. Случаи

Не различаются.

4. Рекуррентность

$A(\lfloor n/2\rfloor)$ сложений на вложенный вызов и ещё одно: $$A(n) = A(\lfloor n/2\rfloor) + 1 \ \text{ при } n > 1, \qquad A(1) = 0.$$ При $n = 1$ рекурсия останавливается без сложений.

5. Решение

Из-за $\lfloor n/2\rfloor$ обратные подстановки «спотыкаются» на $n$, не являющихся степенью двойки. Стандартный приём — решить для $n = 2^k$: $$A(2^k) = A(2^{k-1}) + 1 = A(2^{k-2}) + 2 = \dots = A(2^{k-i}) + i = \dots = A(2^0) + k = k.$$ Возвращаясь к $n = 2^k$, $k = \log_2 n$: $A(n) = \log_2 n$.

Класс

$A(n) \in \Theta(\log n)$ для всех $n$ — по правилу гладкости.

Почему ответ для степеней двойки годится для всех $n$. Правило гладкости (Левитин, Приложение B): пусть $T(n)$ в конечном счёте неубывающая, а $f(n)$ — гладкая функция, то есть в конечном счёте неубывающая и $f(2n) \in \Theta(f(n))$. Если $T(n) \in \Theta(f(n))$ для $n$, являющихся степенями $b \ge 2$, то $T(n) \in \Theta(f(n))$ для всех $n$. Функции $\log n$, $n$, $n\log n$, $n^\alpha$ ($\alpha \ge 0$) гладкие; $2^n$ — нет, так как $2^{2n} = 4^n \notin \Theta(2^n)$.

Для BinRec $A(n)$ неубывает, $\log n$ гладкая, поэтому $A(n) \in \Theta(\log n)$ для всех $n$. Можно уточнить и точную формулу: $A(n) = \lfloor\log_2 n\rfloor$. Это на единицу меньше, чем число сравнений в нерекурсивном Binary ($\lfloor\log_2 n\rfloor + 1$): там считались сравнения $n > 1$, здесь — сложения.

Каждый вызов делит $n$ пополам, то есть отбрасывает последний бит. Цепочка вызовов на единицу длиннее числа сложений.

Предупреждающий пример: числа Фибоначчи

Числа Фибоначчи: $0, 1, 1, 2, 3, 5, 8, 13, \dots$ — заданы рекуррентностью $F(n) = F(n-1) + F(n-2)$ при $n > 1$, $F(0) = 0$, $F(1) = 1$. Явная формула (Левитин, §2.5, Приложение B):

$$F(n) = \frac{1}{\sqrt5}\left(\varphi^n - \hat\varphi^n\right), \qquad \varphi = \frac{1+\sqrt5}{2} \approx 1{,}61803, \quad \hat\varphi = -\frac1\varphi \approx -0{,}61803.$$

Так как $|\hat\varphi| < 1$, слагаемое $\hat\varphi^n$ быстро исчезает, и $F(n) \in \Theta(\varphi^n)$ (золотое сечение φ).

Наивная рекурсия

ALGORITHM F(n)
//Вычисляет n-е число Фибоначчи рекурсивно по определению
//Input: неотрицательное целое n
//Output: n-е число Фибоначчи
if n ≤ 1 return n
else return F(n − 1) + F(n − 2)

1–3. Размер, операция, случаи

Размер $n$; базовая операция — сложение; случаи не различаются.

4. Рекуррентность

$A(n-1)$ и $A(n-2)$ сложений на два вызова и одно на их сумму: $$A(n) = A(n-1) + A(n-2) + 1 \ \text{ при } n > 1, \qquad A(0) = 0,\ A(1) = 0.$$

5. Решение

Правая часть не равна нулю (неоднородная рекуррентность). Перепишем: $$[A(n) + 1] - [A(n-1) + 1] - [A(n-2) + 1] = 0$$ и заменим $B(n) = A(n) + 1$: $B(n) = B(n-1) + B(n-2)$, $B(0) = B(1) = 1$. Это последовательность Фибоначчи, начатая с двух единиц, то есть сдвинутая на шаг вперёд: $B(n) = F(n+1)$. Поэтому $$A(n) = F(n+1) - 1 = \frac{1}{\sqrt5}\left(\varphi^{n+1} - \hat\varphi^{n+1}\right) - 1.$$

Класс

$A(n) \in \Theta(\varphi^n)$ — экспоненциальный. По числу битов $b$ — двойная экспонента $\varphi^{\Theta(2^b)}$.

Причина неэффективности видна в дереве вызовов: одни и те же значения вычисляются снова и снова. Это повторные подзадачи: $F(n-2)$ считается и из $F(n)$, и внутри $F(n-1)$, и дальше всё повторяется. Рекуррентность это и подсказывает: два вызова с размерами лишь чуть меньше $n$.

Дерево вызовов $F(n)$: красным отмечены повторные вычисления. Включите мемоизацию — дерево сжимается до цепочки, пунктирные узлы берут готовое значение из таблицы.

Мемоизация: функции с памятью

Устранить повторы, сохранив рекурсию, позволяет мемоизация. У Левитина этот приём называется memory functions и разобран в §8.2 (на задаче о рюкзаке): рекурсия идёт сверху вниз, но перед вычислением проверяется таблица, и каждое значение вычисляется один раз.

ALGORITHM MemoFib(n)
//Функция с памятью; F[0..n] заранее заполнена значениями −1 («не вычислено»)
if F[n] < 0
    if n ≤ 1  F[n] ← n
    else  F[n] ← MemoFib(n − 1) + MemoFib(n − 2)
return F[n]

Каждое $F(k)$ при $2 \le k \le n$ вычисляется один раз и стоит одно сложение: $A_{memo}(n) = n - 1$. Вызовов $2n - 1$ (при $n \ge 2$): $n + 1$ первых вызовов — по одному на каждое $F(0), \dots, F(n)$ — и $n - 2$ обращения к уже готовым значениям. Цена — таблица из $n + 1$ ячейки и стек глубины $n$.

Итерация

Ещё проще вычислять числа подряд, снизу вверх:

ALGORITHM Fib(n)
//Вычисляет n-е число Фибоначчи итеративно
F[0] ← 0; F[1] ← 1
for i ← 2 to n do
    F[i] ← F[i − 1] + F[i − 2]
return F[n]

Алгоритм делает $n - 1$ сложений, $\Theta(n)$. Массив не нужен: каждый шаг использует только два предыдущих значения, поэтому хватает двух переменных и памяти $O(1)$:

ALGORITHM Fib2(n)
//Две переменные вместо массива
if n = 0 return 0
a ← 0; b ← 1          //a = F(i − 1), b = F(i)
for i ← 2 to n do
    c ← a + b
    a ← b; b ← c
return b

Итог: одна и та же рекуррентность значений может приводить к экспоненциальному ($\Theta(\varphi^n)$) или линейному ($n - 1$ сложений) алгоритму. Всё зависит от того, решаются ли подзадачи повторно.

Рекурсия против итерации

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

Алгоритм	Наибольшая глубина стека	Итеративная версия
Факториал $F(n)$	$n + 1$	$O(1)$
Ханойская башня	$n$	есть, без рекурсии
BinRec$(n)$	$\lfloor\log_2 n\rfloor + 1$	Binary, $O(1)$
Наивный Фибоначчи	$n$ (при $2^{\Theta(n)}$ вызовов)	Fib2, $O(1)$
Сумма массива Sum (ниже)	$n + 1$	$O(1)$
Максимум делением пополам MaxDC	$\lceil\log_2 n\rceil + 1$	MaxElement, $O(1)$

Глубина — это длина самой длинной ветви дерева вызовов, а не число узлов. У Ханоя $2^n - 1$ вызовов, но одновременно в стеке не больше $n$.

Свой пример 1. Рекурсивная сумма массива

ALGORITHM Sum(A[0..n − 1])
//Сумма элементов массива
if n = 0 return 0
else return Sum(A[0..n − 2]) + A[n − 1]

1–3. Размер, операция, случаи

Размер $n$; базовая операция — сложение; случаи не различаются.

4. Рекуррентность

$S(n) = S(n-1) + 1$ при $n > 0$, $S(0) = 0$ (пустой массив — ни одного сложения).

5. Решение

Как у факториала: $S(n) = n$.

Класс

Время $\Theta(n)$, память стека $\Theta(n)$ — глубина $n + 1$.

Цикл делает те же $n$ сложений с памятью $O(1)$. Можно ли сохранить рекурсивную запись и не платить стеком? Это вопрос о хвостовой рекурсии.

Хвостовая рекурсия

Вызов называется хвостовым, если он — последнее действие функции: его результат сразу возвращается, без дальнейших вычислений (хвостовая рекурсия). В Sum после вызова ещё выполняется сложение, поэтому вызов не хвостовой. Перенесём накопление в параметр-аккумулятор:

ALGORITHM SumAcc(A[0..n − 1], i, acc)
//Вызов: SumAcc(A, 0, 0)
if i = n return acc
else return SumAcc(A, i + 1, acc + A[i])

Теперь вызов хвостовой: текущая запись стека больше не нужна, её можно переиспользовать, то есть превратить рекурсию в цикл. Это и есть устранение хвостовой рекурсии (tail-recursion elimination). У Левитина этой темы нет; она разобрана в CLRS (Cormen и др., задачи гл. 7 о глубине стека быстрой сортировки): хвостовой вызов заменяется присваиванием параметров и переходом в начало процедуры. Для SumAcc дополнительная память после этого падает с $\Theta(n)$ до $\Theta(1)$. Число сложений не меняется: $n$.

Python хвостовую рекурсию не оптимизирует. Каждый вызов, хвостовой или нет, занимает кадр стека, а глубина ограничена (по умолчанию sys.getrecursionlimit() возвращает 1000). Поэтому sum_acc на массиве из 5000 элементов падает с RecursionError, а обычный цикл спокойно обрабатывает $10^6$ элементов:

import sys

def sum_acc(a, i=0, acc=0):
    if i == len(a):
        return acc
    return sum_acc(a, i + 1, acc + a[i])   # хвостовой вызов, но стек всё равно растёт

print(sys.getrecursionlimit())             # 1000
try:
    sum_acc(list(range(5000)))
except RecursionError:
    print("RecursionError: глубина больше лимита")

def sum_loop(a):                            # то же самое после устранения хвостовой рекурсии
    acc = 0
    for x in a:
        acc += x
    return acc

print(sum_loop(list(range(10**6))))

Практический вывод: в Python глубокую линейную рекурсию переписывают циклом вручную.

Свой пример 2. Максимум делением пополам

Найдём максимум массива рекурсивно: разделим массив на две половины, найдём максимум каждой и сравним.

ALGORITHM MaxDC(A[l..r])
//Наибольший элемент A[l..r]; вызов MaxDC(A[0..n − 1])
if l = r return A[l]
m ← ⌊(l + r)/2⌋
a ← MaxDC(A[l..m])
b ← MaxDC(A[m + 1..r])
if a > b return a
else return b

1. Размер входа

Число элементов $n = r - l + 1$.

2. Базовая операция

Сравнение $a > b$.

3. Случаи

Не различаются: сравнение выполняется в каждом вызове с $n > 1$ независимо от значений.

4. Рекуррентность

Левая половина содержит $\lceil n/2\rceil$ элементов, правая — $\lfloor n/2\rfloor$: $$C(n) = C(\lceil n/2\rceil) + C(\lfloor n/2\rfloor) + 1 \ \text{ при } n > 1, \qquad C(1) = 0.$$

5. Решение

Для $n = 2^k$ обе половины равны: $C(2^k) = 2C(2^{k-1}) + 1$. Подстановки — как у Ханоя: $$C(2^k) = 2^2C(2^{k-2}) + 2 + 1 = \dots = 2^iC(2^{k-i}) + 2^i - 1 \overset{i=k}{=} 2^k\cdot0 + 2^k - 1 = n - 1.$$ Для произвольного $n$ формула $C(n) = n - 1$ тоже верна — это доказывается индукцией (задача C1).

Класс

$C(n) = n - 1 \in \Theta(n)$.

Вывод: сравнений столько же, сколько у MaxElement: каждое сравнение отсеивает ровно одного кандидата. Но рекурсия «пополам» даёт глубину стека всего $\lceil\log_2 n\rceil + 1$, а не $n$, как у «линейной» рекурсии Sum. Форма дерева вызовов определяет память, а не только время.

Свой пример 3. Быстрое возведение в степень

Нерекурсивный вариант этого алгоритма Левитин разбирает в §6.5; здесь — рекурсивная версия и её анализ через рекуррентное соотношение.

Вычислим $a^n$ ($n \ge 1$), используя $a^n = (a^{\lfloor n/2\rfloor})^2$ при чётном $n$ и $a^n = (a^{\lfloor n/2\rfloor})^2\cdot a$ при нечётном.

ALGORITHM Power(a, n)
//Input: число a и целое n ≥ 1
//Output: a^n
if n = 1 return a
h ← Power(a, ⌊n/2⌋)
if n mod 2 = 0 return h ∗ h
else return h ∗ h ∗ a

1. Размер входа

Число битов показателя $b = \lfloor\log_2 n\rfloor + 1$ (так размер измеряет Левитин для возведения в степень, §6.5). Для краткости формулы ниже записаны и через $n$.

2. Базовая операция

Умножение. Число умножений — $M(n)$.

3. Случаи

Различаются: чётный показатель стоит 1 умножение, нечётный — 2. Среди всех $n$ с одним и тем же числом битов $b$ число умножений зависит от того, сколько единиц в двоичной записи $n$.

4. Рекуррентность

$M(n) = M(\lfloor n/2\rfloor) + 1 + (n \bmod 2)$ при $n > 1$, $M(1) = 0$.

5. Решение

Лучший случай при данном $b$ — одна единица в записи, $n = 2^{b-1}$: все промежуточные показатели чётные, и $$M(2^k) = M(2^{k-1}) + 1 = \dots = M(1) + k = k, \quad\text{то есть } M = b - 1.$$ Худший случай при данном $b$ — все единицы, $n = 2^b - 1 = 11\ldots1_2$: каждый уровень, кроме последнего, стоит 2 умножения, $M = 2(b-1)$. Оба входа имеют один и тот же размер $b$. В общем случае $\lfloor\log_2 n\rfloor \le M(n) \le 2\lfloor\log_2 n\rfloor$ (доказательство — задача C2).

Класс

$M(n) \in \Theta(\log n)$ — против $n - 1$ умножений у наивного алгоритма. Например, $a^{1000}$: 14 умножений вместо 999.

Точная формула, проверенная программой для всех $n \le 2000$: $M(n) = \lfloor\log_2 n\rfloor + \nu(n) - 1$, где $\nu(n)$ — число единиц в двоичной записи $n$. Для $n = 1000 = 1111101000_2$: $9 + 6 - 1 = 14$.

Эмпирическая проверка

План эксперимента тот же, что в модуле 1. Для рекурсивной функции счётчик удобно держать в глобальной переменной или передавать списком. Его увеличивают в том месте, где выполняется базовая операция, — не при входе в функцию, если считаются не вызовы.

moves = 0

def hanoi(n, src, dst, aux):
    global moves
    if n == 1:
        moves += 1                     # перенос одного диска
        return
    hanoi(n - 1, src, aux, dst)
    moves += 1
    hanoi(n - 1, aux, dst, src)

for n in range(1, 21):
    moves = 0
    hanoi(n, "A", "C", "B")
    print(n, moves, 2**n - 1, moves == 2**n - 1)

Ханойская башня: число ходов совпадает с 2^n − 1, логарифмическая шкала — Ханойская башня, $n = 1..20$ (логарифмическая шкала): точки лежат на прямой $2^n - 1$. Модель стержней проверяла правила на каждом ходе; глубина рекурсии ровно $n$.

Фибоначчи: сложения наивной рекурсии F(n+1) − 1 и мемоизированной n − 1 — Фибоначчи: наивная рекурсия делает $F(n+1) - 1$ сложений (на логарифмической шкале — прямая, признак экспоненты), мемоизация — $n - 1$. Отношение $A(n)/A(n-1)$ при $n = 25$ равно $1{,}61804 \approx \varphi$.

BinRec: число сложений равно floor(log2 n) — BinRec: $A(n) = \lfloor\log_2 n\rfloor$ для всех $n$ от 1 до 5000; в степенях двойки ступенька касается кривой $\log_2 n$.

Быстрое возведение в степень: число умножений между log2 n и 2 log2 n — Power: все точки лежат между $\log_2 n$ и $2\log_2 n$; нижнюю границу дают степени двойки, верхнюю — числа вида $2^k - 1$.

Выводы. Для факториала ($n$ умножений, глубина $n + 1$), Ханоя ($2^n - 1$ ходов и вызовов), BinRec ($\lfloor\log_2 n\rfloor$), Фибоначчи ($F(n+1) - 1$ и $n - 1$), MaxDC ($n - 1$ сравнений), Power ($\lfloor\log_2 n\rfloor + \nu(n) - 1$) и Sum ($n$) счётчик совпал с формулой при всех проверенных $n$. Опыт с sum_acc подтвердил, что Python не устраняет хвостовую рекурсию: при $n = 5000$ возникает RecursionError.

Квиз модуля 2

Десять вопросов: рекуррентности, начальные условия, классы, стек и хвостовая рекурсия.

Задачи

У каждой задачи три раскрывающихся блока: подсказка, ответ и полное решение.

Уровень A: прямое применение

Уровень B: решение рекуррентностей

Уровень C: доказательство индукцией

Найди ошибку

Эмпирическая задача

Резюме

План анализа рекурсивного алгоритма отличается шагами 4 и 5: вместо суммы составляется и решается рекуррентное соотношение, а начальное условие берётся из строки выхода из рекурсии.
Метод обратных подстановок: подставить три раза, увидеть закономерность после $i$ шагов, выбрать $i$ до начального условия. Результат проверяется индукцией.
Факториал: $M(n) = n$. Рекуррентность значений и рекуррентность числа операций — разные вещи.
Ханойская башня: $M(n) = 2^n - 1$, по дереву вызовов $\sum_{l=0}^{n-1}2^l = 2^n - 1$. Краткость рекурсии может скрывать неэффективность.
BinRec: решаем для $n = 2^k$, переносим на все $n$ правилом гладкости; точно $\lfloor\log_2 n\rfloor$.
Наивный Фибоначчи — $\Theta(\varphi^n)$ из-за повторных подзадач. Мемоизация (memory functions, §8.2) и итерация дают $n - 1$ сложений; итерации хватает двух переменных.
Память рекурсии — глубина стека. Хвостовую рекурсию можно заменить циклом, но Python этого не делает.

Шпаргалка формул

факториал

$M(n) = M(n-1) + 1,\ M(0) = 0 \Rightarrow M(n) = n$

Ханойская башня

$M(n) = 2M(n-1) + 1,\ M(1) = 1 \Rightarrow 2^n - 1$

дерево вызовов Ханоя

$C(n) = \sum_{l=0}^{n-1} 2^l = 2^n - 1$

BinRec

$A(n) = A(\lfloor n/2\rfloor) + 1,\ A(1) = 0 \Rightarrow \lfloor\log_2 n\rfloor$

наивный Фибоначчи

$A(n) = A(n-1) + A(n-2) + 1 \Rightarrow F(n+1) - 1 \in \Theta(\varphi^n)$

Фибоначчи, память / итерация

$n - 1$ сложений

$x(n) = x(n-1) + c$

$x(n) = x(0) + cn$

$x(n) = x(n-1) + n$

$x(n) = x(0) + \frac{n(n+1)}{2}$

$x(n) = 2x(n-1) + 1$

$x(n) = 2^n x(0) + 2^n - 1$

$x(n) = x(n/2) + 1$, $n = 2^k$

$x(n) = x(1) + \log_2 n$

$\varphi$

$\varphi = \frac{1+\sqrt5}{2} \approx 1{,}618$, $F(n) \in \Theta(\varphi^n)$

правило гладкости

$T$ в конечном счёте неубывающая, $f$ гладкая, $T(n) \in \Theta(f(n))$ для $n = b^k$ ($b \ge 2$) $\Rightarrow$ для всех $n$