В первую очередь необходимо постараться описать процесс решения в виде . В них функция f может быть выражена в словесной форме. Затем разделить это описание на 2 части: собственно рекуррентные соотношения и соотношения, задющие граничные (начальные и конечные) условия процесса. Например, в задаче вычисления факториала соотношения (1) разбиваются на следующие 2 части: 1) Граничные условия
0!=1 - начальные условия;
k=N - условия окончания; 2) Рекуррентные соотношения
k!=(k-1)!*k;
k=1, 2, 3,... Рекурсивное определение в программе также делится на две части. Одна из них соответствует рекуррентным формулам и состоит из правил, в теле которых присутствует целевое утверждение с тем же предикатом, что и заголовок правила, т.е. из правил, рекурсивно вызывающих самих себя. Другая часть содержит утверждения, описывающие терминальную ситуацию, т.е. ситуацию, в которой рекурсивное обращение предиката к самому себе прекращается. В качестве терминальной ситуации выбирается одно из граничных условий. Обычно терминальная ситуация является первым утверждением в определении. В этом случае вот что происходит при выполнении (см. ):
• оценивается первое утверждение в рекурсивном определении;
• если первое утверждение не выполняется, осуществляется переход к следующему в определении утверждению, и оно оценивается. Обычно это правило, которое содержит условие, начинающее рекурсию;
• после прохождения первого уровня рекурсии выполнение возвращается к первому утверждению в определении и опять оценивается его истинность;
• если оценивание первого утверждения заканчивается неудачей, выполнение переходит ко второму в определении утверждению и входит во второй уровень рекурсии. Этот процесс продолжается до тех пор, пока первое утверждение (содержащее терминальную ситуацию) не выполнится и, таким образом, сделает определение успешным и остановит рекурсию.
В зависимости от того, как осуществляется переход от соотношений (1) к программе, различают два разных стиля рекурсивных определений: нисходящая рекурсия и восходящая рекурсия.
Опубликовал Kest
November 05 2009 12:58:26 ·
0 Комментариев ·
8105 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
