Рекурсия – математика мен компьютерлік ғылымының фундаментальды ұғымы. Бағдарламалау тілдерінде рекурсиялы бағдарламалар деп өз-өзін шағыратын бағдарламаларды айтады. Рекурсиялы бағдарлама өзін-өзі шексіз шақыра алмайды, сондықтан, екінші негізгі ерекшелігі аяқталу шартының болуында.
Осылайша бағдарлама барысында рекурсия сол бағдарламаның өзіне негізделген, бірақ қарапайым берілімдерді қолданатын көмекші бөлігі деп қарастыруға болады.
Рекурсия екі түрлі жағдайда орындалуы мүмкін, біріншісі – рекурсиялы шақыру («күрделі» берілімдер жағдайы), екіншісі – рекурсиялы емес шақыру («қарапайым» берілімдер жағдайы.
Рекурсия және итерация. Рекурсиялы бағдарламаны кез-келген уақытта дәл сол есептеулерді орындайтын рекурсиялы емес бағдарламаға түрлендіруге болады және керісінше.
Рекурсиялы бағдарламалардың құрылымы. Рекурсиялы есептеулердің формальды схемаларына келетін болсақ, онда кем дегенде екі шығару жолы беріледі. Бірінші жағдайда есептеуді жүргізу үшін рекурсиялы шақыру кезінде қарапайым берілімдерді қолданады. Екінші жағдайда берілімдердің қарапайымдылығы соншалықты рекурсияны қолданудың қажеті де болмайды.
Мысалы, факториалды анықтау мысал ретінде қарастыруға болады
F(n) = {n*F(n-1), n> 1
{1, n = 1
Фибоначчи сандары
Ф(n) = {Ф(n-2)+Ф(n-1), n > 2
{1, n = 1,2
Немесе Ханой мұнарасы туралы есеп
T(n,a,c,b) = { T(n-1,a,b,c), a->c, T(n-1,b,c,a), n > 1
{ a->c , n = 1
Рекуррентті қатынастар. Рекуррентті қатынастар – бүтін мәнді берілімдерімен берілетін рекурсивты функция. Осындай функцияның кез-келген мәнін ең кішісінен бастап барлық мәнін есептеуді қолдану арқылы анықтауға болады.
Рекуррентті өрнекті көп жағдайда рекурсиялы есептеудің күрделілігін анықтауда қолданады.
Мысалы, рекурсивті схема арқылы Фибоначчи сандарын анықтауда.
F(i) = F(i-1) + F(i-2), при N >= 1; F(0) = 0; F(1) = 1;
Бағдарла мәтіні шамамен төмендегідей болуы мүмкін.
Function F( n : integer ) : longint;
begin
if n < 2 then F := n
else F := F(n-1) + F(n-2)
end;
Есептеу барысында F(N) мәнін қажет ететін рекурсиялы шақырудың санын келесі рекуррентті өрнекті шешу арқылы анықталады
TN = TN-1 + TN-2, при N >= 1; T0 = 1; T1 = 1
TN шамамен ФN тең, мұндағы ФN –орташа пропорция, яғни жоғарыда келтірілген бағдарлама экспоненциалды уақытты жұмсауды қажет етеді.
«Бөліп ал да басқар» әдісі. Көптеген алгоритмдер екі рекурсиялы шақыруды қолданады, әрбіреуі шамамен берілімдердің жартысымен жұмыс істейді. Мұндай рекурсиялы схема алгоритмді құрудың «бөліп ал да басқар» (divide and conquer) әдісіне сәйкес келеді.
Мысал ретінде N элементтен тұратын Item типті a[1], . . . , a[N] массивіне сақталған максимал элементті анықтауды қарастырайық. Бұл есеп массивті бір рет қарапшығу арқылы шешіледі:
Max:=a[1];
For i:=1 to N do
if a[i] > Max then Max:=a[i];
Рекурсия арқылы шешудің «бөліп ал да басқар» әдісі – тағы бір шешудің жолы.
Function Max (a array of Item; l, r : integer): Item;
var u, v: Item; m : integer;
begin
m:= (l+r)/2;
if (l = r)
then Max:= a[l]
else begin
u := Max (a, 1, m);
v := Max )a, m+1, r);
if (u > v) then Max:= u else Max:= v
end;
end;
Көп жағдайда «бөліп ал да басқар» әдісін итерациялы алгоритмдерге қарағанда тез шешуді жүргізгендіктен қолданылады. Бірақ бір маңызды кемшілігі де бар, бағдарламаны өзара тәуелсіз ішкі бағдарламаларға бөлінуі. Ішкі бағдарламалар тәуелсіз болған жағдайда есептеуге көп уақыт жұмсалады.
Мысалы, жоғарыда қарастырылған Фибоначчи сандарын есептеу схемасында N-ның үлкен мәнін қарастыру мүмкін емес, себебі көп ретті есептеуді қажет етеді және есептеудің экспоненциалды күрделі болғандығынан.
Аталған мәселені динамикалық бағдарламалау арқылы шешуге болады.
Динамикалық бағдарламалау. Рекурсиялы бағдарламалардың негізгі мақсаты есепті шешу барысында тиімді әдістерді қарастыру болып табылады. Шығыстағы динамикалық бағдарламалу(bottom-up dynamic programming) арқылы функцияның барлық мәндерін ең кішісінен бастап және де алдыңғы есептеуді нәтижесін жадыға сақтай отырып, ағымдағы есептеу барысында сол нәтижені қолдануға негізделген. Нәтижесінде уақыт үнемделеді.
Төменнен динамикалық бағдарламалау (top-down dynamic programming) бұдан да қарапайым технология. Рекурсиялы функцияның орындалуын шығыстағы динамикалық бағдарламалудағы итерация санына тең болады. Бұл рекурсиялы бағдарламаның технологиясы белгілі бір құралдарды енгізуді қажет етеді. Әрбір сақталған мәнді тексеріп отыруды ұйымдастырады.
Статистикалық K[1..100] массивінде мәндерін сақтай отырып, біз есептеулердің қайталануын болдырмаймыз.
Төменде келтірілген бағдарлама F(N) - ды N - ғы пропорционал уақытта есептейді.
Function F(n: integer): longint;
Begin
if (K[n] <> -1)
then F := K[n]
else if n < 2
then F := n
else begin
t := F(n-1) + F(n-2)
K[n] := t;
F := t
end;
Бағдарламалаудағы модульді есептеу әдісінің математикалық негізі «абстракциядан» әдісі болып табылады. Абстракцияның принципі бойынша белгілі бір жиында анықталған кез-келген теңдік қатынасы осы жиынды өзара жұптасқан қиылыспайтын және бос емес элементтерге бөледі.
Аталған класстар абстракциялар классы деп аталады, ал бөліктерге бөлу (класстар отбасы) – осы қатынасқа сәйкес фактор - жиыны болып табылады. Абстракцияның бұл принципі абстракцияның екі процессін көрсетеді: біріншіден, класстар теңдігі сияқты абстаркция ұғымын енгізу; екіншіден, сондай класстың объектісіне қатысты «абстракция» ұғымын енгізу.
Рекурсия арқылы есепті шығарудың критерийлері:
- рекурсиялы функция өз-өзін шақырады;
- әрбір рекурсивті шақыру сол сияқты есептің азайтылған түрін шығарады;
- базисты шарттарды тексеру рекурсия үдерісін тоқтатуға мүмкіндік береді;
- есептердің біреуі ғана базисты болып табылады.
Программалаудың рекурсиялы әдісі рекурсиялы функциялардың
теориясы туралы білімді қажет етеді. Программистердің бағдарламалау барысында рекурсиялы функциялардың қолданудағы мүмкіндіктер 9.2-кестеде келтірілген.
9.2-кесте – Бағдарламалауда рекурсиялы функциялардың рөлі
Рекурсиялы функциялар
|
Бағдарламалауда қалай қолданылады
|
Примитивті рекурсивты функциялар – қарапайым функцмяға рекурсияны қолду арқылы алынатын функциялар ( – нөлге тең функция,  – келіп шығу функциясы,  – аргументті таңдау функциясы)
|
Примитивті функциялар арифметикалық опреацияларды, шарттық операторды және арифметикалық циклды қолданатын программалық функцияларға сәйкес болады (итерация саны алдын ала белгілі шарттық оператор)
|
Жартылай рекурсивты функциялар дегеніміз – примитивті функцияны қолданатын функцияларды айтады.
Кез-келген примивті рекурсивты функция жартылай рекурсиялы болып келеді, себебі, жартылай рекурсивті функцияны құрайтын операторлардың құрамына примитвті рекурсиялы функцияны ұйымдастыруға арналған операторлардан тұрады.
|
Егер программалау барысында итерация саны алдын ала белгісіз және шексіз болуы мүмкін while шарттық операторын қолданатын болсақ, онда жартылай рекурсивты функциялр класына өтетін боламыз
Жартылай рекурсивты функциялар аргументтің кейбір мәндерінда анықталмауы мүмкін.
|
Ортақ рекурсиялы функциялар – барлық жерде анықталған жартылай рекурсивты функциялар
|
Примитивті рекурсивті функция барлық жерде анықталған сондықтан жалпы рекурсивті функция болып табылады.
|
Программалауда белгілі бір тілді жеткілікті түрде меңгеру төмендегідей білімді қажет етеді: (1) алгоритмді және берілімдер құрылымын; (2) программалау парадигмаларын; (3) тілдің синтаксисы мен оның операциялық және дедуктивті жүйесін; (4) программалау құралдарын жасау технологияларын; (5) программалаудың психологиялық аспектілерін.
Достарыңызбен бөлісу: |
