Адитья Бхаргава – Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих (страница 7)

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!"