Құйрықтық Рекурсия және Итерация

66
GCD(x, y) = gcd((bigger(x, y) modulo smaller(x, y)), smaller(x, y)). % tail 
recursive definition
GCD(0, x) = x % base case
Жоғарыда келтірілген анықтамада егер бірінші аргумент 0-ге тең болса 
негізгі нұсқа екінші аргументің мәнін қайтарады. Бұл соңғы рекурсия-
ның сол жағы аз аргументтердің жиыны ретінде көп аргумент алған кез-
де болады. Соңғы рекурсивтілікті анықтау бірінші аргументтен үлкен 
және  кіші  аргументтерді  бөлуден  қалған  рекурсивті  GCD  функцияны 
шақырады. Ал екінші аргумент соңғы аз аргументтің соңғы аз аргумент 
ретінде   GCD функциясының жаңа шақыртуында үлкен аргумент болар 
еді. 
Соңғы рекурсияның бір қасиеті анықталмаған итерацияны пайдаланып 
моделденеді және рекурсивті анықтаманың жаңа үдерістерін шақырту-
мен байланысты жадының қосымша шығындарын болдырмайды. Назар 
аударыңыздар, факториалды анықтау да, Фибоначчиді анықтау да  соңғы 
рекурсия болып табылмайды. Факториалда «көбейту» соңғы операция 
ретінде болады. Ал Фибоначчидің рекурсивті анықтамасы бар екі шақы-
ртуы бар. Соңғы рекурсияны оңтайландыру – бұл кодты оңтайландыру 
әдісі уақытты қысқартуға мүмкіндік беретін жадыны қайта пайдалануға 
арналған және атқаруды итерацияның белгісіз мерзімге соңғы рекурсия 
бағдарламасын түрлендіру арқылы тежейді. Итерациялық бағдарлама-
лар бағдарламаны баяу жүзеге асырып және жады кеңістігін шығындай-
тын стектағы жады мен уақыттың қосымша шығындарын төмендетеді. 
2.2.3.2 Сызықтық рекурсия және итерация
Сызықтық рекурсивті функцияның үлкен классы, рекурсивті анықтама-
дағы өзіне тек бір реет қана шақыратын функциялар мерзімсіз итерация 
және жинақтағышты пайдаланып итерациялық бағдарламаға түрлен-
діреді.  Жинақтағыш-  соңғы  ішінара  есептелген  нәтижені  сақтайтын 
абстракция. Итерациялық нұсқада айнымалының сол жинағы қайтадан 
қолданылады. Ал рекурсивті үдерістің шақыртулары негізгі жағдайдан 
басталып, әрбір циклдан кейін ішінара шығыс мәндерін жинап, сақтай-
тын қайталанатын кодпен алмастырады.  
2.9-мысал
Факториал функциясының итераривті нұсқасы 2.3-суретте келтірілген. 
Жинақтағыш  факториал  (0)  =  1-ге  факториал  функциясының  негізгі 
мәніне  жүктелген.  Ал  рекурсивті  шақыртулар  итерациямен  алмасты-
рылған. Әрбір қадамнан кейін жинақтағыштың мәні жаңарып тұрады. 
Бұл  рекурсияның  негізгі  жағдайының  басына  және  құрылуға  балама 

67
болады; қазіргі жағдайда оны бұрынғыдан да тиімді ететін рекурсивті 
үдеріс ашылмайды. 
Algorithm iterative_factorial
Input: value of n;
Output: accumulator value;
{ accumulator = 1;
for (i = 1; i =< n; i++) accumulator = i * accumulator;
return(accumulator);
}
2.3-сурет. Факториал функциясының итеративті нұсқасы.
2.2.4 Соңғы автоматтар
Соңғы автомат -шынайы әлемнің құбылыстарын әртүрлі 
жағдайларды (күйлерді) моделдеу арқылы моделдеуге арналған 
абстрактылы машина. Графалардағы түйіндер мен түйіндер арасындағы 
доға белгісі түріндегі күйлер арасындағы өткелдер бейнесінде болады. 
Автомат  бір  күйден  екінші  күйге  кіріс  мәндердің  негізінде  өтеді.  Бұл 
күйлердің барлығы барлық күйлерге ашық болмауы мүмкін. Бір немесе 
бірнеше бастапқы күй болады және бір немесе бірнеше соңғы күй бола-
ды. автоматтар бастапқы күйдің біреуінен бастап, соңғы күймен аяқта-
лады. 
2.10 мысал
Қыздыру және салқындату жүйесі 2.4-суретте көрсетілгендей соңғы ав-
томат сияқты моделденуі мүмкін. Үш күй келтірілген: «бөлмеде ыстық», 
«бөлмеде суық», «температура оңтайлы».  Осы күйдің барлығы баста-
пқы күй болуы мүмкін. Соған қарамастан, тек «оңтайлы температура» 
күйі ғана соңғы күй болып табылады.  
«Бөлмеде ыстық» күйінде термостат салқындай бастайды. Мұның нәти-
жесі «оңтайлы температура» күйіне өту болады. «Бөлмеде суық» күйін-
де термостат қыза бастайды. Мұның нәтижесі «оңтайлы температура» 
күйіне өту болады. Егер берілген температура мен бөлмедегі темпера-
тура  бастапқы мәннің шегінде болса, онда ешқандай дабыл берілмейді. 
2.11-мысал
2.5-суреттегі  соңғы  автомат  бағдарламадағы  айнымалылар  аттарын 
анықтайтын болады. Айнымалы ағылшын әрібі сияқты анықталады.ке-
лесілері латын әріптері немесе сандарының кез-келген санымне анықта-

68
лады. Автоматтың бастапқы күйі S0 соңғы күйі S1, ал  S2 күйі барлық 
қателіктердің шарттарын өңдеу үшін. Автомат S0 шартында басталады. 
S1шартына  өту  үшін  тек  ағылшын  әріптері  қолданылады;  кез  келген 
басқа сипаттар автоматты S0 шартынан S2 шартына алып келеді. Мұнда 
қате күй туралы дабыл алынып, атқару дұрыс аяқталатын болады. 
Room  is  hot  -  Бөлме  ыстық;  Cool  –  Салқындату;  Room  has  optimal 
temperature - Бөлменің температурасы оңтайлы; Room is cold – Бөлме 
салқын; Heat – Жылыту.
2.4-сурет. Термостаты моделдеудің соңғы автоматы.  
S
o
  (initial)  –  S
o
  (бастапқы); A  letter  –  Әріп;  S
1
  (final)  –  S
1 
(соңғы); Any 
digit, letter or ‘_’ - Кез келген сан, әріп немесе '_'; Other than digit, letter 
or ‘_’ – Саннан, әріптен немесе ‘_’ басқа; S
2
 (fail) – S
2
 (қате); Other than 
letter – Әріптен басқа. 
2.5-сурет. Айнымалылардың аттарын қабылдау үшін соңғы автомат
Бірінші әріпті қабылдағаннан кейін автомат S1 күйге көшеді. Ол жер-
де  басқа  әріп  я  болмаса  басқа  сандар  да  қабылданады.  Автомат  әріп, 
сан немесе  “_” сияқты басқа да арнайы таңбаларды алу-алмуына қара-
мастанмастан а  мА  S1 -ден S1 –ге тәуелсіз ауысады.
Басқа жағдайда ол  S2 – қате шартқа өтеді.  

69
2.3 Деректер құрылымының тұжырымдамасы
Бағдарламалау  тілдерін  қолдану  үшін  түсінуге  тиісті  мәліметтер 
құрылымында көптеген тұжырымдамалар кіріді. Кейбір маңызды тұжы-
рымдар  мыналар:  өңдеуде  қолданылатын  ағаш;  бағдарламалау  тілдері 
механизмдерінің рекурсияларында және жүзеге асыруда болымсыз пай-
даланылатын стектар; кейбір тиімді қоқыс жинау сызбаларында қолда-
нылатын тізімдер мен графиктер; және бағдарламалаудың әртүрлі пара-
дигмаларын жүзеге асыратын механизмдер мен нысандарға болымсыз 
рұхсат алу үшін қолданылатын хэштегтеу. 
2.3.1 Әрекеттер тізбегі
Әрекеттер тізбегі – тікелей алдыңғы элемент тірек элементтің позици-
ясынан  тұп-тура  бір  элементке  кем  қалыппен  тізбектей  байланысқан 
реттелген мультижиын элементтері. Мысалы, тармақ дегеніміз таңба-
сыдар тізбегі, ал файл мәліметтер нысанының тізбегі. Тіпті мәліметтер 
типінің абстарктылы стектары мына тізімдері келесі тармақта көрсетіл-
гендей әрекеттер тізбегін пайдалана отырып моделденуі мүмкін.  
Тізбекті  құрушы  элементтермен  бұрыштық  жақшалармен  белгілейміз 
'<' және '>'. Мысалы, <x, y, z>  х мәліметтер элементі 1 қалыппен бай-
ланысқан, у элементі 2-қалыппен, z элементі 3-қалыппен байланысқан 
тізбек. Егер біз екі функцияны –тізбектегі мәліметтер элементімен  ал-
дыңғы және қабылдағыш функциялар деп белгілесек, онда алдыңғы(у) 
= х және алдыңғы (z) = у, өйткені у мәліметтер элементінің қалыбы х 
мәліметтер  элементінің  қалыбынан  көп.  Ал  z  мәліметтер  элементінің 
позициясы у мәліметтер элементінің қалыбынан көп. Сәйкесінше, қа-
былдағыш(x) = y және қабылдағыш(y) = z. Тізбекпен операция элемент-
ті алу, элементті қою, элементті басқа элементпен алмастыру, екі тізбек-
ті жалғастыру, тізбек басқа тізбектің тізбегі екендігін тексеру, тізбекті 
алу  және  тізбекті  басқа  тізбекпен  алмастыру  категориясына  жатады. 
Тізбекпен жасалатын негізгі операциялар 2.5-кестеде келтірілген. 
Элемент  басынан  бастап,  соңынан  немесе  элемент  индексін  ұсыну 
арқылы  қолжетімді  болуы  мүмкін.  first  операторы  тізбектің  бірінші 
элементін қайтарады, second операторы тізбектің екінші элементін, ал 
last операторы тізбектің соңғы элементін қайтарады. Қосымша опера-
ция элемент түскеннен кейін тізбек ішінде қалғандарын анықтау болып 
табылады. rest операторы соңғы тізбектің қалған ішкі тізбегіне минус 
бірінші  элементті  береді.  Ал  оператор  butlast  соңғы  тізбектің  қалған 
ішкі тізбегіне минус соңғы элементті береді. select операторы элемент 
индексінің  және  тізбектін  екі  кірісін  қабылдап,  тізбектің  сәйкес  эле-
ментін қайтарады. Cons (construct сөзінің қысқарған түрі) берілген эле-

70
ментті соңғы тізбектің басына қойып, жаңа тізбек құрады.
 2.5 кесте. Әрекет тізбегін қосатын негізгі операциялар
Операция
Шығыс
Түсіндірме
first(1…xn>)
x1
Бірінші элемент
 тізбек
last(1…xn>)
xn
Соңғы элемент 
тізбек
rest(1…xn>)
n>
Қалған бөлік 
тізбек
butlast(1…xn>)
1,…,xn-1>
Соңғы элементті 
қоспағандағы тізбек
select(i, (1…xn>)
xi
"i"- элемент тізбек
cons(a, 1…xn>)
1,…,xn>
Ескі тізбектің басына "a" 
қосу  арқылы  жаңа  тізбек 
жасау
insert(i, a, 1…xn>)
1,…xi-1,,a,,xi+1,… xn>
append(1…xn>, 1…ym>) (1…xn, y1…ym>
тізбектің жиыны реттелген
subsequence(1…xn>,i, m)
i,…,xi+m-1>
Тізбектің іші і орыннан 
m ұзындықтан басталады
is_subseq(1…xn>,  1…
ym>)
Boolean
Қайтару  "ақиқат", егер 1…
xn> кірсе1,…ym> , басқаша 
жағдайда қайтару «Жалған»
insert  операциясы берілген элементті берілген күйге қойып, жаңа тізбек 
құрады. cons операторы – бұл қоюдың арнайы жағдайы. append опера-
торы келесідей екі тізбек болады <x1…xn>  и <y1…ym>  және екінші тіз-
бектің элементтерін бірінші тізбектің элменттерінен кейін қойып  <x1…
xn, y1…ym>  жаңа тізбек жасайды. subseq операторы үш кіріс аргументті 
қабылдайды: (1) соңғы тізбек, (2) соңғы тізбектегі бастапқы қалып және 
(3) тізбек ұзындығы мен тізбекті алу. Мысалы, subseq(<4, 5, 6, 7>, 3, 2)-
тің тізбегі <6, 7>. is_subseq предикаты кіріс ретінде екі тізбекті қабыл-
дап, тізбек екінші тізбектің тізбегі бола мА, соны тексереді. Мысалы,
is_subseq(<6, 7>, <4, 5, 6, 7>) қайтуы "ақиқат".
Тізбек  байланысқан  тізбек,  массив  немесе  векторды  пайдаланып  жү-
зеге асуы мүмкін. Мәліметтердің барлық құрылымдарының сипаттары
әртүрлі. Байланысқан тізімде элементтерге ереже бойынша жоғарыдан
аяғына дейін барады; массивте элементтер бейберекет түрде қолжетімді,
ал вектор кездейсоқ қолжетімді және атқару кезінде кеңейеді.
2.3.2 Стектар мен Тізімдер
Стектар да, тізімдер де бағдарламалау тілдерін жүзеге асыру үшін маңы-
зды. Стекар да, тізім де ағаш немесе график түрінде моделденген іздеу-
дің күрделі кеңістігін іздеуде қолданылады. Стектер (1) бағдараламалу 
тілдерін  жүзеге  асыру,  (2)  рекурсияны  өңдеу,  (3)  және  5,6  тарауларда 
айтылғандай хиптегі мәліметтердің динамикалық құрылымын басқару 

71
және қайта өңдеу кезінде қолданылады. Тізімдер 6-тарауда айтылғандай 
хиптен  бөлінген  мәліметтердің  динамикалық  құрылымын  болымсыз 
қайта жасауа қолданылады.  
2.3.2.1Стек
Стек  –  бұл  мәліметтер  тек  бір  шеттен  ғана  енгізілетін  абстрактылы 
мәліметтер типі. Енгізілген мәліметтер қашан да стектің ағымдағы ба-
сына  орналасады,  ал  мәліметтер  элементі  стектің  ағымдағы  басынан 
жоғалады; келесі шеті бекітіледі.  Оның үстіне, біз стектің жоғарғы эле-
ментін стектегі элементті жоймай-ақ оқи аламыз және біз оны бос стек 
үшін де тексере аламыз. Стектің негізгі артықшылығы - оның мәлімет-
тердің ең соңғы элементтерімен жұмыс істеу мүмкіндігі. Стектер сон-
дай-ақ «соңынан келіп – бірінші кетті» (LIFO, акроним Last In, First Out).
TOS – TOS; Empty stack - Бос стек; Stack after pushing A then B – А мен 
В басқаннан кейінгі стек; Stack after one pop operation – Бір операциядан 
кейінгі стек.
2.6.-сурет. Стек операциясы.
Стектің төрт абстрактылы операциясы бар: (1) push (стек, мәліметтер 
элементі) – мәліметтер элементінің стектің жоғарғы жағына жылжуы; 
(2) pop (стек) – стектің жоғарғы элементін оқу және жою; (3) top (стек)
– стектің  жоғарғы  элементін  стекті  өзгертусіз  оқу;  және  (4)  is_empty
(стек) – стек бос па, сонны тексеру. push (стек, мәліметтер элементі)
нұсқаулықтары  және  pop  (стек)  стекті  өзгертеді.  Push  операциясы
кезінде қойлыған элемент стектің жоғарғы элементі болады. pop(стек)
жағдайында жоғарғы элемент стектен жойылады. top(стек) нұсқаулығы
стектің жоғарғы элементін стектің мазмұнын модификациялаусыз оқи-
ды. Стек негізіндегі операциялар 2.6 суретте келтірілген.
Стек  мәліметтер  соңынан  бастап  қойылатын  және  алынатын  тізбек
ретінде моделденуі мүмкін. x элементін стеке жіберу S = <a1, a2, …, aN>
жаңа <x, a1, a2, …, aN> сапасындағы S’ стек береді және стек өлшемі
1-ге артады. Элементті S = <a1, a2, …, aN> стектен итеріп шығару жаңа
S’ = <a2, …, aN> стек береді және стек өлшемі 1-ге кемиді. Бос стек бос

72
тізбек< > ретінде моделденеді. 
Стекті  компьютер  жадысында  қолдану  екі  көрсеткішті  талап  етеді: 
бастапқы көрсеткіш және соңғы көрсеткіш. Бос стектің жоғарғы жағын 
көрсеткіш бастапқы көрсеткішке тең және толы стектің жоғарғы жағын 
көрсеткіш соңғы көрсеткішке тең. Егер стектің жоғарғы жағын көрсет-
кіш көрсеткіштің соңынан шығуға тырысса, онда бұл «жады толып кет-
ті» деген қателікті көрсетеді. 
2.3.2.2 Тізім 
Тізім – мәліметтер бір шетінен шығарылып, ал мәліметтер екінші шеті-
не қойылатын мәліметтердің абстрактылы түрі. Әдетте, мәліметтер эле-
менті тізімге келген рет бойынша шығарылады. Тізімке екі көрсеткіш 
керек:  алдыңғы  және  артқы.  Алдыңғы  көрсеткіш  бірінші  мәліметтер 
элементін  алуға  қолданылса,  артқы  көрсеткіш  жаңа  мәліметтер  эле-
ментін  қоюға  арналған.  Егер  алдыңғы  көрсеткіш  артқы  көрсеткішті 
қуып жетсе, тізім бос. Элементті тізімге қою үшін мәліметтерді артқы 
көрсеткіш көрсеткен жерге орналастырады. Ал артқы көрсеткіш бір бір-
лікке артады. Мәліметтер элементін екінші шетінен алу үшін алдыңғы 
көрсеткіш көрсеткен мәліметтер элементін алады ал алдыңғы көрсет-
кіш бір бірлікке артады. Егер «артқы» және «алдыңғы» көрсеткіштер 
2.7-суретте көрсетілген бағытта бірге қозғалатын болса, онда тізім сы-
зықтық деп аталады. Тізім «алдыңғы» және «артқы» көрсеткіштер тізім-
дегі соңғы элемент өткеннен кейін бірінші элемент өткен кезде модул 
бойынша арифметикалық операция арқылы шеңберлі болады. 
Rear – Артқы; Front – Алды; Empty queue - Бос кезек; Queue after inserting 
A then B – A мен В қосқаннан кейінгі кезек; Queue after remove operation 
- Жою операциядан кейінгі кезек.
2.7-сурет. Тізімдермен операциялар
Жою операциясынан кейінгі тізім
Шеңберлі  тізім  мәліметтер  элементін  жойғаннан  кейін  босаған  жады 
кеңістігін тиімді түрде қайта пайдаланады. 
Гипотезалық тұрғыдан тізімдер мәліметтердің жаңа элементтері артқы 
бөлікке орналасып, ал мәліметтердің бірінші элементі соңғы бөліктен 

73
жойылатын элементтер тізімі сияқты моделденуі мүмкін. Q = …, aN> тізіміне жаңа х элементін қосу жаңа Q' тізім 
береді, ал тізімнің өлшемі 1-ге артады.  Q =   тізімінен 
элементті алып тастау, жаңа Q’ =  тізімін береді, ал тізім 
өлшемі 1-ге кемиді.  
2.3.3 Референттік механизмдер
Жады ұяшықтары және тіркеуіштер ақпараттың екі түрін сақтайды: (1) 
есептеу жүргізілетін мәліметтер мәні және (2) басқа жады ұяшықтарына 
көрсететін жады ұяшықтары. Көрсеткіштер – бұл тіркеуіште немесе 
жады ұяшығында сақталатын басқа жады ұяшықтарының адресі. Көр-
сеткіштерді пайдаланудың көптеген артықшылықтары бар: 
1. Жадының  басқа  бір  бөлігінде  сақталатын  мәліметтердің  күрделі
құрылымын референттейді.
2. Физикалық жағынан көп мәліметтер құрылымының орнын ауысты-
руға кететін қосымша шығындардан қашу.
3. Атқаруға дейін айнымалы үшін жадының бөлінуін кері шегеріу. Бұл
қасиет  байланысқан  тізімдер,  ағаштар,  векторлар  және  сол  сияқты
кеңейген мәліметтер құрылымы үшін жадыны тиімді тарату үшін пай-
далануы мүмкін.
4. Физикалық жадының бірнеше блоктары әртүрлі уақытта таралатын
және көрсеткіштер арқылы байланған мәліметтер құрылымының күр-
делі логикалық іргелестер үшін жады блогын бөлу.
5. Физикалық жадыда мәліметтердің орын ауыстыруынан бағдарлама-
ның  тәуелсіздігін  қамтамасыз  етіп,  қайта  адрестеу  сілтемесі  ретінде
пайдалану.
6. Күрделі  мәліметтер  құрылымының  бөліктерін  басқа  мәліметтер
құрылымымен бірге пайдалану.
Көрсеткіштер  рекурсивті  мәліметер  құрылымы  үшін  жадының  нақты 
өлшемі компиляция кезінде белгісіз болғандықтан, байланысқан тізімер, 
ағаштар сияқты рекурсивті мәліметтер құрылымын жүзеге асыру кезін-
де  пайдаланылды.  Сонымен  қатар,  кіріс  мәліметтерге  байланысты 
мәліметтердің рекурсивті құрылымдарының өлшемдері өзгеруі мүмкін 
және компиляция кезінде бағаланбауы мүмкін емес.
Жүйелік  бағдарламалауға  жады  ұяшықтары  арқылы  әр  адам  сайын 
рұхсат алу талап етіледі. Бұл талап көрсеткіш жүйелік бағдарламалар 
бірөлшемді  массив  сияқты  моделденетін  жады  облысы  арқылы  өте 
алатын    көбейту  және  алу  мүмкіндіктерімен  қамтамасыз  етілу  қажет 

74
болғандықтан қойылады. Бұл пайдаланушы анықтаған көрсеткіш сег-
мент- белгілі бір бағдарламаны орындауға бөлінген жедел жады облы-
сы, шекарасын қиып өтпеу үшін керек.   
Көрсеткіштердің артқышылығына қарамастан, көрсеткіштерді жоғары 
деңгейлі тілдерде қолданудың негізгі үш кемшілігі бар:
1.
Көрсеткіштермен  арифметикалық  операция  жадының  секіртпелі
түрде орналасуына мүмкіндік береді. Жады ұяшығына сегменттен тыс
рұхсат  алудың  арифметикалық  операциясы  «сегменттің  бұзылуы»  қа-
тесін тудырады.
2. Программаны  компиляциялағаннан  кейін  әртүрлі  мәліметтер  түрі
бар әртүрлі айнымалылар сызықтық жадының бір кеңістігіне түрленеді;
мәліметтердің осы түрлерінің арасындағы барлық ақпарат жойылады.
Егер  біз  көрсеткіштерге  арифметиканы  жіберсек,  онда  көрсеткіштер
оқу кезінде берілген нысандардың әртүрі арқылы өтуі мүмкін немесе
мәннің өзгерісі дұрыс болмайды.
3. Мәліметтердің бірнеше құрылымымен пайдалнатын жады ұяшықта-
ры жады ұяшықтарын көрсететін көрсеткіштер босамайынша қайтадан
пайдаланылмайды.
Көрсеткіштердің осы қиындықтары себепті бағдарламаларда қателіктер
кетіп, жұмыс барысында ақау орын алады. Көрсеткіштерге байланысты
мұндай қателіктерді анықтау қиын.
2.3.4 Рекурсивті мәліметтер құрылымы. 
Рекурсивті анықталатын байланысқан тізімдер, ағаштар және векторлар 
сияқты мәліметтер құрылымының класстары бар. Байланысқан тізімдер 
тізімнің қалған бөлігінің ақпарат түйіні сияқты рекурсивті анықталады, 
ал жалпы жағдайда бос тізім болып қалады. 
<linked-list> ::= <information-node> <linked-list>
<linked-list> ::= null
Бинарлы ағаш сол жақ ағаш және оң жақ ағаш болатын ақпараттық түй-
ін сияқты рекурсивті анықталады. Жалпы жағдайда бос ағаш болады. 
<binary-tree> ::= <binary-tree><information-node><binary-tree>
<binary-tree> ::= null
Мәліметтер  құрылымы  негізіндегі  көрсеткіштерінде  тиімді  қою  және 
жою  операциялары    бар.  Алайда,  мәліметтердің  рекурсивті  құрылы-
мы мәліметтердің рекурсивті құрылымының орындалу уақытының өл-

75
шемін білмегендіктен компиляция кезінде бөлінбейді.  Мәліметтердің 
рекурсивті  құрылымы  бағдарламалардың  орындалуына  және  кіріс 
мәліметтеріне байланысты атқару кезінде өседі. Рекурсивті мәліметтер 
құрылымы жады бағдарламалаушының талабына сүйеніп, атқару кезін-
де бөлшектеніп бөлінеді. 
Бізге рекурсивті мәліметтер құрылымын жүзеге асыру үшін хип деп ата-
латын жалпы жадының арнайы облысы керек. Бұл хип біздің мәліметтер 
құрылымында оқыған хиптен өзгеше. Рекурсивті мәліметтер құрылымы 
хипке физикалық тұрғыдан атқару кезінде жадыны бөлу үшін бағдарла-
ма талап ететін жады мен рет слотының болуына негізделіп таратыла-
ды. Сол рекурсивті құрылымның әртүрлі физикалық фрагменттері көр-
сеткіштің тізбегі арқылы байланысқан. 
2.3.5 Ағаш
Ағаш  бір  немесе  бірнеше  мәліметтер  элементі  бар  және  ақпараттық 
түйіннің түйін-тармақтарына қатысты бекітілген бұтақтары бар жалпы 
ақпараттық  түйін  түрінде  ұйымдасқан  бірнеше  ақпараттық  түйіннен 
тұратын  рекурсивті  мәліметтер  құрылымы.  Негізгі  жағдай  «нөлдік» 
ағаш деп аталады. Ағаштың бірнеше тармақтары болуы мүмкін. Бинар-
лы ағаштың әрбір ақпараттық түйін үшін бір ұяшығы болады және екі-
ден көп емес бұтағы болады: сол жақ бұтақ және оң жақ бұтақ. Егер түй-
іннен таралатын бұтақтардың максималды саны "N" болса, онда ол ағаш 
"n-жұп ағаш" деп аталады.  ағаштар екі әдісті қолдану арқылы жүзеге 
асады: (1) массивтер немесе векторлар сияқты индекстелген мәліметтер 
құрылымы және (2) негізгі түйіндерді таралған түйіндерге байланысты-
ратын  көрсеткіштер.  Индекстелген  мәліметтер  құрылымы  толық  би-
нарлы ағаштарды немесе толық дерлік бинарлы ағаштарды  көрсетуге 
арналған. Толық дерлік ағаштың екі тармағы бар барлығы жапырақты 
емес түйіні болады. Тек, соңғы оң жағында 2.8 суретте көрсетілгендей 
бір сол жақ тармағы бар екі жапырақты түйіні бар. 
Көрсеткіш негізінде жүзеге асыру кез келген ағашқа жарай береді. Соған 
қарамастан, кері қайту үшін негізге түйіннің индексін есептеу мүмкінді-
гі жоқ. Көрсеткішті пайдаланып жүзеге асқан ағаш табиғатынан бағыт-
талған болып табылады: ағаштар тек негізгі түйіннен таралған түйін-
ге  ғана  алмаса  алады.  Көрсеткіштің  осы  бағытталған  қасиетінен  өтіп 
кету  үшін  бізге  негізгі  мекеннен  ұрпаққа  өткенге  дейінгі  мекежайды 
сақтайтын  стек  керек  немесе,  көрсеткішке  қосымша  негізгі  түйіннен 
ұрпақ түйінге өткен ұрпақ түйінде сақталған кері көрсеткішті пайдала-
ну керек.  Екі сызбаның да қосымша шығын жадылары бар, сондай –ақ 
атқару  уақытының  да  қосымша  шығыны  бар.  Соған  қарамастан,  стек 

76
жағдайында жадының бос шығындалуы ағаштың тереңдігімен шектел-
ген. 
Ағаш  бағдарламалау  тілдерінде  және  компиляторларда  синтаксистік 
сараптау  фазасы  кезінде  қолданылады.  «ЖӘНЕ-НЕМЕСЕ»  деп  атала-
тын  ағаштың  арнайы  түрі  логикалық  бағдарламалау  парадигмасының 
негізгі жүзеге асырылуы болып табылады және 10 тарауда кеңінен қа-
ралады.  Ағаш  сондай-ақ,  бағдарламадағы  үдерістің  немесе  үдерістегі 
блоктардың    тіркеме  құрылымын  көрсету  үшін,  пайдаланылады  және 
солайша үдерісте немесе блокта белгіленген айнымалы көлемінің дәре-
жесін түсінуге көмектеседі.  N-ағаш 10  тарауда көрсетілгендей логика-
лық бағдарламалау парадигмасындағы мәліметтер құрылымын жүзеге 
асыру үшін пайдаланылады. 
2.8-сурет. Толық дерлік бинарлы ағаш.

жүктеу/скачать 6,26 Mb.

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