— Постой, постой, дай я соображу, как она будет работать. Если в колонне всего один человек, то его нечего перестраивать. Правильно, тут и написано «возврат». А куда возврат? Ладно, пока это неважно, а там посмотрим.
Теперь пусть в колонне два человека. Идем по программе. Первая строчка не для нас, поскольку в колонне два человека. Смотрим следующую строчку. Первый делает шаг вбок — это мы выполнили вторую строчку. Согласно третьей строчке, мы должны перестроить остаток колонны, то есть последнего, второго. Это мы уже умеем — он остается на месте, и происходит какой-то возврат. Чип, а что это за возврат?
— Ну, сам подумай, что ты должен сейчас делать? Вспомни, что ты делал до того, как прочел таинственное слово «возврат», и... возвращайся к этому делу.
— Как что делал? Я перестраивал колонну из двух человек. У меня первый сбоку стоит и ждет.
— Вот и возвращайся к тому, что ты дальше должен с ним делать. В программе на четвертой строчке сказано: «Первый идет назад». Это как раз к нему и относится.
— Так, значит, первый идет назад и оказывается позади второго. Опять возврат! Колонна из двух человек перестроена. Все-таки я с этим возвратом чего-то не понял. Интересно, как он будет работать с тремя людьми? Первая строчка нашей программы для колонны из трех человек не годится. На второй строчке первый человек делает шаг вбок, а на третьей... Ага, на третьей строчке мы перестраиваем колонну из двух, это мы уже умеем. Перестроили. На четвертой строчке ставим первого сзади них, то есть на самое последнее место, как и надо.
А зачем же нужен возврат? Ну, теперь ясно — от перестройки одного человека мы вернулись к перестройке двоих, от перестройки двоих к троим и так далее. Значит, возвращаемся на один шаг назад, к самому последнему из брошенных дел. Чип, а знаешь, что мне еще непонятно: как это программа будет работать, если взять много людей, ну, скажем, сто? На третьей строчке написано: «Перестрой остаток колонны», а там 99 человек. Мы же еще не знаем, как их перестраивать?
— А и не надо заранее знать! Начинай применять к ним ту же самую программу, и все получится. Они по очереди будут делать шаг вбок, пока не дойдет черед до последнего, а потом предпоследний встанет позади последнего, предпоследний за ним и так далее, пока первый не встанет сзади всех. Программа будет применяться сто раз, и сто раз будет происходить возврат к предыдущей перестройке.
— Как сложно, правда, Чип? Три строчки написано, а сколько беготни.
— А ты попробуй к следующему разу сам сочинить рекурсивную программу. Договорились?
ОТ РЕДАКЦИИ.
Ребята, может быть, и вы попробуете сочинить рекурсивную программу для сказки или считалки? А Чип проверит, что у вас получится. Ждем ваших писем.
Конкурс поросят
К следующему разу Сережа ничего путного не смог придумать. В голову лезла какая-то чепуха про двенадцать поросят.
«12 поросят на палубе сидят.
Они песенки поют, им уроки задают.
Один из них устал и с палубы удрал,
И вот результат — 11 поросят.
11 поросят на палубе сидят...».
И так далее...
В конце концов из этого тоже можно сделать программу. Сережа взял листочек бумаги и написал:
Программа. «ПЕСЕНКА ПРО N ПОРОСЯТ».
Но тут вспомнил, как Чип объяснял ему: «Если внутри программы что-то меняется, то это уже не программа, а подпрограмма».
«У нас же число поросят будет меняться», — подумал Сережа, зачеркнул первую строчку и написал вот что:
Подпрограмма.
«ПЕСЕНКА ПРО N ПОРОСЯТ»
Если N=0, то конец.
N ПОРОСЯТ НА ПАЛУБЕ СИДЯТ.
ОНИ ПЕСЕНКИ ПОЮТ, ИМ УРОКИ ЗАДАЮТ
ОДИН ИЗ НИХ УСТАЛ И С ПАЛУБЫ УДРАЛ.
И ВОТ РЕЗУЛЬТАТ: N-1 ПОРОСЯТ
«ПЕСЕНКА ПРО N-1 ПОРОСЯТ»
Конец подпрограммы.
— Ну что, не так уж плохо, — сказал Чип, прочтя про поросят. — Не так плохо для начала: ты догадался, что нужно написать не программу, а подпрограмму и остановиться, когда все поросята удерут с палубы.
— Ну, а что у тебя? — поинтересовался Сережа.
— А у меня конкурс для твоих поросят.
— Конкурс? Какой конкурс?
— Ну, скажем, по пению. Они песенки поют? Вот мы и проверим, кто лучше поет.
Подпрограмма «Лауреат... (среди поросят)».
Если поросенок один, то объявить его лауреатом.
Если их больше, то отвести в сторону первого поросенка и найти лауреата среди остальных поросят.
Сравнить пение этого лауреата и первого поросенка.