Кенгуренок имеет в своем распоряжении небольшое количество команд и алгоритмических конструкций, но все же он обладает еще одной возможностью, написание программы с рекурсивным вызовом вспомогательного алгоритма.

Рекурсия – это способ программирования, при котором программа вызывает саму себя. Рекурсия бывает конечной и бесконечной.

Рассмотрим следующую задачу, решить которую без использования рекурсии не возможно.

Кенгуренок находится где-то посередине листа и смотрит на юг. Дойти до края листа с рисованием линии и вернуться в исходную позицию.

Если бы в задаче не было условия возврата в исходную позицию, то написание алгоритма не составило бы труда. Рассмотрим этот случай:

пока впереди не край, повторять

шаг

конец цикла

В результате Кенгуренок нарисует линию и остановится на краю листа.

Рассмотрим теперь вариант программы решающий нашу задачу.

сделай Линия

процедура Линия

шаг

если впереди не край, то

сделай Линия

иначе

сделай Разворот

конец ветвления

прыжок

конец процедуры

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

Программа начинается с вызова вспомогательного алгоритма Линия, на этом основной алгоритм закончен.

Посмотрим, что делает вспомогательный алгоритм Линия.

Первая команда Кенгуренку шаг, что он выполнит без труда. Далее идет условие, в котором проверяется, не дошли ли мы до края листа. Допустим впереди не край, и можно идти дальше, посмотрим какие команды внутри условия. Но там находится единственная команда, сделай Линия! Что же получается, вспомогательный алгоритм Линия вызывает саму себя. Что делать? Очевидно, нам придется выполнить этот алгоритм, ведь никто нам этого не запрещает. Хорошо. Процедура Линия состоит из команды шаг, потом условие и снова вызов алгоритма Линия. Все повторяется сначала.

Что же произойдет в итоге? Кенгуренок будет все время смещаться вниз на один шаг, пока… пока не остановится у края поля, это случится когда кенгуренок на вопрос впереди не край ответит уверенно нет.

Хорошо, мы выполнили несколько раз команду шаг и вызвали несколько раз алгоритм Линия, но когда же мы вернемся? Вот в этот самый момент, но сначала выполним блок иначе. Перед тем как идти обратно, мы должны развернуться, что и делаем вызвав алгоритм Разворот. Итак, мы развернулись, выходим из ветвления и выполняем первый прыжок назад, на этом работа алгоритма линия закончена и мы возвращаемся обратно в алгоритм Линия в точку ее вызова, т.е. внутри условного оператора. Очевидно, блок иначе мы не выполняем т.к. условие было верным, остается еще раз выполнить прыжок и снова выйти из алгоритма в точку ее вызова. Так будет продолжаться до тех пор, пока мы не выйдем из рекурсии, т.е. до последнего вызова алгоритма Линия.

В результате работы алгоритма Линия, не только нарисуем линию, но и сможем вернуть в исходную позицию.

№ 33. Кенгуренок находится где-то посередине листа и смотрит на юг. Дойти до края листа нарисовать квадрат и вернуться в исходную позицию.

№ 34. Кенгуренок находится где-то посередине листа и смотрит на восток. Составьте алгоритм изображения лесенки на рисунке с использованием рекурсии. Кенгуренок должен рисовать ступеньки, пока не достигнет края листа, и вернуться в исходную позицию.