Э. А. Абдыкеримова
жүктеу/скачать 1,31 Mb. Pdf көрінісі
|
Э.А.Абдыкеримова.ИНФОРМАТИКАНЫҢ ТЕОРИЯЛЫҚ НЕГІЗДЕРІ
|
13.11 Рекурсивті алгоритмдер Рекурсия – ішкі программаны оның ӛз ішінде тҧрып шақыру. Паскаль тілінде рекурсияны қолдануға рҧқсат етілген. Рекурсиялық алгоритм, қойылуының ӛзі рекурсиялық сипатта болатын кейбір математикалық есептерді шешкенде ӛте тиімді. Бҧл жағдайда есеп кіші ӛлшемді шағын есептер жиынтығына бӛлінеді. Классикалық мысал - N>0 және 0!=1!=1 шарттары ҥшін N!=N*(N-1)! факториалын есептеу. Мҧнда N ӛлшемді бастапқы есеп N кӛбейтінді мен N-1 шағын есебін шешуге бӛлінген. Рекурсиялық алгоритм қҧру ҥш этапты қамтиды: 1) Есепті параметрлеу; 2) Тривиалдық жағдай іздеу және оны шешу; 3) Жалпы жағдайды бейнелеу. Ішкі программа әрбір орындалған сайын оның жергілікті айнымалылары мен ішкі программадан қайту адресі жадының арнайы облысы – стекте сақталады. Ішкі программа аяқталып, одан шығу кезінде жадының бҧл бӛлігі босайды. Рекурсиялық шақыру кезінде локалдық жады босамайды, "қысқы ҧйқыға" кетеді, стекте жергілікті айнымалылардың жаңа мәндеріне жаңа облыс және жаңа қайту адресі бӛлінеді. Стекке қатынас жасау "соңынан келу – бірінші кету" (Last Іnput, Fіrst Output - LІFO) қағидасы бойынша жҥреді, сондықтан ішкі программадан шығу кезінде қайту нҥктесі – соңғы шақыру нҥктесі болады. Яғни стекті ҧйымдастыру рекурсияның жҥзеге асырылуын қамтамасыз етеді. Рекурсия – жанама болуы мҥмкін: A ішкі программасы B ішкі программасын, ал ол ӛз кезегінде A ішкі программасын шақырады. Ал бҧл Паскальдың қатаң типтендірілген - ішкі программа оған сілтеме жасалмас бҧрын сипатталуы тиіс деген принципін бҧзады. Бҧл жағдайда тӛменде анықталған ішкі программа тақырыбын алғашқы ішкі программадан жоғары шығару керек, ал ішкі программа денесінің орнына тақырыптан кейін forward қызметші сӛзін кӛрсетеді; (нҥктелі ҥтір - міндетті). Рекурсия деп ӛзін ӛзі анықтайтын немесе қҧрайтын объект. Рекурсия тек қана математика да ғана емес, кҥнделікті ӛмірде де жиі кездеседі. Рекурсия анықтамасы математикада ӛте ҥлкен қуатты аппарат. Бірнеше мысалдарға тоқталайық. Натурал сан, ағаш және анықталған функция. 1. Натурал сан: а) 0 натурал сан, б) натурал саннан кейінгі сан да натурал. 108 2. Ағаш: а) 0 ағаш (оны "бос ағаш " деп атайды), б) егер t 1 және t 2 — ағаш болса, онда оның тӛбесін қҧрайтын екі тӛменгі орналасқан ағашта ағаш болады 3 "факториал" п! функциясы (теріс емес бҥтін сан): а) 0! = 1, б) п >0: п ! = п *(п- 1)! Рекурсивті алгоритмнің артықшылығы ақырғы тҧжырым кӛмегімен объектілердің шексіз жиынын анықтауға кӛмектеседі. Сәйкесінше соңғы рекурсивтік программа кӛмегімен шексіз есептеулер жҥргізуге болады және программада бірдей қайталаулар кездеспейді. Алайда рекурсивті алгоритмдерді негізінен шығарылатын есепте, есептелетін функцияда немесе ӛңделетін берілгендер қҧрылымында нақты анықталған рекурсия бар болса. Жалпы жағдайда Р рекурсивті программасын S операторлар жиынынан (Р-ны қамтымайтын) және Р-ның ӛзінен тҧратын қандай да бір Р композициясы ретінде ӛрнектеуге болады: P=P[S,Р]. Рекурсивті программаларды ӛрнектеу ҥшін процедура немесе ішкі программа ҧғымын білу қажетті және жеткілікті, себебі олар кез-келген операторға оған қатынайтын ат қоюға мҥмкіндік туғызады. Егер қандай да бір Р процедурасы ӛз ӛзіне нақты сілтеме жасаса, онда оны тура рекурсия деп аталады, егер Р процедурасы Р-ға тура немесе жанама сілтеме жасайтын басқа Q процедурасына сілтеме жасаса, онда Р жанама рекурсия деп аталады. Сондықтан программа мәтіні бойынша рекурсиялық әрқашан айқын кӛрінбейді. Негізінен, прохедтрамен сек оры прохедтрада анықсалған және одан сыр жерде мағынары болмайсын локальді объексілер жиыны, эғни айнымалылар, конрсансалар, сипсер және прохедтралар жиыны байланырсырылады. Ондай прохедтралардың әрбір ректрривсі орындалты кезінде байланырқан локальді айнымалылардың жаңа жиыны құрылады. жүктеу/скачать 1,31 Mb. Достарыңызбен бөлісу:
|