Предисловие.........................................................................................................................12
Целевая аудитория..........................................................................................................................14
Содержание и структура книги ..................................................................................................15
Примерные учебные курсы.........................................................................................................17
Благодарности...................................................................................................................................17
Глава 1. Основные понятия рекурсивного программирования ...................................19
1.1. Распознание рекурсии...........................................................................................................19
1.2. Декомпозиция задачи............................................................................................................25
1.3. Рекурсивный код......................................................................................................................33
1.4. Индукция .....................................................................................................................................40
1.4.1. Математические доказательства методом индукции...................................................40
1.4.2. Рекурсивная убеждённость.....................................................................................................41
1.4.3. Императивное и декларативное программирование ................................................43
1.5. Рекурсия против итерации...................................................................................................44
1.6. Типы рекурсии...........................................................................................................................46
1.6.1. Линейная рекурсия.....................................................................................................................46
1.6.2. Хвостовая рекурсия....................................................................................................................46
1.6.3. Множественная рекурсия.........................................................................................................47
1.6.4. Взаимная рекурсия .....................................................................................................................47
1.6.5. Вложенная рекурсия ..................................................................................................................48
1.7. Упражнения.................................................................................................................................48
Глава 2. Методика рекурсивного мышления ..................................................................51
2.1. Шаблон проектирования рекурсивных алгоритмов .................................................51
2.2. Размер задачи ...........................................................................................................................52
2.3. Начальные условия .................................................................................................................54
2.4. Декомпозиция задачи............................................................................................................57
2.5. Рекурсивные условия, индукция и схемы......................................................................61
2.5.1. Рекурсивное мышление посредством схем .....................................................................61
2.5.2. Конкретные экземпляры задачи...........................................................................................65
2.5.3. Альтернативные обозначения................................................................................................66
Оглавление  7
2.5.4. Процедуры.......................................................................................................................................67
2.5.5. Несколько подзадач ...................................................................................................................69
2.6. Тестирование..............................................................................................................................71
2.7. Упражнения.................................................................................................................................75
Глава 3. Анализ времени выполнения рекурсивных алгоритмов ...............................77
3.1. Предварительные математические соглашения.........................................................77
3.1.1. Степени и логарифмы................................................................................................................78
3.1.2. Биномиальные коэффициенты ..............................................................................................78
3.1.3. Пределы и правило Лопиталя ................................................................................................79
3.1.4. Суммы и произведения.............................................................................................................79
3.1.5. Верхняя и нижняя границы.....................................................................................................85
3.1.6. Тригонометрия..............................................................................................................................86
3.1.7. Векторы и матрицы......................................................................................................................87
3.2. Временнáя сложность вычислений...................................................................................89
3.2.1. Порядок роста функций............................................................................................................90
3.2.2. Асимптотические обозначения..............................................................................................92
3.3. Рекуррентные соотношения................................................................................................95
3.3.1. Метод расширения......................................................................................................................99
3.3.2. Общий метод решения разностных уравнений............................................................107
3.4. Упражнения .............................................................................................................................119
Глава 4. Линейная рекурсия I: основные алгоритмы...................................................122
4.1. Арифметические операции...............................................................................................123
4.1.1. Степенная функция .................................................................................................................. 123
4.1.2. Медленное сложение.............................................................................................................. 127
4.1.3. Двойная сумма........................................................................................................................... 131
4.2. Системы счисления ..............................................................................................................132
4.2.1. Двоичное представление неотрицательного целого числа.................................... 133
4.2.2. Приведение десятичного числа к другому основанию ............................................ 135
4.3. Строки ........................................................................................................................................136
4.3.1. Обращение строки................................................................................................................... 137
4.3.2. Является ли строка палиндромом? ................................................................................... 137
4.4. Дополнительные задачи.....................................................................................................139
4.4.1. Сортировка выбором .............................................................................................................. 139
4.4.2. Схема Горнера............................................................................................................................ 141
4.4.3. Треугольник Паскаля............................................................................................................... 143
4.4.4. Резистивная цепь...................................................................................................................... 145
4.5. Упражнения ............................................................................................................................. 147
8  Оглавление
Глава 5. Линейная рекурсия II: хвостовая рекурсия ....................................................151
5.1. Логические функции............................................................................................................152
5.1.1. Есть ли в неотрицательном целом числе заданная цифра? ................................... 152
5.1.2. Равны ли строки?...................................................................................................................... 155
5.2. Алгоритмы поиска в списке..............................................................................................156
5.2.1. Линейный поиск........................................................................................................................ 157
5.2.2. Двоичный поиск в сортированном списке .................................................................... 159
5.3. Двоичные деревья поиска ................................................................................................161
5.3.1. Поиск элемента ......................................................................................................................... 163
5.3.2. Вставка элемента...................................................................................................................... 165
5.4. Схемы разбиения..................................................................................................................165
5.4.1. Основная схема разбиения.................................................................................................. 167
5.4.2. Метод разбиения Хоара......................................................................................................... 168
5.5. Алгоритм quickselect............................................................................................................173
5.6. Двоичный поиск корня функции....................................................................................174
5.7. Задача лесоруба..................................................................................................................... 177
5.8. Алгоритм евклида .................................................................................................................182
5.9. Упражнения .............................................................................................................................184
Глава 6. Множественная рекурсия I: «разделяй и властвуй» .....................................188
6.1. Отсортирован ли список? ..................................................................................................189
6.2. Сортировка ..............................................................................................................................190
6.2.1. Алгоритм сортировки слиянием......................................................................................... 191
6.2.2. Алгоритм быстрой сортировки............................................................................................ 194
6.3. Мажоритарный элемент списка...................................................................................... 197
6.4. Быстрое целочисленное умножение ............................................................................200
6.5. Умножение матриц...............................................................................................................203
6.5.1. Умножение матриц методом «разделяй и властвуй» ................................................ 203
6.5.2. Алгоритм Штрассена умножения матриц ....................................................................... 207
6.6. Задача укладки тримино....................................................................................................208
6.7. Задача очертания ..................................................................................................................213
6.8. Упражнения .............................................................................................................................219
Глава 7. Множественная рекурсия II: пазлы, фракталы и прочее..............................222
7.1. Путь через болото .................................................................................................................222
7.2. Ханойская башня...................................................................................................................226
Оглавление  9
7.3. Обходы дерева.......................................................................................................................230
7.3.1. Внутренний обход..................................................................................................................... 231
7.3.2. Прямой и обратный обходы................................................................................................. 233
7.4. Самый длинный палиндром в строке ...........................................................................234
7.5. Фракталы ..................................................................................................................................236
7.5.1. Снежинка Коха ........................................................................................................................... 236
7.5.2. Ковёр Серпиньского................................................................................................................. 242
7.6. Упражнения..............................................................................................................................245
Глава 8. Задачи подсчёта..................................................................................................250
8.1. Перестановки..........................................................................................................................251
8.2. Размещения с повторениями...........................................................................................253
8.3. Сочетания .................................................................................................................................255
8.4. Подъём по лестнице ............................................................................................................256
8.5. Путь по Манхэттену..............................................................................................................259
8.6. Триангуляция выпуклого многоугольника..................................................................260
8.7. Пирамиды из кругов.............................................................................................................263
8.8. Упражнения .............................................................................................................................265
Глава 9. Взаимная рекурсия .............................................................................................268
9.1. Чётность числа .......................................................................................................................269
9.2. Игры со многими игроками ..............................................................................................270
9.3. Размножение кроликов ......................................................................................................271
9.3.1. Зрелые и незрелые пары кроликов.................................................................................. 272
9.3.2. Родовое дерево кроликов .................................................................................................... 273
9.4. Задача о станциях водоочистки...................................................................................... 277
9.4.1. Переток воды между городами.......................................................................................... 278
9.4.2. Сброс воды в каждом городе.............................................................................................. 280
9.5. Циклические ханойские башни......................................................................................282
9.6. Грамматики и синтаксический анализатор на основе рекурсивного
спуска.........................................................................................................................................288
9.6.1. Лексический анализ входной строки............................................................................... 288
9.6.2. Синтаксический анализатор на основе рекурсивного спуска............................... 293
9.7. Упражнения..............................................................................................................................302
Глава 10. Выполнение программы..................................................................................306
10.1. Поток управления между подпрограммами ...........................................................309
10.2. Деревья рекурсии...............................................................................................................312
10  Оглавление
10.2.1. Анализ времени выполнения............................................................................................ 318
10.3. Программный стек .............................................................................................................320
10.3.1. Стековые кадры ...................................................................................................................... 320
10.3.2. Трассировка стека.................................................................................................................. 323
10.3.3. Пространственная сложность вычислений.................................................................. 325
10.3.4. Ошибки предельной глубины рекурсии и переполнения стека......................... 326
10.3.5. Рекурсия как альтернатива стеку .....................................................................................327
10.4. Мемоизация и динамическое программирование ..............................................332
10.4.1 Мемоизация.............................................................................................................................. 332
10.4.2. Граф зависимости и динамическое программирование ....................................... 336
10.5. Упражнения...........................................................................................................................340
Глава 11. Вложенная рекурсия и снова хвостовая.......................................................347
11.1. Хвостовая рекурсия и итерация................................................................................... 347
11.2. Итерационный подход к хвостовой рекурсии .......................................................351
11.2.1. Факториал................................................................................................................................. 352
11.2.2. Приведение десятичного числа к другому основанию.......................................... 353
11.3. Вложенная рекурсия .........................................................................................................356
11.3.1. Функция Аккермана .............................................................................................................. 356
11.3.2. Функция-91 Маккарти...........................................................................................................357
11.3.3. Цифровой корень....................................................................................................................357
11.4. К хвостовой и вложенной рекурсии через обобщённую функцию ..............359
11.4.1. Факториал................................................................................................................................. 359
11.4.2. Приведение десятичного числа к основанию b........................................................ 363
11.5. Упражнения...........................................................................................................................365
Глава 12. Множественная рекурсия III: перебор с возвратами .................................366
12.1. Введение................................................................................................................................ 367
12.1.1. Частичные и полные решения.......................................................................................... 367
12.1.2. Рекурсивная структура......................................................................................................... 369
12.2. Генерация комбинаторных объектов .........................................................................371
12.2.1. Подмножества ......................................................................................................................... 372
12.2.2. Перестановки............................................................................................................................377
12.3. Задача n ферзей .................................................................................................................381
12.3.1. Поиск всех решений............................................................................................................. 383
12.3.2. Поиск одного решения ........................................................................................................ 384
12.4. Задача о сумме элементов подмножества .............................................................. 387
12.5. Путь в лабиринте ................................................................................................................390
Оглавление  11
12.6. Судоку......................................................................................................................................396
12.7. Задача о рюкзаке 0–1 ......................................................................................................402
12.7.1. Стандартный алгоритм перебора с возвратами........................................................ 402
12.7.2. Алгоритм ветвей и границ ...................................................................................................407
12.8. Упражнения...........................................................................................................................411
Что ещё почитать...............................................................................................................416
Монографии о рекурсии ................................................................................................................... 416
Разработка и анализ алгоритмов .................................................................................................. 416
Функциональное программирование ......................................................................................... 417
Язык Python............................................................................................................................................ 417
Исследования в обучении и изучении рекурсии.................................................................... 417
Дополнительная литература............................................................................................418
Список рисунков.................................................................................................................420
Список таблиц.....................................................................................................................426
Список листингов ...............................................................................................................426
Предметный указатель .....................................................................................................432