Рекурентті қатынастарды есептеу

Рекурентті қатынастарды есептеу

Қатынастың өзі қолданылатын қатынастар анықтамасы рекурсивті деп аталады. Рекурсия – Пролог тілінде программалаудың негізгі механизмдерінің бірі. Процедуралық тілдерде рекурсияны, циклдерді қолдану кезінде жететін эффектілерге қол жеткізу үшін қолдануға болады. «Ата тегі» [1, 2] қатынасын анықтау рекурсияны қолданудың мысалы бола алады. Берілген қатынасты екі ереже көмегімен бейнелеуге болады. Бірінші ереже – жақын ата-тектерін анықтаса, екіншісі – алыстарын анықтайды. Бірінші ережені «ата-ана» қатынасы арқылы оңай құруға болады:

Қатынастың өзі қолданылатын қатынастар анықтамасы рекурсивті деп аталады. Рекурсия – Пролог тілінде программалаудың негізгі механизмдерінің бірі. Процедуралық тілдерде рекурсияны, циклдерді қолдану кезінде жететін эффектілерге қол жеткізу үшін қолдануға болады. «Ата тегі» [1, 2] қатынасын анықтау рекурсияны қолданудың мысалы бола алады. Берілген қатынасты екі ереже көмегімен бейнелеуге болады. Бірінші ереже – жақын ата-тектерін анықтаса, екіншісі – алыстарын анықтайды. Бірінші ережені «ата-ана» қатынасы арқылы оңай құруға болады:

Ата-тегі (X, Z) :- ата-ана(X, Z).

 

Дәл осылай екінші ережені құруға да болады:

Ата-тегі(X, Z) :- ата-ана(X, Z).

Ата-тегі(X, Z) :- ата-ана(X, Y), ата-ана(Y, Z).

Ата-тегі(X, Z) :- ата-ана(X, Y1), ата-ана(Y1, Y2), ата-ана(Y2, Z).

…

Қатынасты жоғарыдағыдай етіп сипаттау, белгілі бір шекте ғана жұмыс істейді, яғни ата-тегін белгілі бір атаға дейін анықтайды, себебі, ата-тегі мен ұрпақ арасындағы байланыс ұзындығы қатынасты анықтайтын сөйлемнің ұзындығымен шектелген. Осындай қатынастарды рекурсияның көмегімен сипаттаған ыңғайлы. Ережелер келесі түрде болады:

 

Барлық X және Z үшін,

Барлық X және Z үшін,

X – Z-тің ата-тегі, егер

Y бар болса,

X - Y –тің ата-анасы және

Y – Z-тің ата-тегі болса.

немесе Пролог тілінде:

ата-тегі(X, Z) :- ата-анасы(X, Y), ата-тегі(Y, Z).

 

Сонымен, «ата-тегі» қатынасын анықтау келесі түрде жүргізіледі:

Ата-тегі(X, Z) :- ата-ана(X, Z).

Ата-тегі(X, Z) :- ата-ана(X, Y), ата-тегі(Y, Z).

Рекурсивті ережелерді сипаттау кезінде, рекурсияның циклде тоқтап қалуын болдырмау үшін мұқтят болу керек. Ол үшін кез-келген қатынасты рекурсивті түрде анықтау, кем дегенде екі ережеден тұруы керек:

Қатынастың бастапқы түрін анықтайтын, рекурсивті емес ереже, яғни рекурсияны тоқтату кезіндегі қатынас түрі;

Рекурсивті ереже – алғашқы мақсат, осы ереже денесінде алғашқы аргументтің жаңа мәндері жасалады. Ары қарай, аргументтің жаңа мәндері қолданылатын рекурсивті мақсат орнатылады.
Жоғарыда келтірілген «ата-тегі» қатынасының анықтамасында, бірінші фраза осы қатынастың бастапқы түрін анықтайды. Ол қатынас анықталған кезде, рекурсия тоқтатылады. Екінші фраза – бұл рекурсивті ереже. Әр шақырылған сайын бұл ереже бір саты жоғарылап отырады. «Ата-ана (X, Y)» мақсаты Y айнымалысының мәнін жасап шығарады, ал «ата-тегі (Y, Z)» рекурсивті мақсатында осы жаңа аргумент қолданылады.
Бақылау мысалдары
Пример 1. Факториалды есептеу
factorial(X, _) :- X<0, ! ,fail.
factorial (0, 1) :- !.
factorial(N, Fact) :- N1=N-1, factorial(N1, Fact1), Fact=N*Fact1.
Мысал 2. Фибоначчи сандары:
F(1,1) :- !.
F(2,1) :- !.
F(I,R) :- I>2, I1=I-1, I2=I-2, F(I1,M), F(I2,N), R=N+M.

жүктеу/скачать 117,74 Kb.

Достарыңызбен бөлісу: