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

ЬЗЯТЬ КОРОБКУ м ОТКРЫТЬ,


если внутри
ЛЕЖИТ К0Р06-'
_кк .ДОБАВИТЬ
ЕЕ 6 КУЧУ
wwmST
к КУЧЕ


-ЁшГвнутрТ
ЛЕЖИТ ККЮЧ,
ПОИСК
ЗАКОНЧЕН!

ОКА 6 КУЧЕ
ОСТАЮТСЯ КОРОБКИ

1. 
   Сложить все коробки в кучу.
   
2. 
   Взять коробку и открыть.
   
3. 
   Если внутри лежит коробка, добавить ее в кучу для последующего по­иска.
   
4. 
   Если внутри лежит ключ, поиск закончен!
   
5. 
   Повторить.
   

Е
проьерить КИШ»* ПРШ.МЕ-Т 6 КОРОБКЕ




L


ЕСЛИ 6Ы HMULETE КМОЧ, ПОИСК
ЗКК0НЧЕН\


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

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. . л
Ее можно записать в рекурсивном виде:
def countdown(i): print i
countdow n(i-l)
Введите этот код и выполните его. И тут возникает проблема: эта функция выполняется бесконечно!
Б
[вызвкть COUNTDQUt^

http://stackoverlow.com / а/72694/139117
есконечный
цикл
Чтобы прервать выполнение сценария, нажмите Ctrl+C.
Когда вы пишете рекурсивную функцию, в ней необходимо указать, в ка­кой момент следует прервать рекурсию. Вот почему каждая рекурсивная функция состоит из двух частей: базового случая и рекурсивного случая. В рекурсивном случае функция вызывает сама себя. В базовом случае функция себя не вызывает... чтобы предотвратить зацикливание.
Добавим базовый случай в функцию countdown: