Негізгі бет
Компьютерлік ғылымдар
Рекурсивті алгоритмдердің қасиеттері
Төменде рекурсивті алгоритмдердің негізгі идеясы берілген:
Берілген есепті шешу үшін алдымен ішкі есепті, яғни дәл сол есептің кіші қосалқы нұсқасын шешу керек. Сол ішкі есептің шешімін бастапқы есептің шешімін табуда қолданамыз.
Рекурсивті алгоритм жұмыс істеуі үшін ішкі есептер нәтижесінде бастапқы нұсқаға келуі керек. -ды есептегенде ішкі есептер мәні табылғанға дейін кішірейе береді. Соңында негізгі есепке келгеніңізге көзіңізді жеткізіңіз.
Мысалы, рекурсивті әдісті қолдана отырып, теріс санның факториалын тапсақ не болатынын көрейік. -ды есептеу үшін біз -ды табуымыз керек. Алынған нәтижені -ге көбейтеміз. Бірақ мәнін табу үшін алдымен -дың шешімі керек. Ол шешімді -ге көбейтеміз. Содан соң -ды есептеп, әрі қарай осылай жалғастырамыз. Иә, сандардың мәні кішірейіп бара жатыр. Бірақ олар бастапқы -ды есептеу нұсқасынан алыстап бара жатыр. Осылайша жауап ешқашан табыла алмайды.
Рекурсия идеясын екі қарапайым ережеге бөлуге болады:
- Әрбір рекурсивті шақыру дәл сол есептің кіші нұсқасында, яғни кіші ішкі есебінде орындалуы керек.
- Рекурсивті шақырулар нәтижесінде одан әрі рекурсиясыз шешілетін бастапқы есепке келулері керек.
Матрешка қуыршақтарына оралайық. Олар ешқандай алгоритмге қатыспаса да, ең кішкентай қуыршаққа дейін(бастапқы нұсқаға ұқсас) әр қуыршақтың ішінде өзінен кіші қуыршақ бар(рекурсивті жағдайға ұқсас) екендігін көре аламыз.
Бұл мазмұн ынтымақтастықтың нәтижесі Дартмут компьютерлік ғылымы профессорлар [Томас Кормен](http://www.cs.dartmouth.edu / ~thc/) және [Дэвин Бэлком](http://www.cs.dartmouth.edu / ~devin/), сонымен қатар Хан академиясының компьютерлік оқу бағдарламасы бойынша тобы. Мазмұн лицензияланған CC-BY-NC-SA.
Талқылауға қосылғыңыз келе ме?
Әзірге посттар жоқ.