Рекурсия для исполнителя Робот

Рекурсия

Для исполнителя Робот в системе программирования КУМИР

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

Для решения поставленной задачи, Роботу необходимо:

• Поднимаясь вверх, дойти до края стены.
• Обойти стену.
• Двигаясь вниз, дойти до нужной клетки.

Какую алгоритмическую конструкцию можно использовать, чтобы провести Робота до верха стены?

?

?

?

Какие команды помогут перевести Робота на другую сторону стены?

Как узнать, на сколько клеток вниз надо перевести Робота?

Вверх

Вправо

Вниз

!

!

Цикл ПОКА:

нц Пока справа стена

• вверх

кц

N раз

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

Пример решения задачи, используя рекурсию.

Правила программирования рекурсии

• Рекурсивная программа обязательно содержит условие прекращения ее выполнения (условие возврата из рекурсии).
• Рекурсивная программа содержит вызов самой себя.

Практическая работа

Задача. На бесконечном поле имеется Робот. Где-то внизу находится горизонтальная стена длиной в одну клетку. Роботу необходимо закрасить клетку над стеной и вернуться в начальное положение.

Домашнее задание

Задача. Робот находится в горизонтальном коридоре. Длина коридора не известна. В нижней стене коридора имеется выход. Необходимо закрасить клетку над выходом и вернуться в начальное положение. Начальное и конечное положение Робота показано на рисунке.

Решение задачи из практической работы

Решение задачи из домашнего задания