Введение в рекурсивное программирование

Мануэль Рубио-Санчес

Введение 
в рекурсивное 
программирование

Introduction to
Recursive
Programming

Manuel Rubio-Sánchez

Москва, 2019

Мануэль Рубио-Санчес

Введение
в рекурсивное 
программирование

УДК   004.02
ББК   32.972
Р82

Р82   Мануэль Рубио-Санчес
Введение в рекурсивное программирование / пер. с англ. Е. В. Борисова. – М.: ДМК Пресс, 2019. – 436 с.: ил.

            ISBN 978-5-97060-703-9

Книга охватывает почти весь круг теоретических и практических вопросов, 
относящихся к рекурсии и рекурсивному программированию, что делает её прекрасным дополнением к уже существующим немногочисленным книгам на эту 
тему. На множестве примеров и задач – от простых к сложным – читатель постепенно погружается в рекурсию, учится мыслить рекурсивно и, отталкиваясь от 
декларативной парадигмы программирования, создавать рекурсивные алгоритмы с использованием пошаговой методики и специальных схем декомпозиции 
задач. При этом автор беспристрастно сопоставляет рекурсивные алгоритмы с 
итерационными, отмечая достоинства и недостатки тех и других. 
Все алгоритмы в книге реализованы на языке Python 3.
Издание предназначено студентам вузов, преподавателям, а также широкому 
кругу разработчиков, желающих эффективно применять рекурсивные алгоритмы 
в своей работе.

УДК  004.02
ББК  32.973

Copyright © 2018 by Taylor & Francis Group, LLC. CRC Press is an imprint of Taylor 
& Francis Group, an Informa business. All rights reserved. Russian-language edition copyright © 2019 by DMK Press. All rights reserved.

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

ISBN 978-1-4987-3528-5 (англ.)             © 2018 by Taylor & Francis Group, LLC
ISBN 978-5-97060-703-9 (рус.)               © Оформление, перевод на русский язык, издание,
 
         ДМК Пресс, 2019

Будущим поколениям

Оглавление

Предисловие .........................................................................................................................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

 Оглавление

Глава 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