Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих

Рекурсия

Допустим, вы разбираете чулан своей бабушки и натыкаетесь на загадочный запертый чемодан.

Бабушка говорит, что ключ к чемодану, скорее всего, лежит в коробке.

В коробке лежат другие коробки, а в них лежат маленькие коробочки. Ключ находится где-то там. Какой алгоритм поиска ключа предложите вы? Подумайте над алгоритмом, прежде чем продолжить чтение.

Одно из решений может выглядеть так:

1. Сложить все коробки в кучу.

2. Взять коробку и открыть.

3. Если внутри лежит коробка, добавить ее в кучу для последующего поиска.

4. Если внутри лежит ключ, поиск закончен!

5. Повторить.

Есть и альтернативное решение.

1. Просмотреть содержимое коробки.

2. Если вы найдете коробку, вернуться к шагу 1.

3. Если вы найдете ключ, поиск закончен!

Какое решение кажется вам более простым? Первое решение можно построить на цикле while. Пока куча коробок не пуста, взять очередную коробку и проверить ее содержимое:

def look_for_key(main_box):

pile = main_box.make_a_pile_to_look_through()

while pile is not empty:

box = pile.grab_a_box()

for item in box:

if item.is_a_box():

pile.append(item)

elif item.is_a_key():

print "found the key!"

Второй способ основан на рекурсии. Рекурсией называется вызов функцией самой себя. Второе решение на псевдокоде может выглядеть так:

def look_for_key(b ox):

for item in box:

if item.is_a_box():

look_for_key(item) Рекурсия!

elif item.is_a_key():

print "found the key!"

Оба решения делают одно и то же, но второе решение кажется мне более понятным. Рекурсия применяется тогда, когда решение становится более понятным. Применение рекурсии не ускоряет работу программы: более того, решение с циклами иногда работает быстрее. Мне нравится одна цитата Ли Колдуэлла с сайта Stack Overlow: «Циклы могут ускорить работу программы. Рекурсия может ускорить работу программиста. Выбирайте, что важнее в вашей ситуации!»[2]

Рекурсия используется во многих нужных алгоритмах, поэтому важно понимать эту концепцию.

Базовый случай и рекурсивный случай

Так как рекурсивная функция вызывает сама себя, программисту легко ошибиться и написать функцию так, что возникнет бесконечный цикл. Предположим, вы хотите написать функцию для вывода обратного отсчета:

> 3...2...1

Ее можно записать в рекурсивном виде:

def countdown(i):

print i

countdow n(i-1)

Введите этот код и выполните его. И тут возникает проблема: эта функция выполняется бесконечно!

Бесконечный цикл

> 3...2...1...0...-1...-2...

Чтобы прервать выполнение сценария, нажмите Ctrl+C.

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

Добавим базовый случай в функцию countdown:

def countdown(i):

print i

if i <= 0: Базовый случай

return

else: Рекурсивный случай

countdow n(i-1)

Теперь функция работает так, как было задумано. Это выглядит примерно так:

Стек

В этом разделе рассматривается стек вызовов. Концепция стека вызовов играет важную роль в программировании вообще; кроме того, ее важно понимать при использовании рекурсии.

Предположим, вы устраиваете вечеринку с барбекю. Вы составляете список задач и записываете дела на листках.

Помните, когда мы рассматривали массивы и списки, у вас тоже был список задач? Задачи, то есть элементы списка, можно было добавлять и удалять в произвольных позициях списка. Стопка листков работает куда проще. Новые (вставленные) элементы добавляются в начало списка, то есть на верх стопки. Читается только верхний элемент, и он исключается из списка. Таким образом, список задач поддерживает всего два действия: занесение (вставка) и извлечение (выведение из списка и чтение.)

Посмотрим, как работает список задач:

Такая структура данных называется стеком. Стек — простая структура данных. А теперь самое неожиданное: все это время вы пользовались стеком, не подозревая об этом!

Стек вызовов

Во внутренней работе вашего компьютера используется стек, называемый стеком вызовов. Давайте посмотрим, как он работает. Предположим, имеется простая функция:

def greet(name):

print "hello, " + name + "!"

greet2(name)

print "getting ready to say bye..."

bye()

Эта функция приветствует вас, после чего вызывает две другие функции. Вот эти две функции:

def greet2(name):

print "how are you, " + name + "?"

def bye():

print "ok bye!"

Разберемся, что происходит при вызове функции.

примечание

В языке Python print тоже является функцией. Чтобы не усложнять пример, мы сделаем вид, что этой функции нет. Просто подыграйте нам.

Предположим, в программе используется вызов greet("maggie"). Сначала ваш компьютер выделяет блок памяти для этого вызова функции.

Затем эта память используется. Переменной name присваивается значение "maggie"; оно должно быть сохранено в памяти.

Каждый раз, когда вы вызываете функцию, компьютер сохраняет в памяти значения всех переменных для этого вызова. Далее выводится приветствие hello, maggie!, после чего следует второй вызов greet2("maggie"). И снова компьютер выделяет блок памяти для вызова функции.

Ваш компьютер объединяет эти блоки в стек. Второй блок создается над первым. Вы выводите сообщение how are you, maggie?, после чего возвращаете управление из вызова функции. Когда это происходит, блок на вершине стека извлекается из него.

Теперь верхний блок в стеке относится к функции greet; это означает, что вы вернулись к функции greet. При вызове функции greet2 функция greet еще не была завершена. Здесь-то и скрывается истинный смысл этого раздела: когда вы вызываете функцию из другой функции, вызывающая функция приостанавливается в частично завершенном состоянии. Все значения переменных этой функции остаются в памяти. А когда выполнение функции greet2 будет завершено, вы вернетесь к функции greet и продолжите ее выполнение с того места, где оно прервалось. Сначала выводится сообщение getting ready to say bye…, после чего вызывается функция bye.

Блок для этой функции добавляется на вершину стека. Далее выводится сообщение ok bye! с выходом из вызова функции.

Управление снова возвращается функции greet. Делать больше нечего, так что управление возвращается и из функции greet. Этот стек, в котором сохранялись переменные разных функций, называется стеком вызовов.

Упражнения

3.1 Предположим, имеется стек вызовов следующего вида:

Что можно сказать о текущем состоянии программы на основании этого стека вызовов?

А теперь посмотрим, как работает стек вызовов с рекурсивными функциями.

Стек вызовов с рекурсией

Рекурсивные функции тоже используют стек вызовов! Посмотрим, как это делается, на примере функции вычисления факториала. Вызов factorial(5) записывается в виде 5! и определяется следующим образом: 5! = 5*4*3*2*1. По тому же принципу factorial(3) соответствует 3*2*1. Рекурсивная функция для вычисления факториала числа выглядит так:

def fact(x):

if x == 1:

return 1

else:

return x * fact(x-1)

В программу включается вызов fact(3). Проанализируем этот вызов строку за строкой и посмотрим, как изменяется стек вызовов. Стоит напомнить, что верхний блок в стеке сообщает, какой вызов fact является текущим.

Здесь важно, что каждый вызов создает собственную копию x. Обратиться к переменной x, принадлежащей другой функции, невозможно.

Стек играет важную роль в рекурсии. В начальном примере были представлены два решения поиска ключа. Вспомните, как выглядел первый:

В этом случае все коробки лежат в одном месте и вы всегда знаете, в каких коробках еще нужно искать ключ.

Но в рекурсивном решении никакой кучи не существует.

Если кучи нет, то как ваш алгоритм узнает, в каких коробках еще нужно искать? Пример:

К этому моменту стек вызовов выглядит примерно так:

«Куча коробок» хранится в стеке! Это стек незавершенных вызовов функции, каждый из которых ведет собственный незаконченный список коробок для поиска. Стек в данном случае особенно удобен, потому что вам не нужно отслеживать коробки самостоятельно — стек делает это за вас.

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

• Переписать код с использованием цикла.

• Иногда можно воспользоваться так называемой хвостовой рекурсией. Это непростая тема, которая выходит за рамки книги. Вдобавок она поддерживается далеко не во всех языках.

Упражнения

3.2 Предположим, вы случайно написали рекурсивную функцию, которая бесконечно вызывает саму себя. Как вы уже видели, компьютер выделяет память в стеке при каждом вызове функции. А что произойдет со стеком при бесконечном выполнении рекурсии?

Шпаргалка

• Когда функция вызывает саму себя, это называется рекурсией.

• В каждой рекурсивной функции должно быть два случая: базовый и рекурсивный.

• Стек поддерживает две операции: занесение и извлечение элементов.

• Все вызовы функций сохраняются в стеке вызовов.

• Если стек вызовов станет очень большим, он займет слишком много памяти.