Игры с Чипом

Такие подпрограммы называются рекурсивными, их всегда трудно понять. Кажется, что они не смогут работать, как Мюнхгаузен не сможет вытянуть себя из лужи. Для того, чтобы рекурсивная подпрограмма работала, надо, чтобы при каждом вызове что-то изменялось так, чтобы работа могла кончиться.

— А можешь еще рекурсивную программу написать? Мне очень понравилось.

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

Программа «ПЕРЕСТРОЙ» (колонну).

Если в колонне один человек, то возврат.

ПЕРВЫЙ ДЕЛАЕТ ШАГ ВБОК.

«ПЕРЕСТРОЙ» (остаток колонны).

ПЕРВЫЙ ИДЕТ НАЗАД.

Возврат.

— Постой, постой, дай я соображу, как она будет работать. Если в колонне всего один человек, то его нечего перестраивать. Правильно, тут и написано «возврат». А куда возврат? Ладно, пока это неважно, а там посмотрим.

Теперь пусть в колонне два человека. Идем по программе. Первая строчка не для нас, поскольку в колонне два человека. Смотрим следующую строчку. Первый делает шаг вбок — это мы выполнили вторую строчку. Согласно третьей строчке, мы должны перестроить остаток колонны, то есть последнего, второго. Это мы уже умеем — он остается на месте, и происходит какой-то возврат. Чип, а что это за возврат?

— Ну, сам подумай, что ты должен сейчас делать? Вспомни, что ты делал до того, как прочел таинственное слово «возврат», и... возвращайсяк этому делу.

— Как что делал? Я перестраивал колонну из двух человек. У меня первый сбоку стоит и ждет.

— Вот и возвращайся к тому, что ты дальше должен с ним делать. В программе на четвертой строчке сказано: «Первый идет назад». Это как раз к нему и относится.

— Так, значит, первый идет назад и оказывается позади второго. Опять возврат! Колонна из двух человек перестроена. Все-таки я с этим возвратом чего-то не понял. Интересно, как он будет работать с тремя людьми? Первая строчка нашей программы для колонны из трех человек не годится. На второй строчке первый человек делает шаг вбок, а на третьей... Ага, на третьей строчке мы перестраиваем колонну из двух, это мы уже умеем. Перестроили. На четвертой строчке ставим первого сзади них, то есть на самое последнее место, как и надо.

А зачем же нужен возврат? Ну, теперь ясно — от перестройки одного человека мы вернулись к перестройке двоих, от перестройки двоих к троим и так далее. Значит, возвращаемся на один шаг назад, к самому последнему из брошенных дел. Чип, а знаешь, что мне еще непонятно: как это программа будет работать, если взять много людей, ну, скажем, сто? На третьей строчке написано: «Перестрой остаток колонны», а там 99 человек. Мы же еще не знаем, как их перестраивать?

— А и не надо заранее знать! Начинай применять к ним ту же самую программу, и все получится. Они по очереди будут делать шаг вбок, пока не дойдет черед до последнего, а потом предпоследний встанет позади последнего, предпоследний за ним и так далее, пока первый не встанет сзади всех. Программа будет применяться сто раз, и сто раз будет происходить возврат к предыдущей перестройке.

— Как сложно, правда, Чип? Три строчки написано, а сколько беготни.

— А ты попробуй к следующему разу сам сочинить рекурсивную программу. Договорились?

ОТ РЕДАКЦИИ.

Ребята, может быть, и вы попробуете сочинить рекурсивную программу для сказки или считалки? А Чип проверит, что у вас получится. Ждем ваших писем.

К следующему разу Сережа ничего путного не смог придумать. В голову лезла какая-то чепуха про двенадцать поросят.

«12 поросят на палубе сидят.

Они песенки поют, им уроки задают.

Один из них устал и с палубы удрал,

И вот результат — 11 поросят.

11 поросят на палубе сидят...».

И так далее...

В конце концов из этого тоже можно сделать программу. Сережа взял листочек бумаги и написал:

Программа. «ПЕСЕНКА ПРО N ПОРОСЯТ».

Но тут вспомнил, как Чип объяснял ему: «Если внутри программы что-то меняется, то это уже не программа, а подпрограмма».