Рекурсивная книга о рекурсии

Об авторе
О научном редакторе
Предисловие
Благодарности
Введение
Для кого эта книга
Об этой книге
Практическая экспериментальная информатика
Установка Python
Запуск среды IDLE и примеров кода на языке Python
Запуск примеров кода JavaScript в браузере
От издательства
ЧАСТЬ I. О РЕКУРСИИ
Глава 1. Что такое рекурсия
Определение рекурсии
Что такое функции
Что такое стеки
Что такое стек вызовов
Что такое рекурсивные функции и переполнение стека
Базовые и рекурсивные случаи
Код находящийся до и после рекурсивного вызова
Резюме
Дополнительные источники информации
Вопросы для закрепления
Глава 2. Рекурсия и итерация
Вычисление факториалов
Итеративный алгоритм вычисления факториала
Рекурсивный алгоритм вычисления факториала
Чем плох рекурсивный алгоритм вычисления факториала
Вычисление последовательности Фибоначчи
Итеративный алгоритм вычисления чисел Фибоначчи
Рекурсивный алгоритм вычисления чисел Фибоначчи
Чем плох рекурсивный алгоритм вычисления чисел Фибоначчи
Преобразование рекурсивного алгоритма в итеративный
Преобразование итеративного алгоритма в рекурсивный
Практический пример: вычисление экспоненты
Создание рекурсивной функции для вычисления экспоненты
Создание итеративной функции для вычисления экспоненты на основе рекурсивного подхода
Когда нужно использовать рекурсию
Создание собственных рекурсивных алгоритмов
Резюме
Дополнительные источники информации
Вопросы для закрепления
Практика
Глава 3. Классические рекурсивные алгоритмы
Суммирование чисел в массиве
Обращение строки
Определение палиндромов
Решение головоломки «Ханойская башня»
Использование заливки
Функция Аккермана
Резюме
Дополнительные источники информации
Вопросы для закрепления
Практика
Глава 4. Алгоритмы поиска с возвратом и обхода дерева
Использование метода обхода дерева
Древовидная структура данных в Python и JavaScript
Обход дерева
Прямой обход дерева
Обратный обход дерева
Центрированный обход дерева
Поиск восьмибуквенных имен в дереве
Определение максимальной глубины дерева
Прохождение лабиринтов
Резюме
Дополнительные источники информации
Вопросы для закрепления
Практика
Глава 5. Алгоритмы типа «разделяй и властвуй»
Двоичный поиск: поиск среди книг упорядоченных по алфавиту
Быстрая сортировка: разделение несортированной стопки книг на отсортированные стопки
Сортировка слиянием: объединение небольших стопок игральных карт в более крупные и отсортированные
Суммирование массива целых чисел
Алгоритм умножения Карацубы
Алгебра лежащая в основе алгоритма Карацубы
Резюме
Дополнительные источники информации
Вопросы для закрепления
Практика
Глава 6. Перестановки и сочетания
Терминология теории множеств
Поиск всех перестановок без повторения: схема рассадки гостей на свадьбе
Поиск перестановок с помощью вложенных циклов: далеко не идеальный подход
Перестановки с повторениями: взломщик паролей
Получение k-элементных сочетаний с помощью рекурсии
Получение всех комбинаций сбалансированных скобок
Булеан множества: поиск всех подмножеств множества
Резюме
Дополнительные источники информации
Вопросы для закрепления
Практика
Глава 7. Мемоизация и динамическое программирование
Мемоизация
Нисходящее динамическое программирование
Мемоизация в функциональном программировании
Мемоизация рекурсивного алгоритма вычисления последовательности Фибоначчи
Модуль Python functools
Что происходит при мемоизации нечистых функций
Резюме
Дополнительные источники информации
Вопросы для закрепления
Глава 8. Оптимизация хвостовых вызовов
Принцип работы хвостовой рекурсии и оптимизации хвостовых вызовов
Аккумуляторы в контексте хвостовой рекурсии
Ограничения хвостовой рекурсии
Примеры использования хвостовой рекурсии
Обращение строки
Нахождение подстроки
Вычисление экспоненты
Определение четности числа
Резюме
Дополнительные источники информации
Вопросы для закрепления
Глава 9. Рисование фракталов
Черепашья графика
Основные функции модуля turtle
Треугольник Серпинского
Ковер Серпинского
Фрактальные деревья
Какова длина береговой линии Великобритании? Кривая и снежинка Коха
Кривая Гильберта
Резюме
Дополнительные источники информации
Вопросы для закрепления
Практика
ЧАСТЬ II. ПРОЕКТЫ
Глава 10. Инструмент для поиска файлов
Полный код программы для поиска файлов
Функции сопоставления
Поиск файлов с четным значением размера в байтах
Поиск имен файлов содержащих все гласные
Рекурсивная функция walk()
Вызов функции walk()
Полезные функции стандартной библиотеки Python для работы с файлами
Поиск информации об имени файла
Поиск информации о временных метках файла
Изменение файлов
Резюме
Дополнительные источники информации
Глава 11. Генератор лабиринтов
Полный код программы для создания лабиринта
Задание констант генератора лабиринта
Создание структуры данных лабиринта
Вывод структуры данных лабиринта на экран
Использование рекурсивного алгоритма поиска с возвратом
Запуск цепочки рекурсивных вызовов
Резюме
Дополнительные источники информации
Глава 12. Решатель «пятнашек»
Рекурсивный алгоритм решения «пятнашек»
Полный код программы для решения «пятнашек»
Задание констант программы
Представление головоломки «пятнашки» в виде данных
Отображение игрового поля
Создание новой структуры данных игрового поля
Нахождение координат пустого квадрата
Совершение хода
Отмена хода
Настройка новой головоломки
Рекурсивное решение «пятнашек»
Функция solve()
Функция attemptMove()
Запуск программы
Резюме
Дополнительные источники информации
Глава 13. Генератор фракталов
Встроенные фракталы
Алгоритм генератора фракталов
Полный код программы для рисования фракталов
Задание констант и настройка конфигурации модуля turtle
Работа с функциями для рисования фигур
Функция drawFilledSquare()
Функция drawTriangleOutline()
Использование функции для рисования фракталов
Настройка функции
Использование словаря спецификаций
Применение спецификаций
Создание фракталов
Четыре угла
Спираль из квадратов
Двойная спираль из квадратов
Спираль из треугольников
Планер из игры Конвея «Жизнь»
Треугольник Серпинского
Волна
Рог
Снежинка
Создание отдельного квадрата или треугольника
Создание собственных фракталов
Резюме
Дополнительные источники информации
Глава 14. Создание эффекта Дросте
Установка библиотеки Python Pillow
Подготовка изображения
Полный код программы для создания эффекта Дросте
Настройка
Поиск пурпурной области
Изменение размера базового изображения
Рекурсивное размещение изображения внутри изображения
Резюме
Дополнительные источники информации