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

Төменде рекурсивті алгоритмдердің негізгі идеясы берілген:

$n!$‍ шешімін табу үшін біз, алдымен, ішкі есептің шешімін таптық. Ол үшін $n$‍-нен кіші $n-1$‍ санын алып, оның факториалын$(n-1)!$‍ (бастапқы есептің кіші нұсқасы) есептедік. Алынған шешімді бастапқы есептің, яғни $n!$‍ мәнін табу үшін қолдандық.

Рекурсивті алгоритм жұмыс істеуі үшін ішкі есептер нәтижесінде бастапқы нұсқаға келуі керек. $n!$‍-ды есептегенде ішкі есептер $0!$‍ мәні табылғанға дейін кішірейе береді. Соңында негізгі есепке келгеніңізге көзіңізді жеткізіңіз.

Мысалы, рекурсивті әдісті қолдана отырып, теріс санның факториалын тапсақ не болатынын көрейік. $(-1)!$‍-ды есептеу үшін біз $(-2)!$‍-ды табуымыз керек. Алынған нәтижені $-1$‍-ге көбейтеміз. Бірақ $(-2)!$‍ мәнін табу үшін алдымен $(-3)!$‍-дың шешімі керек. Ол шешімді $-2$‍-ге көбейтеміз. Содан соң $(-3)!$‍-ды есептеп, әрі қарай осылай жалғастырамыз. Иә, сандардың мәні кішірейіп бара жатыр. Бірақ олар бастапқы $0!$‍-ды есептеу нұсқасынан алыстап бара жатыр. Осылайша жауап ешқашан табыла алмайды.

$n$‍ -нің мәні теріс емес болатындығына кепілдік бергеннің өзінде де, ішкі есептер үдемелі кішіреймесе, бізде проблема туындауы мүмкін. Келесі мысалды қарастырайық. $n!=n\cdot (n-1)!$‍ формуласын алып, екі жағын $n$‍-ге бөлейік. Нәтижесінде $n!/n=(n-1)!$‍ аламыз. Енді $n+1$‍-ге тең болатын жаңа $m$‍ айнымалысын енгізейік. Біздің формула барлық оң сандар үшін қолданылатындықтан, $n$‍-ді $m$‍-мен алмастырайық, сонда $m!/m=(m-1)!$‍ болады. $m=n+1$‍ болғандықтан, $(n+1)!/(n+1)=(n+1-1)!$‍ формуласын аламыз. Екі жағын орындарымен ауыстырып және $n+1-1=n$‍ болатындығын ескере отырып, $n!=(n+1)!/(n+1)$‍ формуласын аламыз. Бұл формула алдымен $(n+1)!$‍ мәнін тауып, нәтижені $n+1$‍-ге бөлу арқылы $n!$‍-ды есептеу мүмкін екендігіне сендіреді. Бірақ $(n+1)!$‍ есептеу үшін біз, біріншіден, $(n+2)!$‍-дың, содан соң $(n+3)!$‍-дың және тағы басқаларының мәнін табуымыз керек. Солайша біз бастапқы 0 нұсқасына ешқашан жете алмаймыз. Неліктен? Себебі әр рекурсивті ішкі есеп бізден кішірек санның орнына үлкенірек санды табуды сұрайды. Егер $n$‍ оң сан болса, негізгі 0 нұқасына жету мүмкін емес болады.

Рекурсия идеясын екі қарапайым ережеге бөлуге болады:

Матрешка қуыршақтарына оралайық. Олар ешқандай алгоритмге қатыспаса да, ең кішкентай қуыршаққа дейін(бастапқы нұсқаға ұқсас) әр қуыршақтың ішінде өзінен кіші қуыршақ бар(рекурсивті жағдайға ұқсас) екендігін көре аламыз.

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