Рекурсията е понятие, използвано в области като математическата лингвистика, програмирането и особено в математиката, което означава един обект да се дефинира чрез самия себе си, чрез по-проста версия на самия себе си или като част от самия себе си. Тя дава възможност за крайна дефиниция на безкрайно множество. Посредством рекурсия се описват много математически структури и формули, като тяхното моделиране и обработка става удобно чрез рекурсивни методи.
Рекурсията дава възможността да бъдат описани циклични алгоритми без да се използват оператори за цикъл. При повечето декларативни езици, като Лисп и Пролог, основна структура за повторение е рекурсията, а оператори на цикъл липсват.
Рекурсията условно се разделя в две категории: директна (пряка) и индиректна (косвена). Рекурсията е пряка, когато в тялото на подпрограмата има референция към нея. Косвена е тази рекурсия, при която една подпрограма вика друга, а тя вика предходната. Съществуват и случаи на косвена рекурсия, при които подпрограмата извиква себе си, след поредица от обръщения към други подпрограми.
Правилната употреба на рекурсията води до елегантни решения на определени проблеми. Понякога нейното използване опростява значително кода и подобрява четимостта му.
Етимология Думата рекурсия произлиза от латинската дума recurrere.
Обяснение на рекурсията
Рекурсията в програмирането обикновено се обяснява с практически реализации в съответния език за програмиране. Ако се излезе и извън рамките на използвания синтаксис, концептуално рекурсията може да бъде оприличена на играчката матрьошка. Началото на рекурсията се оприличава с първоначалното състояние на играчката – една голяма кукла. При отваряне, вътре се намира по-малка версия на куклата, после още по-малка версия и така n на брой пъти, докато се стигне до т.нар. дъно на рекурсията, представляващо най-малкото копие на същата кукла, която не може да бъде отворена или манипулирана по някакъв начин. Когато се използва рекурсия трябва да се вземе предвид кога ще бъде достигнато дъното ѝ. Подобно на цикъла, рекурсията трябва да има условие, при което да спре. В противен случай се стига до грешка от типа на „Stack overflow exception“.
При практическото приложение на рекурсия обектът не се дефинира чрез себе си, а чрез по-прости свои версии. Подобно на матрьошките, при отваряне на голямата матрьошка, резултатът е по-опростено копие на същата матрьошка, до достигане на най-малкото нейно копие, опростено до такава степен, че не подлежи на последваща манипулация. Т.е. рекурсивното дефиниране на обект е извикване на неговата опростена версия.
Съществуват различни подходи за онагледяването на рекурсивно извикване, някои от които са стек и дърво. Дъглас Хофстетър обяснява в пета глава на книгата си „An Eternal Golden Braid“ принципа на стека чрез служител на компания: той разговаря по своя телефон с потребител А, когато друг потребител Б се обажда в същия момент. Служителят слага А на изчакване и се фокусира върху Б, докато не получава трето обаждане от потребител В. Потребител Б е оставен на изчакване, докато не приключи разговора с потребител В. После служителят се връща към Б, докато не се появи четвърти потребител Г. След приключване на последния разговор служителят може да се върне към потребител Б и впоследствие към А. Тази базова аналогия от ежедневието демонстрира рекурсивно поведение в стек, където всеки следващ елемент бива добавен и респективно изваждан от стека. Това са понятията „push“ и „pop“. „Push“ обозначава спирането на конкретната операция, запомнянето на състоянието ѝ и поемането на нова задача, която стои на по-ниско ниво. „Pop“ извършва обратния процес, а именно затварянето на операцията на по-ниско ниво и връщането към предходната, която е с едно ниво нагоре.
Гореописаният процес е ясно различим при обхождане на дърво. В компютърните науки дървото е множество от разклонения, които са свързани помежду си. Тези разклонения може да имат едно или повече дъщерни разклонения. Всяко отделно разклонение се обозначава като връх, към който сочи един път. Този път се нарича още ребро. Празното множество е известно като нулев граф. В конкретния пример всеки от върховете на дървото има определена числова стойност, а целта е да се намери сумата от всички върхове в дървото. За да се извърши тази операция, ще бъде приложено рекурсивно извикване на върха и неговите дъщерни разклонения чрез следния код, реализиран на езика C#: class Node { public Node Left { get; set; } public Node Right { get; set; }
public int Value { get; set; }
public Node(int value)
this.Value = value;
class Program { static int SumNodes(Node root)
// Ако коренът има нулева стойност (нулев граф) тогава нямаме дърво if (root == null)
return 0;
// В случай, че стойността на корена е различна от 0 имаме дърво int sum = checked(root.Value + SumNodes(root.Left) + SumNodes(root.Right)); return sum;
static void Main()
Node root = new Node(5)
Left = new Node(4)
Left = new Node(2), Right = new Node(1) }, Right = new Node(3)
int sum = SumNodes(root); Console.WriteLine(sum); // 15
Долната схема представя примерното дърво, където цифрите са стойност на връх, / и \ обозначават ребрата, а @ – нулев граф:
5 / \ 4 3 /\ /\ 2 1 @ @ /\ /\ @ @ @ @
При прилагане на метода SumNodes върху корена 5, се получава следното: return корена->стойност + SumNodes (корен->ляв връх) + SumNodes (корен->десен връх); return 5 + SumNodes (връх със стойност 4) + SumNodes (връх със стойност 3);
На всяка стъпка, изписването се разширява със съдържанието на съотетния return. Получава се следното: return 5 + 4 + SumNodes (връх със стойност 2) + SumNodes (връх със стойност 1) + SumNodes (връх със стойност 3);
return 5 + 4 + 2 + SumNodes (нулев граф) + SumNodes (нулев граф) + SumNodes (връх със стойност 1) + SumNodes (връх със стойност 3); return 5 + 4 + 2 + 0 + 0 + SumNodes (връх със стойност 1) + SumNodes (връх със стойност 3); return 5 + 4 + 2 + 0 + 0 + 1 + SumNodes (нулев граф) + SumNodes (нулев граф) + SumNodes (връх със стойност 3); return 5 + 4 + 2 + 0 + 0 + 1 + 0 + 0 + SumNodes (връх със стойност 3); return 5 + 4 + 2 + 0 + 0 + 1 + 0 + 0 + 3 + SumNodes (нулев граф) + SumNodes (нулев граф); return 5 + 4 + 2 + 0 + 0 + 1 + 0 + 0 + 3 + 0 + 0 ; return 5 + 4 + 2 + 0 + 0 + 1 + 0 + 0 + 3 ; return 5 + 4 + 2 + 0 + 0 + 1 + 3 ; return 5 + 4 + 2 + 1 + 3 ; return 5 + 4 + 3 + 3 ; return 5 + 7 + 3 ; return 5 + 10 ; return 15 ;
Крайната сума, получена чрез прилагането на рекурсия е 15.
Видове рекурсия Единична и множествена рекурсия Рекурсия, която съдържа само едно извикване се нарича единична рекурсия, а рекурсия, при която е налице многократно извикване се нарича множествена рекурсия. Стандартни примери за единична рекурсия са обхождане на списък, например при линейно търсене, или при изчисляване на факториел, а такива за множествена рекурсия са: обхождане на дърво, например при обхождане в дълбочина или при намиране членовете на редица на Фибоначи.
В повечето случаи единичната рекурсия е по-ефективна от множествената и може да бъде заменена с итеративно изчисление, изпълняващо се за линейно време, заделяйки постоянно количество памет. Множествената рекурсия, от друга страна, може да изисква експоненциално нарастващо процесорно време и памет и е по-фундаментално рекурсивна, като не може да бъде заменена от итерация без изрични стекови операции.
Множествената рекурсия може да бъде сведена до единична (респективно преобразувана в итерация). Например, при изчисление на поредицата на Фибоначи, действието може да бъде сведено до единична рекурсия чрез подаването на две последователни стойности като параметри. Това се нарича двойна рекурсия, при която на всяка стъпка се подават два параметъра.
Косвена рекурсия Най-разпространените примери за рекурсия демонстрират пряка рекурсия, при която извикването е директно. За да е налице случай на косвена рекурсия е необходимо извикване от друга функция (изрично или имплицитно). Например, ако при прилагането на рекурсивен подход f извиква f, се касае за случай на пряка рекурсия, но ако f извиква g, който от своя страна вика f, тогава има налице косвена рекурсия на f. Срещат се и случаи на верижни (три или повече) функционални извиквания; например, функция 1 извиква функция 2, функция 2 извиква функция 3, и функция 3 извиква отново функция 1.
Когато в тялото на метод се извършва извикване на същия метод, методът се дефинира като пряко рекурсивен. Ако метод A се обръща към метод B, B към C, а С отново към А, се твърди, че методът А, както и методите В и C са косвено рекурсивни или взаимно рекурсивни.
Веригата от извиквания при косвената рекурсия може да съдържа както множество методи, така и специални случаи, например при наличие на едно условие се извиква един метод, а при различно – друг.
Косвената рекурсия понякога се нарича споделена рекурсия (mutual recursion), термин, при който фокусът е върху гледната точка, а не идеята. Например, когато f извиква g и след това g извиква f, който от своя страна отново извиква g, погледнато от гледна точка на f, f е индиректно рекурсивна, идентично – от гледна точка на g, отново се касае за косвена рекурсия, докато от гледна точка на двете, f и g са взаимно рекурсивни. Идентично, когато налице са три или повече функции, извикващи се взаимно, те могат да бъдат наречени множество от взаимно рекурсивни функции.
Анонимна рекурсия Рекурсията обикновено се осъществява чрез изрично поименно извикване. Въпреки това е възможно имплицитното извикване на функция на база текущ контекст, особено приложимо в анонимните функции, популярно с названието анонимна рекурсия.
В компютърните науки, анонимната рекурсия е рекурсия, която не вика изрично функцията по име, а по-скоро имплицитно я призовава в зависимост от текущия контекст. Това се реализира в някои програмни езици чрез ключове (или други конструкции), които позволяват референция.
Приложение Анонимната рекурсия обикновено намира приложение в анонимни функции, особено когато те образуват затваряния или се използват за обратно извикване, за да се избегне свързването на функцията с определено наименование.
Анонимната рекурсия главно се изразява в извикване на текущата функция, което води до пряка рекурсия. Анонимна косвена рекурсия е възможна при извикване на предходна функция, или по-рядко при връщане към по-горна функция в стека. Това самоизвикване на текущата функция е функционален еквивалент на ключовата дума „this“ в обектно-ориентираното програмиране, позволяващо референция в текущия контекст.
Анонимната рекурсия също така може да се приложи върху именувани функции, където извикването не се осъществява по име, а чрез уточнение, че самото извикване се осъществява от специфичната функция. Този тип рекурсия също позволява преименуването на функцията, без да се налага промяна на името, където тя се самореферира. Въпреки това, с цел добър стил на програмиране, това ѝ приложение се избягва.
Структурна и генеративна рекурсия Някои автори класифицират рекурсията като „структурна“ или „генеративна“. Разликата се корени в това, от къде рекурсивното извикване получава данните, с които оперира, и начинът, по който ги обработва.
Функции, които използват списъчни данни, обикновено разделят аргументите на техните преки структурни компоненти и впоследствие ги обработват. Ако някой от тях е от същия тип като входния, функцията е рекурсивна. Поради тази причина, тези функции се определят като (структурно) рекурсивни.