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

Эл Свейгарт

• Herausgeber: Питер
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Russisch

Seitenzahl: 383

Veröffentlichungsjahr: 2023

Beschreibung

Книга «Рекурсивная книга о рекурсии» содержит примеры кода на языке Python и JavaScript, которые иллюстрируют основы рекурсии и проясняют фундаментальные принципы всех рекурсивных алгоритмов. Из книги вы узнаете о том, когда стоит использовать рекурсивные функции (и, главное, когда этого не нужно делать), как реализовывать классические рекурсивные алгоритмы, часто обсуждаемые на собеседованиях, а также о том, как рекурсивные методы помогают решать задачи, связанные с обходом дерева, комбинаторикой и другими сложными темами.

Leseprobe

Эл Свейгарт

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

2023

Переводчик С. Черников

Эл Свейгарт

Рекурсивная книга о рекурсии. — СПб.: Питер, 2023.

ISBN 978-5-4461-2393-3

© ООО Издательство "Питер", 2023

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

Посвящается Джеку, который держал свое зеркало напротив моего.

Об авторе

Эл Свейгарт (Al Sweigart) — разработчик программного обеспечения, член организации Python Software Foundation и автор нескольких книг по программированию, в том числе «Python. Чистый код для продолжающих» и «Большая книга проектов Python» (издательство «Питер»). Его работы, распространяемые по лицензии Creative Commons, доступны по адресу https://www.inventwithpython.com.

О научном редакторе

Сара Кучински (Sarah Kuchinsky) имеет ученые степени в области менеджмента, инженерии и математики. Проводит корпоративные тренинги, а также занимается моделированием систем здравоохранения, разработкой игр и автоматизацией различных задач, используя для этого Python. Сара является соучредителем конференции North Bay Python, председателем комиссии на конференции PyCon US и ведущим организатором сообщества PyLadies Silicon Valley.

Благодарности

Хотя на обложке указано только мое имя, было бы несправедливо не отметить тех, кто помогал мне в написании книги. Я хотел бы поблагодарить моего издателя Билла Поллока (Bill Pollock), редактора Фрэнсис Со (Frances Saux), научного редактора Сару Кучински (Sarah Kuchinsky), выпускающего редактора Майлза Бонда (Miles Bond), менеджера по производству Рэйчел Монаган (Rachel Monaghan) и всех остальных сотрудников издательства No Starch Press за их неоценимую помощь.

Наконец, хочу выразить признательность своей семье, друзьям и читателям за ценные предложения и поддержку.

Введение

С помощью такой техники программирования, как рекурсия, можно создавать элегантные кодовые решения. Однако иногда разработчики не понимают, с какой стороны к ней подойти. Это не означает, что программисты могут (или должны) игнорировать рекурсию. Несмотря на свою кажущую­ся сложность, рекурсия является важной темой в информатике и позволяет глубже вникнуть в сам процесс программирования. По крайней мере, если вы разбираетесь в ней, вам будет проще пройти собеседование при приеме на работу.

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

Беспокоиться не о чем. Рекурсию гораздо сложнее объяснить, чем понять. Как будет сказано в главе 1, многие не разбираются в рекурсии не потому, что это сложная тема, а потому, что ее плохо объясняют. А поскольку рекурсивные функции обычно не используются в повседневной работе, многие программисты прекрасно обходятся без них.

Между прочим, рекурсия лежит в основе удивительного математического искусства создания фракталов — самоподобных фигур, примеры которых представлены на рис. В.1.

Рис. В.1. Примеры фракталов: треугольник Серпинского (слева), кривая Гильберта (в центре) и снежинка Коха (справа)

Тем не менее книга посвящена не только восхвалению рекурсии. В ней вы найдете и резкие критические замечания по поводу этой техники. Рекурсией нередко злоупотребляют в тех случаях, когда можно применить более простое решение. Рекурсивные алгоритмы бывают сложными для понимания и отличаются худшей производительностью, а также подвержены ошибкам переполнения стека. Некоторым программистам нравится использовать рекурсию не потому, что это подходящий метод решения конкретной проблемы, а просто потому, что они чувствуют себя умнее, когда пишут код, который другие разработчики понимают с трудом. Доктор технических наук Джон Виландер (John Wilander) однажды сказал: «Когда вы получаете докторскую степень в области computer science, вас отводят в специальную комнату и просят никогда не использовать рекурсию в реальной жизни, поскольку ее главная цель — усложнить жизнь старшекурсникам».

Итак, хотите ли вы получить преимущество на собеседованиях, научиться создавать красивые произведения математического искусства или просто пытаетесь окончательно разобраться в теме — эта книга покажет, насколько глубока кроличья нора (и кроличьи норы внутри нее). Рекурсия — это одна из тех тем информатики, по знанию которой можно профессионала отличить от новичка. Прочитав эту книгу, вы овладеете великим мастерством и узнаете главный секрет рекурсии: она вовсе не так сложна, как многие думают.

Для кого эта книга

Книга предназначена для тех, кого пугают или завораживают рекурсивные алгоритмы. Для большинства новичков понимание рекурсии сродни искусству владения черной магией. В примерах рекурсии далеко не всегда легко разобраться, из-за чего сам предмет вызывает недоумение и даже страх. Я надеюсь, что четкие объяснения и многочисленные примеры, приведенные в книге, помогут читателям наконец освоить эту тему.

Единственным минимальным условием для изучения книги является наличие базового опыта программирования на языке Python или JavaScript, на которых написан код в листингах. Код в книге сведен к самой сути: если вы умеете вызывать и создавать функции, а также различать глобальные и локальные переменные — вы знаете достаточно, чтобы разобраться в этих примерах.

Об этой книге

Книга состоит из 14 глав.

Часть I. О рекурсии

• Глава 1 «Что такое рекурсия?». Здесь объясняется само понятие рекурсии и приводятся доказательства, что в ней нет ничего мистического.

• Глава 2 «Рекурсия и итерация». Эта глава посвящена различиям (и сходствам) между рекурсивными и итеративными методами.

• Глава 3 «Классические рекурсивные алгоритмы». Здесь рассматриваются известные рекурсивные программы, такие как «Ханойская башня», алгоритм заливки и др.

• Глава 4 «Алгоритмы поиска с возвратом и обхода дерева». В главе обсуждается проблема, для решения которой рекурсия подходит особенно хорошо: обход древовидных структур данных, например, при прохождении лабиринтов и навигации по каталогу.

• Глава 5 «Алгоритмы типа “разделяй и властвуй”». Здесь обсуждается применение рекурсии для разделения больших задач на более мелкие подзадачи, а также разбирается несколько распространенных алгоритмов типа «разделяй и властвуй».

• Глава 6 «Перестановки и комбинации». Эта глава охватывает рекурсивные алгоритмы, связанные с упорядочением и сопоставлением, а также общие задачи программирования, для решения которых эти алгоритмы применяются.

• Глава 7 «Мемоизация и динамическое программирование». В ней объясняются некоторые простые приемы повышения эффективности кода при применении рекурсии в реальном мире.

• Глава 8 «Оптимизация хвостовых вызовов». Глава посвящена оптимизации хвостовых вызовов, которые часто используются для повышения производительности рекурсивных алгоритмов.

• Глава 9 «Рисование фракталов». Здесь мы познакомимся с захватывающим способом создания произведений искусства с помощью рекурсивных алгоритмов. Для генерации изображений в этой главе используется так называемая черепашья графика.

Часть II. Проекты

• Глава 10 «Инструмент для поиска файлов». В этой главе описывается программа, которая выполняет поиск файлов на компьютере в соответствии с заданными параметрами.

• Глава 11 «Генератор лабиринтов». В главе представлена программа, которая автоматически генерирует лабиринты любого размера, используя рекурсивный алгоритм поиска с возвратом.

• Глава 12 «Решатель “пятнашек”». Эта глава посвящена созданию программы для решения головоломки под названием «пятнашки».

• Глава 13 «Генератор фракталов». Здесь описана программа, позволяющая создавать фрактальные рисунки в соответствии с вашим собственным дизайном.

• Глава 14 «Создание эффекта Дросте». В главе мы напишем программу, которая создает рекурсивные изображения типа «картинка в картинке» с использованием модуля обработки изображений Pillow.

Практическая экспериментальная информатика

Чтение даже множества книг о рекурсии не научит вас реализовывать ее самостоятельно. В этой книге вы найдете немало примеров рекурсивного кода, написанного на языках программирования Python и JavaScript. Со всеми фрагментами программ вы можете поэкспериментировать. Если вы новичок в программировании, рекомендую прочитать мою книгу Automate the Boring Stuff with Python или книгу Эрика Мэтиза «Изучаем Python»2, чтобы познакомиться с базовыми концепциями программирования на языке Python.

Советую запускать примеры программ с применением отладчика, который позволяет выполнять код построчно, следя за состоянием программы и точно определяя места возникновения ошибок. В главе 11 книги Automate the Boring Stuff with Python объясняется, как использовать отладчик Python. Ее можно бесплатно прочитать в Интернете по адресу https://automatetheboringstuff.com/2e/chapter11.

Примеры кода на языках Python и JavaScript в книге представлены вместе. Код Python сохраняется в файле с расширением .py, а код JavaScript — .html (не .js). Возьмем, к примеру, файл hello.py:

print('Hello, world!')

И файл hello.html:

<script type="text/javascript">

document.write("Hello, world!<br />");

</script>

Эти два листинга описывают на двух разных языках программы, дающие одинаковые результаты.

Примечание

HTML-тег <br /> в файле hello.html обозначает разрыв или перенос строки, позволяющий разделить выводимый результат на несколько строк. Функция print() в Python автоматически добавляет символ разрыва строки в конец текста, в то время как функция document.write() в JavaScript этого не делает.

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

Файлы с расширением .html технически не являются исполняемыми, поскольку в них отсутствуют несколько необходимых HTML-тегов, таких как <html> и <body>, однако ваш браузер все равно сможет их отобразить. Данные теги специально опущены. При написании приведенных программ-примеров главной целью были простота и удобочитаемость, а не демонстрация лучших практик веб-разработки.

Установка Python

Браузер, позволяющий просматривать файлы .html, есть на каждом компьютере, однако если вы намерены запускать код из книги на этом языке, вам придется установить Python отдельно. Можно бесплатно скачать Python для Microsoft Windows, Apple macOS и Ubuntu Linux со страницы https://python.org/downloads. Обязательно загрузите версию Python 3 (например, 3.10), а не Python 2, поскольку в более новую версию было внесено несколько обратно несовместимых изменений, из-за чего на Python 2 представленные здесь примеры могут работать некорректно.

Запуск среды IDLE и примеров кода на языке Python

Для написания кода можно использовать редактор IDLE, который поставляется вместе с Python, или установить бесплатный, например Mu Editor (https://codewith.mu), PyCharm Community Edition (https://www.jetbrains.com/pycharm/download) или Microsoft Visual Studio Code (https://code.visualstudio.com/Download).

Чтобы запустить IDLE в операционной системе (ОС) Windows, откройте меню Пуск в нижнем левом углу экрана, введите IDLE в поле поиска и выберите IDLE (Python 3.10 64-bit).

В macOS откройте окно Finder и выберите Applications→Python3.10, а затем щелкните на значке IDLE.

В Ubuntu выберите Applications→Accessories→Terminal, а затем введите IDLE3. Вы также можете нажать кнопку Applications в верхней части экрана, выбрать раздел Programming, а затем нажать IDLE 3.

Среда IDLE предусматривает два вида окон. Окно интерактивной оболочки с подсказкой >>> используется для запуска инструкций на языке Python по одной за раз. Это бывает полезно, когда вы хотите поэкспериментировать с фрагментами кода. В окне редактора можно ввести программу целиком и сохранить ее в виде файла с расширением .py. Именно в нем вы будете писать исходный код приведенных в книге программ на языке Python. Чтобы открыть новое окно редактора файлов, выберите пункт New File в меню File. Для запуска программы необходимо нажать клавишу F5 или выбрать пункт меню Run→Run Module.

Запуск примеров кода JavaScript в браузере

Браузер вашего компьютера позволяет запускать программы на языке JavaScript и выводить на экран результат их выполнения, однако для написания самого кода вам понадобится текстовый редактор. Можно использовать как простые программы вроде Блокнота или TextMate, так и специальные, например IDLE или Sublime Text (https://www.sublimetext.com).

После ввода кода программы на языке JavaScript сохраните его в виде файла с расширением .html, а не .js. Откройте его в любом современном браузере, чтобы просмотреть результат.

От издательства

Ваши замечания, предложения, вопросы отправляйте по адресу [email protected] (издательство «Питер», компьютерная редакция).

Мы будем рады узнать ваше мнение!

На веб-сайте издательства www.piter.com вы найдете подробную информацию о наших книгах.

2Мэтиз Э.Изучаем Python: программирование игр, визуализация данных, веб-приложения. 3-е изд. — Питер, 2022.

Часть I. О рекурсии