Конспект: индукция и рекурсия

Понятия

Математическая индукция - доказательство утверждения для всех случаев двумя проверками: база и шаг. Шаг проверяется один раз для произвольного n.

Сильная индукция - в шаге разрешено опираться на все предыдущие случаи, а не только на соседний. Нужна, когда задача сводится к половине.

Структурная индукция - разбор по устройству объекта, а не по числу. Ею доказывают алгоритмы на деревьях, списках и выражениях.

Контракт рекурсивной функции - формулировка того, что функция обещает. Внутри тела вложенный вызов читается как «здесь работа уже сделана правильно».

Дерево вызовов - узел это вызов, потомки это вызовы, которые он делает. Число узлов даёт время, глубина даёт память.

Три части рекурсии

Часть	Что это	Чем ломается
база	случай, решаемый без вызовов	базы нет или она поймана только при одном значении
шаг	сведение к меньшему случаю и сборка ответа	части шага переставлены местами
мера	величина, строго убывающая при вызове	убывает, но не ограничена снизу - уход в минус

Цена по форме дерева вызовов

Форма	Время	Глубина	Пример
один вызов размера n-1	n	n	сумма списка рекурсией
два вызова размера n/2	n·log n	log n	сортировка слиянием
один вызов размера n/2	log n	log n	двоичный поиск
два вызова размера n-1	2^n	n	ханойские башни
два вызова, n-1 и n-2, с повторами	1,618^n	n	fib в лоб

Что унести

Инвариант цикла и есть индукция: инициализация это база, сохранение это шаг, завершение переводит доказанное в постусловие.

Шаг индукции проверяют на наименьшем значении, к которому его применяют. Разрыв между базой и областью применимости шага - это ровно та ошибка, из которой получаются «все лошади одной масти».

Рекурсию доказывают контрактом, а не прослеживанием вызовов вглубь. На глубине пять человек теряет нить, а доказательство от этого не меняется.

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

Экспонента бывает свойством задачи и бывает дефектом решения. У Ханоя ходов действительно 2^n - 1; у fib той же величины можно достичь за n шагов, если не считать одно и то же дважды.

В Python нет оптимизации хвостового вызова, и предел глубины около тысячи кадров. Рекурсию глубиной n пишут только при заведомо малом n, глубиной log n - свободно.

Ловушки джокера

База поймана не тем случаем, что нужен. У возведения в степень if n == 1: return a виснет на нуле, и чинится это базой n == 0: return 1 - а не if n <= 1: return a, тогда a⁰ вернёт a вместо 1. У проверки палиндрома if levo == pravo вместо >= роняет строки чётной длины: там нужно именно неравенство.

Мера убывает, но не ограничена снизу. Формально «уменьшается каждый раз» - и вызовы уходят в отрицательные числа.

Переставил части индуктивного шага. Число вызовов остаётся верным, ответ - нет, и заметить это можно только на входе от двух элементов.

Посчитал время и забыл про глубину. Обход дерева-цепочки из миллиона узлов делает столько же вызовов, сколько обход сбалансированного, и падает.

Решил, что ветвление само по себе даёт экспоненту. У сортировки слиянием ветвление есть, а экспоненты нет: подзадачи не повторяются и мельчают вдвое.

Проверь себя

Почему двух проверок индукции хватает для утверждения обо всех n?

Что такое контракт рекурсивной функции и почему он избавляет от прослеживания вызовов?

Какие две величины считают по дереву вызовов и какая из них отвечает за падение по стеку?

Чем экспонента ханойских башен отличается от экспоненты наивного Фибоначчи?