Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - Адитья Бхаргава
def fact(x):
if x == 1:
return 1
else:
return x * fact(x-1)
В программу включается вызов fact(3). Проанализируем этот вызов строку за строкой и посмотрим, как изменяется стек вызовов. Стоит напомнить, что верхний блок в стеке сообщает, какой вызов fact является текущим.
Здесь важно, что каждый вызов создает собственную копию x. Обратиться к переменной x, принадлежащей другой функции, невозможно.
Стек играет важную роль в рекурсии. В начальном примере были представлены два решения поиска ключа. Вспомните, как выглядел первый:
В этом случае все коробки лежат в одном месте и вы всегда знаете, в каких коробках еще нужно искать ключ.
Но в рекурсивном решении никакой кучи не существует.
Если кучи нет, то как ваш алгоритм узнает, в каких коробках еще нужно искать? Пример:
К этому моменту стек вызовов выглядит примерно так:
«Куча коробок» хранится в стеке! Это стек незавершенных вызовов функции, каждый из которых ведет собственный незаконченный список коробок для поиска. Стек в данном случае особенно удобен, потому что вам не нужно отслеживать коробки самостоятельно — стек делает это за вас.
Стек удобен, но у него есть своя цена: сохранение всей промежуточной информации может привести к значительным затратам памяти. Каждый вызов функции занимает не много памяти, но если стек станет слишком высоким, это будет означать, что ваш компьютер сохраняет информацию по очень многим вызовам. На этой стадии есть два варианта:
• Переписать код с использованием цикла.
• Иногда можно воспользоваться так называемой хвостовой рекурсией. Это непростая тема, которая выходит за рамки книги. Вдобавок она поддерживается далеко не во всех языках.
Упражнения
3.2 Предположим, вы случайно написали рекурсивную функцию, которая бесконечно вызывает саму себя. Как вы уже видели, компьютер выделяет память в стеке при каждом вызове функции. А что произойдет со стеком при бесконечном выполнении рекурсии?
Шпаргалка
• Когда функция вызывает саму себя, это называется рекурсией.
• В каждой рекурсивной функции должно быть два случая: базовый и рекурсивный.
• Стек поддерживает две операции: занесение и извлечение элементов.
• Все вызовы функций сохраняются в стеке вызовов.
• Если стек вызовов станет очень большим, он займет слишком много памяти.
4. Быстрая сортировка
В этой главе
• Вы узнаете о стратегии «разделяй и властвуй». Случается так, что задача, над которой вы трудитесь, не решается ни одним из известных вам алгоритмов. Столкнувшись с такой задачей, хороший программист не сдается. У него существует целый арсенал приемов, которые он пытается использовать для получения решения. «Разделяй и властвуй» — первая общая стратегия, с которой вы познакомитесь.
• Далее рассматривается быстрая сортировка — элегантный алгоритм сортировки, часто применяемый на практике. Алгоритм быстрой сортировки использует стратегию «разделяй и властвуй».
Предыдущая глава была посвящена рекурсии. В этой главе вы воспользуетесь новыми знаниями для решения практических задач. Мы исследуем принцип «разделяй и властвуй», хорошо известный рекурсивный метод решения задач.
В этой главе мы постепенно добираемся до полноценных алгоритмов. В конце концов, алгоритм не особенно полезен, если он способен решать задачу только одного типа, — «разделяй и властвуй» помогает выработать новый подход к решению задач. Это всего лишь еще один инструмент в вашем арсенале. Столкнувшись с новой задачей, не впадайте в ступор. Вместо этого спросите себя: «А нельзя ли решить эту задачу, применив стратегию “разделяй и властвуй”?»
К концу этой главы вы освоите свой первый серьезный алгоритм «разделяй и властвуй»: быструю сортировку. Этот алгоритм сортировки работает намного быстрее сортировки выбором (о которой рассказывалось в главе 2). Он является хорошим примером элегантного кода.
«Разделяй и властвуй»
Возможно, вы не сразу поймете суть стратегии «разделяй и властвуй», поэтому мы рассмотрим три примера. Сначала я приведу наглядный пример. Потом мы разберем пример кода, который выглядит не так красиво, но, пожалуй, воспринимается проще. В завершение будет рассмотрена быстрая сортировка — алгоритм сортировки, использующий стратегию «разделяй и властвуй».
Представьте, что вы фермер, владеющий земельным участком.
Вы хотите равномерно разделить землю на одинаковые квадратные участки. Участки должны быть настолько большими, насколько это возможно, так что ни одно из следующих решений не подойдет.
Как определить наибольший размер квадрата для участка? Воспользуйтесь стратегией «разделяй и властвуй»! Алгоритмы на базе этой стратегии являются рекурсивными.
Решение задачи методом «разделяй и властвуй» состоит из двух шагов:
1. Сначала определяется базовый случай. Это должен быть простейший случай из всех возможных.
2. Задача делится или сокращается до тех пор, пока не будет сведена к базовому случаю.
А теперь воспользуемся стратегией «разделяй и властвуй» для поиска решения этой задачи. Каков самый большой размер квадрата, который может использоваться?
Для начала нужно определить базовый случай. Самая простая ситуация — если длина одной стороны кратна длине другой стороны.
Предположим, длина одной стороны составляет 25 м, а длина другой 50 м. В этом случае размер самого
