Игры с Чипом

— Ну, а как же эта подпрограмма поможет Мюнхгаузену вылезти из лужи? — спросил Сережа с подозрением.

— А вот как: Мюнхгаузен первый раз потянет себя за волосы и нагреет своими движениями лужу на одну тысячную часть градуса. Потом, если лужа не высохла (а она, конечно, и не подумала высохнуть, хоть чуть-чуть и нагрелась), он снова потянет и нагреет лужу еще на одну тысячную часть градуса и так далее. Если у Мюнхгаузена скорость работы, как у рядового компьютера, то не пройдет и секунды, как вода в луже поднимается до 100°С и закипит. Ну, а из кипятка-то, я думаю, он и сам не заметит, как выпрыгнет!

— Здорово, — восхищенно протянул Сережа. — Слушай, а я как-то и не понимал, что компьютеры так быстро работают. В одну секунду: раз — буль-буль — и прыг! Готово дело!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ОТ РЕДАКЦИИ.

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

Конкурс поросят 

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

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

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

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

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

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

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

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

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

«У нас же число поросят будет меняться», — подумал Сережа, зачеркнул первую строчку и написал вот что:

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

— Ну, а что у тебя? — поинтересовался Сережа.

— А у меня конкурс для твоих поросят.

— Конкурс? Какой конкурс?

— Ну, скажем, по пению. Они песенки поют? Вот мы и проверим, кто лучше поет.

— Ага, — Сережа задумался, — это похоже на перестройку колонны, которую мы делали в прошлый раз. Сейчас я вспомню. Значит, сначала мы поросят будем поочередно отводить в сторону, потом начнем с конца: объявим последнего лауреатом, сравним его с предпоследним, и так до самого первого. Вспомнил, вспомнил! Знаешь, Чип, а это несправедливо: последнему дали побыть лауреатом, даже не проверяя, как он поет. А бедненький первый, даже если он по пению на втором месте, ни разу лауреатом не был.