рекурсивна функция
Концепцията за рекурсия е доста проста за разбиране и не включва познаване на конкретен формализъм или специална нотация. Като цяло, човек трябва да разглежда рекурсията като въвеждане на препратка към самия обект в дефиницията на обект или по-конкретно като метод за редуциране на решението на някакъв проблем до решението на „по-прост“ проблем от същия клас. В програмирането това се изразява в изграждането на програми (процедури и функции), които, когато се изпълняват, се отнасят директно към себе си или чрез верига от други програми.
Когато работите с подпрограми, концепциите заформални и действителни параметриса важни.Формалните параметриса идентификаторите на входните данни за подпрограмата. Ако формалните параметри получат конкретни стойности, те се наричат действителни. Формалните параметри могат да получат конкретни стойности само в програмата, където се извиква дадения модул-подпрограма.Тип иРед на действителните параметри трябва да са същите като формалните параметри. В противен случай резултатът от програмата ще бъде непредсказуем. От това следва, че действителните параметри се използват при достъп до подпрограмата от основната, а формалните параметри се използват само в самия модул.
Една функция се нарича рекурсивна, ако нейната дефиниция съдържа извикване на същата функция. Прави се разлика между проста рекурсия, когато програмният текст на функцията F директно съдържа извикване на F, и непряка рекурсия, когато F препраща към други функции, които съдържат извикване на F. Следователно рекурсивността не винаги се определя изрично от програмния текст. Познаването на механизмите за прилагане на рекурсията помага да се използва ефективно. Какво се случва, когато функция F направи рекурсивно извикване? На първо място, токсъстоянието на програмата, необходимо за продължаване на изчислението, когато контролът се върне към нея отново. Тогава F с новите стойности на аргументите започва да се изпълнява отново, сякаш с нов екземпляр на програмата. Следващото рекурсивно извикване на F повтаря всичко и т.н. докато следващото извикване на F не доведе до някакъв тривиален случай, който може да бъде разрешен без рекурсивни извиквания. След това, в реда, обратен на този, в който са били съхранени поредицата от повиквания, се извършват връщания на контрола. В практическите приложения е важно да се уверите, че максималната дълбочина на рекурсивните извиквания е не само крайна, но и достатъчно малка. В противен случай препълването на стека не може да бъде избегнато - специално организирана област от паметта, където се съхраняват отделни състояния на програмната функция.
Решаването на конкретен проблем по рекурсивния метод е разделено на няколко стъпки, основните от които са четири етапа:
2. избор на основа и възможни правила за нейното изменение,
4. извършване на разсрочени изчисления.
Първите три от тях се наричат рекурсивна триада. Нека се спрем на тези етапи по-подробно.
Параметризиранетона проблема се състои в идентифициране на набор от начални стойности, които определят формулирането и решението на проблема. Стойностите на тези параметри или някои от тях влияят върху сложността на решаването на проблема. Понякога е полезно да се въведат под внимание допълнителни параметри, които не са пряко свързани с постановката на проблема, но спомагат за организирането на рекурсията.
Базов избор- търсене на една или повече подзадачи, които могат да бъдат решени директно без рекурсивно извикване. Ако базата ще се промени в хода на изчисленията, тогава трябва да се посочи алгоритъмът за нейната промяна. По правило такава динамична база се разширява чрез получаване на решениямеждинни задачи и улеснява изпълнението на процеса на отложени изчисления. Също така е възможно да се стесни рекурсивната база.
Разлаганена общия случай е процесът на последователно разлагане на първоначалния проблем на поредица от по-прости подпроблеми, подобни на първоначалния проблем, всеки от които обикновено е по-близо до тривиалния случай от предходния по един или друг начин. Декомпозицията предполага наличието на някои изчисления, които предхождат и улесняват преходите към по-прости подзадачи. Удобно е да ги наречем предварителни изчисления. Декомпозицията трябва да се извърши по такъв начин, че да е лесно да се докаже, че за всеки допустим набор от стойности на параметри, рано или късно, ще ни доведе до един от избраните тривиални случаи, тоест до основата.
Извършване на мързелива оценка. На последния етап, решавайки една по една подзадачите, получени на етапа на декомпозиция в обратния ред на тяхното получаване, стигаме до решението на първоначалния проблем. Този етап се основава директно на съответните предварителни изчисления (предварителни изчисления).
Напишете рекурсивен алгоритъм за изчисляване на най-големия общ делител (gcd) на две цели числа.