| Рекурсией называется ситуация, когда процедура прямо или косвенно, обращается к самой себе. То есть когда имеется цепочка вызовов P1 -> P2 -> ... -> Pn -> P1) |
В задачах 1 – 3 доказать невозможность построить (без рекурсии и проверки
ЗАКРАШЕНО) команды с определенными свойствами.
1. Дано: Робот находится в n-ой клетке бесконечного в одну сторону (огра-
ниченного слева и неограниченного справа) коридора высотой в одну клетку.
2. Дано: Робот находится в коридоре шириной в 1 клетку.
3. Дано: на бесконечном поле есть одна горизонтальная стена неизвестной
ширины, Робот стоит у нее снизу.
(обойдя стену).
4. Доказать, что любую программу, не содержащую рекурсии, можно заменить
эквивалентной программой с рекурсией, не содержащей циклов.
5. Решить задачу 1.
6. Решить задачу 2.
7. Решить задачу 3.
8. Дано: Робот находится в лабиринте; на поле расставлены стены, так что
число доступных для Робота клеток конечно. Вначале ни одной клетки не
закрашено.