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

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

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

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

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

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

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

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

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