Главная /
Инструменты, алгоритмы и структуры данных /
Необходимыми условиями корректно определенного рекурсивного метода является существование у метода ветви без рекурсии и разные контексты у каждого рекурсивного вызова. Рассмотрим метод с циклом: cicle do from Init until Exit loop Body end end Заменим его
Необходимыми условиями корректно определенного рекурсивного метода является существование у метода ветви без рекурсии и разные контексты у каждого рекурсивного вызова. Рассмотрим метод с циклом:
cicle
do
from Init until Exit loop Body end
end
Заменим его методом
recursive
do Init; loop_eqviv end
с вызовом рекурсивного метода:
loop_eqviv
do
if not Exit then
Body; loop_eqviv
end
end
Какие утверждения справедливы относительно корректности такой замены?
вопрос
Правильный ответ:
такая замена некорректна, поскольку не выполняется необходимое условие существования у рекурсивного метода не рекурсивной ветви
у метода
loop_eqviv
существует не рекурсивная ветвь. Когда выполняется условие выхода, то можно полагать, что выполняется ветвь без рекурсии (пустая в данном случае), завершающая выполнение метода
такая замена некорректна, поскольку не выполняется необходимое условие изменения контекста при каждом вызове рекурсивного метода
контекст у рекурсивного метода меняется автоматически
контекст каждого вызова будет меняться только при выполнении условий, предполагаемых по умолчанию для этой схемы замены цикла рекурсией:
Init
, Exit
, Body
определены над полями класса - глобальной для метода информацией;Init
задает начальный контекст вызова;Body
изменяет контекст и уменьшает значение варианта метода, гарантируя завершаемость.
завершаемость метода
cicle
гарантирует завершаемость метода loop_eqviv
Сложность вопроса
61
Сложность курса: Инструменты, алгоритмы и структуры данных
89
Оценить вопрос
Комментарии:
Аноним
Это было сложно
17 май 2018
Аноним
Это очень элементарный вопрос intuit.
03 ноя 2016
Другие ответы на вопросы из темы программирование интуит.
- # Какие типы данных можно использовать в языке Eiffel для сущностей, представляющих тексты?
- # Какие утверждения справедливы для грамматики и языка, порожденного грамматикой?
- # Укажите, какое утверждение является корректным для универсально порожденного типа:
- # Для каких понятий нельзя дать корректного рекурсивного определения?
- # Рассмотрим игру, в которой применяется минимаксная стратегия. Напомним, это означает, что в игре участвуют два противника, поочередно выполняющие ходы. Существует оценочная функция, которая выдает оценку (число) для каждой позиции после очередного хода. Положительное значение этой оценки рассматривается как выигрыш для одного игрока и как проигрыш для другого (игра с нулевой суммой). Зададим дерево конкретной игры, в узлах которого записаны оценки позиций. Дерево зададим скобочной записью: ( ((5, 3) (6, -1, 8)) ((10, 6, 2) (-2, -4, -7)) ) Здесь цифры, заключенные в скобки - это оценки в листьях, принадлежащих одному родителю. Игрок на нижнем уровне выбирает минимальную оценку. При вычислении цены игры применяется альфа-бета стратегия отсечения вариантов. Сколько вариантов (в данном случае листьев дерева) будет отсечено при применении этой стратегии?