В этой главе
• Вы узнаете, что такое рекурсия — метод программирования, используемый во многих алгоритмах. Это важная концепция для понимания дальнейших глав книги.
• Вы научитесь разбивать задачи на базовый и рекурсивный случай. В стратегии «разделяй и властвуй» (глава 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]
Рекурсия используется во многих нужных алгоритмах, поэтому важно понимать эту концепцию.
