Бұл хабарлама біздің веб-сайтқа сыртқы ресурстарды жүктеу кезінде қиындықтар туындағанын білдіреді.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Негізгі бет

Рекурсивті алгоритмдердің қасиеттері

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