Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
Имитационное мо... 60790
Реклама
Сейчас на сайте
Гостей: 3
На сайте нет зарегистрированных пользователей

Пользователей: 13,122
новичок: BenderSergey1969
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Диплом - база данных поставщиков на Delphi (MS Sql Server)+ Пояснительна...
Движение шарика в эллиптическои параболоиде на Delphi [OpenGL] + Блок схемы
Моделирование ЭВМ на GPSS (три класса заданий) + Пояснительная записка

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
ВОСХОДЯЩАЯ РЕКУРСИЯ
При восходящей рекурсии моделирование процесса начинается сначала, с момента k=0. Номер шага постоянно возрастает: k=k+1. В качестве терминальной ситуации выбирается момент достижения условий окончания процесса k=N, начальные условия задаются в качестве значений аргументов целевого утверждения-запроса. В восходящей рекурсии параметры, характеризующие состояние процесса, вычисляются на каждой стадии рекурсии в процессе выполнения прямого хода. Ниже приведено определение процесса вычисления факториала F=3!, написанное с использованием техники восходящей рекурсии.
/* неправильное определение восходящей рекурсии */
'факт1'(3,P):- write(P), nl. /* терминальная ситуация */
/* описывает условия */
'факт1'(K,P):-K1 is K+1, P1 is P*K1,
/* P1 – текущее состояние процесса*/
'факт1'(K1,P1).
?-'факт1'(0,1). /* начальные состояние процесса */



В этом определении K и K1=K+1 - номера соответственно текущего и следующего шагов; P - промежуточное значение факториала, вычисленное к моменту K; следующее значение P1 определяется как P1=P*K1.
ВОСХОДЯЩАЯ РЕКУРСИЯ
Рис.2
Как видим, огромным недостатком определения 'факт1' является зависимость описания терминальной ситуации от значений исходных данных. Например, для F=4! первое утверждение должно иметь вид 'факт1'(4,P). Проанализируем вычисление восходящей рекурсии с помощью И-ИЛИ-дерева, представленного на рис.2.
Из анализа схемы следует, что в процессе выполнения прямого хода результат строится постепенно (P хранит промежуточные значения) и окончательное значение приобретается в момент достижения терминальной ситуации. При обратном ходе результат теряется, так как восстанавливаются конкретизированные значения аргументов цели 'факт1'. Таким образом, в вершине доказательства результат отсутствует. Чтобы его не потерять, необходимо в момент достижения терминальной ситуации передать его значение переменной-результату, которую дополнительно необходимо включить в список аргументов. Избавиться от конкретики терминальной ситуации также можно введением еще одной переменной N в список аргументов, представляющей собой номер последнего шага процесса. С ее значением постоянно сравнивается номер текущего шага K, и при выполнении условия окончания процесса K=N достигается терминальная ситуация.
Таким образом, список аргументов предиката, проектируемого по схеме восходящей рекурсии, должен содержать две группы параметров: одна группа - это исходные данные и результат, вторая - промежуточные значения переменных процесса. Например:
'факт1'(N,F,K,P),



где N - исходное данное, F - результат, K - текущий номер, P - текущее состояние.
Чтобы сохранить число аргументов таким же, как и при нисходящей рекурсии, следует определить два разных предиката, один из которых (основной) обращается к предикату с дополнительно введенными аргументами и построенному по схеме восходящей рекурсии. Например:
/* правильное определение восходящей рекурсии */
'факт'(N,F):- /* основной предикат */
'факт1'(N,F,0,1). /* рекурсивно описанный предикат */
'факт1'(N,F,N,F):-!. /* терминальная ситуация */
'факт1'(N,F,K,P):- K1 is K+1, /* восходящая рекурсия */
P1 is P*K1, 'факт1'(N,F,K1,P1).
?-'факт'(3,F). /* запрос */



Достоинством восходящей рекурсии (рекурсивный вызов в конце тела правила) является экономия памяти. Необходимо хранить только параметры рекурсивно определенных целей 'факт1', а не все тело правила. Следствием этого является также эффективность восходящей рекурсии по быстродействию. Рекомендуется во всех случаях, когда это возможно, переходить от нисходящей рекурсии к восходящей. Ниже приведен пример восходящей рекурсии для многошагового итерационного процесса на примере получения чисел фибоначчи.
/* восходящая рекурсия */
'фибоначчи' (N,F):- 'фибоначчи' (N,F,1,1,0). /* начальные услови я */

'фибоначчи' (N,F,N,F,_):-!. /* условия окончания */
/* терминальная ситуация */
'фибоначчи' (N,F,K,F1,F0):- K1 is K+1,
F2 is F0+F1, /* F(K)=F(K-2)+F(K-1) */
'фибоначчи' (N,F,K1,F2,F1).
?- 'фибоначчи' (10,Z). /* запрос */



Здесь N - порядковый номер элемента последовательности чисел фибоначчи; F - число фибоначчи.
Опубликовал Kest Ноябрь 05 2009 16:06:59 · 1 Комментариев · 11526 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
юрий Август 18 2014 16:23:55
неудобопонятна трассировка рекурсии факториала где начало ,где конец ,голову сломаешь
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Delphi 7 Enterpri...
Архив программ
PCXReader. Програ...
StartMark
BSButton
База данных: Книж...
TelBook
WinAmp
Программирование ...
Цветной Grid
Разработка Web-пр...
Медиа комбайн
Игра Car [Исходни...
Delphi на примерах
DragMe [Исходник ...
JanComp
Философия C++. Пр...
Java 2 - Эффектив...
DelphiXIsoDemo1
FileFind

Топ загрузок
Приложение Клие... 100532
Delphi 7 Enterp... 92141
Converter AMR<-... 20103
GPSS World Stud... 15545
Borland C++Buil... 13132
Borland Delphi ... 9197
Turbo Pascal fo... 7115
Калькулятор [Ис... 5221
Visual Studio 2... 5037
FreeSMS v1.3.1 3561
Случайные статьи
Структуры, объедин...
Диалоговое окно Re...
Переписать текст и...
Обучение английско...
Topology Change и ...
Поисковый механизм...
Первый служит для ...
Бесшумная работа
4.1. Порождение ...
Шесть тепловых стр...
Спецификация MPEG-4
по всему лесу
Лексикографическая...
Бесплатный игровой...
Функции
Настройте коммутир...
Исследование перет...
Протокол РоЕР внут...
службы поддержки в...
Функция VirtualQue...
Вставка узла похож...
Стандарт AES. Алго...
Разработка собстве...
Краткое введение в...
Дополнительная инф...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?