Грокаем алгоритмы

В этой главе

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

• Вы научитесь разбивать задачи на базовый и рекурсивный случай. В стратегии «разделяй и властвуй» (глава 4) эта простая концепция используется для решения более сложных задач.

Эта глава мне самому очень нравится, потому что в ней рассматривается рекурсия — элегантный метод решения задач. Рекурсия относится к числу моих любимых тем, но вызывает у людей противоречивые чувства. Они либо обожают ее, либо ненавидят, либо ненавидят, пока не полюбят через пару-тройку лет. Лично я отношусь к третьему лагерю. Чтобы вам было проще освоить эту тему, я дам несколько советов:

• Глава содержит множество примеров кода. Самостоятельно выполните этот код и посмотрите, как он работает.

• Мы будем рассматривать рекурсивные функции. Хотя бы один раз возьмите бумагу и карандаш и разберите, как работает рекурсивная функция: «Так, я передаю функции factorial значение 5, потом возвращаю управление и передаю значение 4 функции factorial, которая…» и т.д. Такой разбор поможет вам понять, как работает рекурсивная функция.

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

Рекурсия

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

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

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

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

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]

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

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