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

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

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

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 copy-
right © 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

 Оглавление

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. Приведение десятичного числа к к другому основанию ...................................... 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

Предисловие

Рекурсия – одно из самых фундаментальных понятий в информатике 
и ключевая методика программирования, позволяющая, подобно итерации, 
многократно повторять вычисления. Это достигается за счёт использования 
методов, вызывающих самих себя, когда решение исходной 
задачи сводится к решению нескольких экземпляров той же самой 
задачи, но меньшего размера. Крайне важно то, что рекурсия – мощный 
подход к решению задач, позволяющий программистам разрабатывать 
лаконичные, интуитивно понятные и изящные алгоритмы.
Несмотря на значимость рекурсии для создания алгоритмов, большинство 
книг по программированию не уделяет внимания её деталям. 
Обычно они посвящают ей лишь одну-единственную главу или коротенький 
раздел, которых зачастую недостаточно для освоения понятий, 
необходимых для овладения предметом. Исключениями являются книги [
11], [14], [15], посвящённые исключительно рекурсии. Данная книга 
также рассматривает рекурсию со всех сторон, но несколько отличается 
от предыдущих.
Многие преподаватели программирования и исследователи в области 
обучения информатике признают, что рекурсия трудна для студента-
новичка. С учётом этого книга содержит несколько элементов,  усиливающих 
ее педагогический эффект. Во-первых, перед погружением в 
более сложный материал она предлагает множество простых задач для 
закрепления основных понятий. Кроме того, одно из основных достоинств 
книги – использование пошаговой методики и специально созданных 
схем, сопровождающих и иллюстрирующих процесс разработки 
рекурсивных алгоритмов. Книга также содержит специальные главы 
по комбинаторным задачам и взаимной рекурсии. Эти темы позволяют 
расширить понимание рекурсии студентами, побуждая их применять 
освоенные понятия несколько иначе или более изощрённо. Наконец, 
вводные курсы программирования обычно сосредоточиваются на императивной 
парадигме программирования, когда студенты изучают 
прежде всего итерацию, усваивая то и овладевая тем, как работают программы. 
Рекурсия же подразумевает совсем иной способ мышления, 
когда упор делается на то, что вычисляют программы. В связи с этим 
некоторые исследователи призывают при объяснении рекурсии не раскрывать 
или откладывать на потом механизмы работы рекурсивных 

Предисловие  13

программ (поток управления, деревья рекурсии, программный стек 
или связь между итерацией и хвостовой рекурсией), так как усвоенные 
идеи и приобретённые навыки итеративного программирования 
могут существенно помешать овладению рекурсией и декларативным 
программированием. По этой причине темы, связанные с итерацией и 
исполнением программы, раскрываются в конце книги, когда читатель 
уже овладел разработкой рекурсивных алгоритмов с чисто декларативных 
позиций.
В книге также есть большая глава по теоретическому анализу стоимости 
вычислений рекурсивных программ. С одной стороны, она содержит 
обширный материал о рекуррентных соотношениях – основном 
математическом инструменте анализа рекурсивных алгоритмов 
и времени их выполнения. С другой стороны, она содержит раздел с 
предварительными математическими сведениями, в которых даётся 
обзор понятий и свойств, необходимых не только для решения рекуррентных 
соотношений, но и для понимания условий и решений вычислительных 
задач этой книги. В связи с этим раздел предоставляет ещё 
и возможность попутно изучить или вспомнить немного элементарной 
математики. Желательно, чтобы читатель изучил этот материал, так как 
он важен во многих областях информатики.
Примеры кода написаны на языке Python 3, который сегодня является, 
видимо, самым популярным языком для вводных курсов программирования 
в ведущих университетах. Все они были проверены в 
основном в SPYDER (Scientifi c PYthon Development EnviRonment – научная 
среда разработки на языке Python). Читатель должен понимать, 
что цель книги не в изучении языка Python, а в овладении при решении 
задач навыками рекурсивного мышления. Поэтому такие аспекты, 
как простота и удобочитаемость кода, были важнее его эффективности. 
По этой причине код не содержит расширенных возможностей языка 
Python. Так что студенты, знакомые с такими языками программирования, 
как C++ или Java, должны без усилий понять этот код. Конечно, 
методы из данной книги могут быть реализованы различными способами, 
и читатели вольны писать более эффективные версии с включением 
более сложных конструкций языка Python или разрабатывать 
альтернативные алгоритмы. Наконец, в книге приводятся рекурсивные 
варианты итерационных алгоритмов, которые обычно сопутствуют 
другим хорошо известным рекурсивным задачам. Например, в книге 
приводятся рекурсивные версии метода разделения Хоара, используемого 
в алгоритме быстрой сортировки, или метода слияния в алгоритме 
сортировки слиянием.

 Предисловие

В конце каждой главы предлагаются многочисленные упражнения, 
полные решения которых включены в руководство преподавателя, доступное 
на официальном веб-сайте книги (см. www.crcpress.com). Многие 
из них связаны с задачами из основного текста книги, что делает их 
подходящими кандидатами для экзаменов и заданий.
Код из данного текста также будет доступен для загрузки на веб-сайте 
книги. Кроме того, я буду поддерживать дополнительный веб-сайт 
книги https://sites.google.com/view/recursiveprogrammingintro/. Буду более 
чем признателен читателям за присланные комментарии, предложения 
по усовершенствованию, альтернативный (более ясный или эффективный) 
код, версии на других языках программирования или обнаруженные 
опечатки. Письма присылайте, пожалуйста, по адресу: recursion.
book@gmail.com.

Целевая аудитория

Основная цель книги – на множестве примеров разнообразных вычислительных 
задач научить студентов думать и программировать 
рекурсивно. Она предназначена главным образом для студентов, обучающихся 
информатике или связанным с ней техническим дисциплинам, 
которые охватывают программирование и алгоритмы (например, 
биоинформатика, инжиниринг, математика, физика и т. д.). Книга может  
быть также полезна для программистов-любителей, студентов массовых 
открытых сетевых курсов или более опытных профессионалов, 
которые хотели бы освежить знакомый им материал или взглянуть на 
него иначе, проще.
Чтобы понять код в книге, студенты должны владеть некоторыми 
базовыми навыками программирования. Читатель должен быть знаком 
с такими понятиями базового курса программирования, как выражения, 
переменные, условные и циклические конструкции, методы, 
параметры и элементарные структуры данных (массивы или списки). 
Эти понятия не объясняются в книге. Кроме того, код в книге следует 
процедурной парадигме программирования и не использует объектно-
ориен тированные средства. Что касается языка Python, то знание его 
основ может быть полезно, но совсем не обязательно. Наконец, студент 
должен владеть математикой в объёме средней школы.
Книга также может оказаться полезной и для преподавателей информатики, 
причём не только как справочник с большой коллекцией 
разнообразных задач, но и, принимая во внимание описанные методику 
и схемы, как пособие по разработке рекурсивных решений. Более 

Содержание и структура книги  15

того, преподаватели могут использовать её структуру для организации 
своих занятий. Книга могла бы использоваться как приемлемый 
учебник по вводному (CS1/2) курсу программирования, в углублённых 
курсах – по разработке и анализу алгоритмов (она, например, охватывает 
такие темы, как «разделяй и властвуй» или перебор с возвратами). 
Кроме того, поскольку книга закладывает прочный фундамент рекурсии, 
она может использоваться в качестве дополнительного материала 
в курсах, посвящённых структурам данных или функциональному 
программированию. Однако читатель должен иметь в виду, что книга 
не касается ни структур данных, ни понятий функционального программирования.


Содержание и структура книги

Глава 1 предполагает, что читатель не имеет никакого представления о 
рекурсии, и вводит основные её понятия, систему обозначений и даёт 
первые примеры рекурсивного кода.
Глава 2 описывает методику разработки рекурсивных алгоритмов, 
а также схем, способствующих рекурсивному мышлению, которые 
иллюст рируют исходную задачу и её декомпозицию (разложение) на 
меньшие экземпляры той же самой задачи. Это одна из самых важных 
глав, так как методика и рекурсивные схемы будут использоваться во 
всей остальной части книги. Желательно, чтобы читатели ознакомились 
с этой главой независимо от их предыдущих знаний о рекурсии.
Глава 3 даёт обзор основных математических принципов и обозначений. 
Кроме того, она описывает методы решения рекуррентных соотношений, 
которые являются основным математическим инструментом 
для теоретического анализа стоимости вычислений рекурсивных 
алгоритмов. Глава может быть опущена во вводных курсах по рекурсии. 
Однако она помещена в начало книги, чтобы заложить почву для 
оценки и сравнения эффективности различных алгоритмов, что важно 
в расширенных курсах по разработке и анализу алгоритмов.
Глава 4 посвящена «линейной рекурсии». Этот тип рекурсии приводит 
к простейшим рекурсивным алгоритмам, когда решение исходной 
вычислительной задачи вытекает из решения единственного её меньшего 
экземпляра (подзадачи). Хотя предлагаемые задачи можно легко 
решить посредством итерации, они идеально подходят для введения 
основных понятий рекурсии, а также в качестве примеров применения 
рекурсивной методики и рекурсивных схем.