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