From Wikipedia, the free encyclopedia
Рекурсията е понятие, използвано в области като математическата лингвистика, програмирането и особено в математиката, което означава един обект да се дефинира чрез самия себе си, чрез по-проста версия на самия себе си или като част от самия себе си. Тя дава възможност за крайна дефиниция на безкрайно множество. Посредством рекурсия се описват много математически структури и формули, като тяхното моделиране и обработка става удобно чрез рекурсивни методи.[1]
Рекурсията дава възможността да бъдат описани циклични алгоритми без да се използват оператори за цикъл. При повечето декларативни езици, като Лисп и Пролог, основна структура за повторение е рекурсията, а оператори на цикъл липсват.[1]
Рекурсията условно се разделя в две категории: директна (пряка) и индиректна (косвена). Рекурсията е пряка, когато в тялото на подпрограмата има референция към нея. Косвена е тази рекурсия, при която една подпрограма вика друга, а тя вика предходната. Съществуват и случаи на косвена рекурсия, при които подпрограмата извиква себе си, след поредица от обръщения към други подпрограми.
Правилната употреба на рекурсията води до елегантни решения на определени проблеми. Понякога нейното използване опростява значително кода и подобрява четимостта му.
Думата рекурсия произлиза от латинската дума recurrere.
Рекурсията в програмирането обикновено се обяснява с практически реализации в съответния език за програмиране. Ако се излезе и извън рамките на използвания синтаксис, концептуално рекурсията може да бъде оприличена на играчката матрьошка. Началото на рекурсията се оприличава с първоначалното състояние на играчката – една голяма кукла. При отваряне, вътре се намира по-малка версия на куклата, после още по-малка версия и така n на брой пъти, докато се стигне до т.нар. дъно на рекурсията, представляващо най-малкото копие на същата кукла, която не може да бъде отворена или манипулирана по някакъв начин. Когато се използва рекурсия трябва да се вземе предвид кога ще бъде достигнато дъното ѝ. Подобно на цикъла, рекурсията трябва да има условие, при което да спре. В противен случай се стига до грешка от типа на „Stack overflow exception“.
При практическото приложение на рекурсия обектът не се дефинира чрез себе си, а чрез по-прости свои версии. Подобно на матрьошките, при отваряне на голямата матрьошка, резултатът е по-опростено копие на същата матрьошка, до достигане на най-малкото нейно копие, опростено до такава степен, че не подлежи на последваща манипулация. Т.е. рекурсивното дефиниране на обект е извикване на неговата опростена версия.
Съществуват различни подходи за онагледяването на рекурсивно извикване, някои от които са стек и дърво. Дъглас Хофстетър обяснява в пета глава на книгата си „An Eternal Golden Braid“[2] принципа на стека чрез служител на компания: той разговаря по своя телефон с потребител А, когато друг потребител Б се обажда в същия момент. Служителят слага А на изчакване и се фокусира върху Б, докато не получава трето обаждане от потребител В. Потребител Б е оставен на изчакване, докато не приключи разговора с потребител В. После служителят се връща към Б, докато не се появи четвърти потребител Г. След приключване на последния разговор служителят може да се върне към потребител Б и впоследствие към А. Тази базова аналогия от ежедневието демонстрира рекурсивно поведение в стек, където всеки следващ елемент бива добавен и респективно изваждан от стека. Това са понятията „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“ в обектно-ориентираното програмиране, позволяващо референция в текущия контекст.
Анонимната рекурсия също така може да се приложи върху именувани функции, където извикването не се осъществява по име, а чрез уточнение, че самото извикване се осъществява от специфичната функция. Този тип рекурсия също позволява преименуването на функцията, без да се налага промяна на името, където тя се самореферира. Въпреки това, с цел добър стил на програмиране, това ѝ приложение се избягва.
Някои автори класифицират рекурсията като „структурна“ или „генеративна“. Разликата се корени в това, от къде рекурсивното извикване получава данните, с които оперира, и начинът, по който ги обработва.
Функции, които използват списъчни данни, обикновено разделят аргументите на техните преки структурни компоненти и впоследствие ги обработват. Ако някой от тях е от същия тип като входния, функцията е рекурсивна. Поради тази причина, тези функции се определят като (структурно) рекурсивни.
На база гореспоменатото може да се стигне до заключението, че определящата характеристика на структурно рекурсивната функция, а именно аргументът на всяко рекурсивно извикване, е съдържанието на поле от първоизточника. Към структурната рекурсия могат да бъдат отнесени почти всички обхождания на дървета, включително XML обработка, създаване и търсене в двоични дървета, и т.н. Вземайки предвид алгебричната структура на естествените числа (естествено число е или нула, или наследник на естествено число), функции като факториел могат да се разглеждат като структурни рекурсии.
Генеративната рекурсия е алтернативният вариант. Повечето широко разпространени рекурсивни алгоритми генерират изцяло нов резултат от изходната информация и реализират повторения върху него. Примери за генеративна рекурсия са: алгоритъм на Евклид за намиране на най-голям общ делител, бързо сортиране, двоично търсене, сортиране чрез сливане, метод на Нютон, фрактали.
Разграничението на структурна и генеративна рекурсия е важно, за да се осигури условие за прекратяване на функцията. Всички структурно рекурсивни функции са ограничени (по тип) структури от данни и могат лесно да бъдат прекратени чрез структурна индукция: всяко рекурсивно извикване получава опростена част от входните данни, до достигане на базовия случай (дъно на рекурсията). В противовес, генеративно рекурсивните функции не винаги връщат опростена версия по време на рекурсивното извикване, което създава трудности при дефинирането на условието за прекратяване и предполага повече внимание при приложението им, за да се избегне бездънна рекурсия. Генеративно рекурсивните функции често могат да бъдат интерпретирани и представени като корекурсивни функции – на всяка стъпка се генерират нови данни, например при приложението на метода на Нютон – за прекратяването на корекурсията се изисква изпълнението на условие, което не винаги може да бъде осъществено.
При разработката на компютърни програми повторението може да бъде реализирано по два начина: чрез рекурсия или итерация. Независимо че резултатите са еднакви, в зависимост от контекста се прилага единият от двата варианта. В тази секция ще бъдат разгледани разликите между тях.
При равни други условия рекурсията е по-удачният подход когато задачата може да бъде решена с опростена версия на обекта, а итерацията се прилага в случаи, когато до крайния резултат се достига чрез определен брой повторения на обекта или повторения на операции с обекта. По-конкретно рекурсията може да бъде заменена с итерация чрез изрични стекови инструкции (например push и pop), респективно итерацията – с опашкова рекурсия. В императивното програмиране итерацията е предпочитан подход, особено в случаи на проста рекурсия, тъй като по този начин се избягва голямото процесорно натоварване, предизвиквано от множеството функционални извиквания и управлението на стековите операции. Ако налице е случай на множествена рекурсия, респективно се прилага рекурсивно извикване. Във функционалните езици, за разлика от императивното програмиране, рекурсията е предпочитан вариант, поради оптимизирания разход на процесорно време при приложението на опашкова рекурсия или при невъзможност за приложение на изрична итерация.
Съществуват две изисквания за успешно приложение на рекурсивен подход:
При нея рекурсивното обръщение е последното действие, извършвано от викащата подпрограма, преди тя да се върне от своето собствено текущо обръщение.
Това позволява оптимизация, наречена премахване на опашното извикване (tail call elimination), т.е. вместо с обръщение към подпрограма (с последващо връщане към мястото на извикване) рекурсивното обръщение се реализира с обикновен преход (скок) без връщане.
При това текущият кадър от стека се използва повторно за аргументите на опашно-рекурсивното обръщение, вместо да се заделя нов.
Така рекурсията може да се превърне в итерация с постоянно количество памет, независещо от дълбочината на рекурсията.
Това намалява разхода на памет и (обикновено) подобрява бързодействието, но може да затрудни откриването на грешки.
int foo (int x, int y)
{
if (y == 0)
return x;
else
return foo(y, x % y);
}
int foo (int n)
{
if (n == 0) return 1;
return n * foo(n – 1);
}
int foo(int x)
{
if (x <= 0) return x;
return foo(x – 1);
}
int foo(int x)
{
if (x <= 0) return x;
return foo1(x);
}
int foo1(int y)
{
return foo(y – 1);
}
int foo(int x)
{
if (x <= 0) return x;
return foo1(x);
}
int foo1(int y) {
return foo(y – 1);
}
int foo(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
return foo(n – 1) + foo(n – 2);
}
Ханойската кула е математически пъзел, чието решение илюстрира рекурсията. Има три колчета, които държат дискове с различни диаметри. Голям диск не може да бъде сложен върху по-малък. Започвайки от n дискове на един кол, те трябва да бъдат преместени върху друг едно по едно. Какъв е най-малкият брой стъпки, с който можем да ги преместим?
public void move(int n, int from, int to, int via) {
if (n == 1) {
System.Console.WriteLine("Move disk from pole " + from + " to pole " + to);
} else {
move(n – 1, from, via, to);
move(1, from, to, via);
move(n – 1, via, to, from);
}
}
Двоичното търсене е метод за намиране на елемент от подреден масив, като го разделяме на половина. На всяка стъпка от двоичното търсене ще проверявате дали на m-та позиция (където m е средата на текущо разглеждания интервал) стои числото m. Ако не, то липсващото число е или на тази позиция, или наляво. Ако ли е, то значи липсващото число е на индекс, по-голям от m.
Рекурсия се използва в този алгоритъм, защото от всяка следваща стъпка се създава нов масив, като се разделя старият на половина. След това двоичното търсене се извиква рекурсивно, този път върху по-малкия масив.
public static int binarySearch(int[] array, int searchTerm, int firstIndex, int lastIndex)
{
//Елементът не е открит, изход
if(lastIndex < firstIndex)
{
return -1;
}
//Разделяме масива на две части и търсим само частта, от която се нуждаем
int middle = (lastIndex + firstIndex) / 2;
//Втората половина
if (searchTerm > array[middle])
{
//Рекурсивно извикване на метода с нови индекси
return binarySearch(array, searchTerm, middle + 1, lastIndex);
}
//Първата половина
else if (searchTerm < array[middle])
{
// Рекурсивно извикване на метода с нови индекси
return binarySearch(array, searchTerm, firstIndex, middle – 1);
}
//Елементът намерен, връщане
return middle;
}
Когато алгоритъмът за решаване на даден проблем е рекурсивен, реализирането на рекурсивно решение, може да бъде много по-четливо и елегантно от реализирането на итеративно решение на същия проблем.
Понякога дефинирането на еквивалентен итеративен алгоритъм е значително по-трудно и не е лесно да се докаже, че двата алгоритъма са еквивалентни.
В определени случаи, чрез използването на рекурсия може да се постигнат много по-прости, кратки и лесни за разбиране решения.
От друга страна рекурсивните извиквания може да консумират много повече ресурси и памет. При всяко рекурсивно извикване, в стека се заделя нова памет за аргументите, локалните променливи и връщаните резултати. При прекалено много рекурсивни извиквания може да се получи препълване на стека, поради недостиг на памет.
В дадени ситуации рекурсивните решения може да са много по-трудни за разбиране и проследяване от съответните итеративни решения.
Рекурсията е мощна програмна техника, но трябва внимателно да преценяваме, преди да я използваме. При неправилна употреба, тя може да доведе до неефективни и трудни за разбиране и поддръжка решения.
Ако чрез използването на рекурсия, постигаме по-просто, кратко и по-лесно за разбиране решение, като това не е за сметка на ефективността и не предизвиква други странични ефекти, тогава можем да предпочетем рекурсивното решение. В противен случай, е добре да помислим дали не е по-подходящо да използваме итерация.
Типични примери за неподходящо използване на рекурсия са намирането на факториел и числата на Фибоначи.
//Рекурсивно изчисляване на n!
static int FactorialRecursive(int n)
{
if (n <= 1) return 1;
return n * FactorialRecursive(n – 1);
}
//Итеративно изчисляване на n!
static int FactorialIterative(int n)
{
int sum = 1;
if (n <= 1) return sum;
while (n > 1)
{
sum *= n;
n--;
}
return sum;
}
| N | Рекурсивен | Итеративен |
|---|---|---|
| 10 | 334 ticks | 11 ticks |
| 100 | 846 ticks | 23 ticks |
| 1000 | 3368 ticks | 110 ticks |
| 10000 | 9990 ticks | 975 ticks |
| 100000 | препълване на стека | 9767 ticks |
За измерване на времето е използван System.Diagnostics.Stopwatch, където 1 tick е 100 наносекунди.
Въпреки че рекурсивният подход е по-кратък като код, той е много по-бавен от итеративния и е ограничен (поради препълване на стека).
Причината за лошата производителност е голямото натоварване при всяко рекурсивно извикване при заделяне на нова памет за аргументите и локалните променливи, а също и за връщаните резултати. Това изисква многократно повече памет, защото при n рекурсивни извиквания в паметта ще бъдат запазени n междинни резултата. При итеративния подход се използва само една променлива, в която се натрупва резултатът.
Още по-красноречив пример за неправилно приложение на рекурсивен подход е намиране на числа на Фибоначи.
//- Рекурсивно изчисление по стандартния алгоритъм -
static int FibonacciRecursive(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
return FibonacciRecursive(n – 1) + FibonacciRecursive(n – 2);
}
//- Рекурсивно изчисление по оптимизиран алгоритъм -
static Dictionary<int> resultHistory = new Dictionary<int>();
static int FibonacciRecursiveOpt(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
if (resultHistory.ContainsKey(n))
return resultHistory[n];
int result = FibonacciRecursiveOpt(n – 1) + FibonacciRecursiveOpt(n – 2);
resultHistory[n] = result;
return result;
}
// – Изчисление по итеративен подход -
static int FibonacciIterative(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
int prevPrev = 0;
int prev = 1;
int result = 0;
for (int i = 2; i <= n; i++)
{
result = prev + prevPrev;
prevPrev = prev;
prev = result;
}
return result;
}
| N | Рекурсивен | Рекурсивен оптимизиран | Итеративен |
|---|---|---|---|
| 5 | 5 ticks | 22 ticks | 9 ticks |
| 10 | 36 ticks | 49 ticks | 10 ticks |
| 20 | 2315 ticks | 61 ticks | 10 ticks |
| 30 | 180254 ticks | 65 ticks | 10 ticks |
| 100 | препълване на стека | 158 ticks | 11 ticks |
| 1000 | препълване на стека | 1470 ticks | 27 ticks |
| 10000 | препълване на стека | 13873 ticks | 190 ticks |
| 100000 | препълване на стека | препълване на стека | 3952 ticks |
И тук рекурсивният подход е много по-кратък като код, но изисква многократно повече време, за да върне очаквания резултат.
Освен същите причини както при намирането на факториела, като прехвърляне на данни от едната функция към другата, тук имаме напълно излишно неколкократно изчисляване на вече изчислени членове на редицата, която расте експоненциално.[4]
F4
/ \
F3 F2
/ \ / \
F2 F1 F1 F0
/ \
F1 F0
За намирането на F(4) например члена F(2) се изчислява два пъти, за намирането на F(5) трябва да се изчисли три пъти F(2) и два пъти F(3) и т.н. Колкото по-дълбока е рекурсията, толкова повече се влошава производителността.
Ако се използва оптимизираният рекурсивен алгоритъм (или динамично оптимизиране, още познато като memorization), при който се съхраняват стойностите на вече намерените членове, се получават значително по-добри резултати, но не със същата ефективност като при прилагането на итеративен подход.
При реалната имплементация на рекурсивни алгоритми, могат да бъдат направени редица изменения, с цел постигане на по-голяма яснота и по-висока ефективност. Чистите рекурсивни функции (като например единична проверка на базов случай, чието неизпълнение води до рекурсивна стъпка) често биват разширени по някои от следните начини:
От гледна точка на елегантността на кода „функциите обвивки“ се ползват с всеобщо одобрение, докато „даването на късо“, особено в академичните среди, се счита за по-нискокачествена техника. „Хибридните алгоритми“ от своя страна често се използват за повишаване на ефективността на кода и за да се намали натоварването на рекурсията при по-малки случаи. „Рекурсията на една ръка разстояние“ е частен случай на този подход.
Това е функция, която се извиква пряко, но тя не се обръща рекурсивно към себе си. Вместо това „обвивката“ извиква отделна, допълнителна функция, която всъщност осъществява рекурсията. „Функциите обвивки“ могат да се използват за валидиране на параметри (така, че рекурсивните функции да се разтоварят от тази задача), да извършват инициализация (да разпределят памет и да инициализират променливи), това се отнася особено за спомагателни променливи като „ниво на рекурсия“ или частични изчисления за меморизация (съхраняване на информация в паметта с цел по-нататъшното ѝ използване), и да обработват изключения и грешки. В езиците, които поддържат вложени функции (nested function), спомагателната функция може да бъде вложена във „функцията обвивка“ и да използва споделен обхват. При липса на вложени функции, помощните функции се използват вместо отделни такива и ако е възможно, като частни (private) функции (тъй като те не се извикват директно), и информацията се споделя с „функцията обвивка“, като се извиква по референция.
„Даване на късо на базовия случай“, известно още като „рекурсия на една ръка разстояние“, се състои от проверка на базовия модел, преди да се направи рекурсивното извикване, т.е. проверява се дали следващото извикване ще бъде на база на случая, вместо извикване и след това проверка на базовия случай. „Даването на късо“ се прилага най-вече от съображения за ефективност, за да се избегне натоварването предизвикано от извикване на функцията, което се връща незабавно. Трябва да се вземе в предвид, че тъй като базовият случай вече е бил проверен (непосредствено преди рекурсивната стъпка), няма нужда да се проверява отделно, но трябва да се използва функция обвивка при случаите, когато самата рекурсия започва с базовия случай. Примерно, при изчисляването на факториел стандартният ред за базовия случай е: 0! = 1, но в алгоритъма за 1! веднага се връща 1, това е „даване на късо“ и на практика може да се пропусне достигането до нулата. Това може да се облекчи чрез използването на „функция обвивка“.
„Даването на късо“ създава проблеми предимно в случаите, когато има много базови случаи. Използването на този подход създава по-сложен поток, в сравнение с ясното разделение на базовия случай и рекурсивната стъпка при стандартната рекурсия. Поради това „даването на късо“ се счита за по-ниско качествен стил на програмиране, като това важи с особена сила за академичните среди.
Рекурсивните алгоритми често са неефективни при малки обеми данни, поради натоварването предизвикано от многократните извиквания на функцията и връщането на резултат. По тази причина ефективните реализации на рекурсивни алгоритми често започват с рекурсия, но след това преминават към по-различен алгоритъм, когато обработваните данни намалеят. Пример за това е сортирането чрез сливане, което често се осъществява чрез преминаване към нерекурсивно сортиране чрез вмъкване (insertion sort), когато данните са достатъчно малки. Хибридните рекурсивни алгоритми често могат да бъдат усъвършенствани.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
