Привет,
Рекурсията е програмна техника, която включва в себе си използването на процедури, подпрограми, функции или алгоритми, които извикват свои опростени версии един или повече пъти, при решаването на определен проблем (докато дадено условие е изпълнено), през което време резултатът от всяко повторение се изпълнява от последното извикано повторение в посока първото.
В програмирането - рекурсията е случай, когато една подпрограма вика предходна своя функция.
На пръв поглед рекурсията изглежда парадоксално, поради впечатлението, че при приложението ѝ, обектът бива дефиниран чрез самия обект. По пътя на логиката това би довело до безкрайна цикличност, но в действителност при практическото приложение на рекурсия обектът не бива дефиниран чрез себе си, а по-прости свои версии. За лесно обяснение можем да използваме аналогията на рекурсията към матрьошките - при отваряне на голямата матрьошка, резултатът е по-опростено копие на същата матрьошка, до достигане на най-малкото нейно копие, опростено до такава степен, че не подлежи на последваща манипулация. Т.е. рекурсивното дефиниране на обект е извикване на неговата опростена версия.
Рекурсията най-често бива 2 вида – пряка (директна) и косвена (индиректна). Има и още – тях съм ги обозначил по-надолу.
Пряка - когато в тялото на подпрограмата има референция към нея.
Косвена – рекурсия, при която една подпрограма вика друга, а тя предходната.
Може да има косвена, в която подпрограма да вика себе си, след поредица от обръщения към други подпрограми.
На въпроса дали се учи само в университета без да е полезно на практика или се ползва отговарям: Ползва се, и то много. Най-малкото, което е – един пример чрез редицата на Фибоначи:
Това са членовете на следната редица:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Всеки член на редицата се получава като сума на предходните два. Пър¬ви¬те два члена по дефиниция са равни на 1, т.е. в сила е:
F1 = F2 = 1
Fi = Fi-1 + Fi-2 (за i > 2)
Изхождайки директно от дефиницията, можем да реализираме следния рекурсивен метод за намиране на n-тото число на Фибоначи:
static long Fib(int n)
{
if (n <= 2)
{
return 1;
}
return Fib(n - 1) + Fib(n - 2);
}
За да можем да направим 1 рекурсия трябва да знаем „дъното на рекурсията“. След краен брой стъпки ще искаме да получим конкретен резултат. Затова трябва да имаме един или няколко случаи, чието решение можем да намерим директно, без рекур¬сивно извикване.
В примера с числата на Фибоначи, дъното на рекурсията е случаят, когато n e по-малко или равно на 2. При него можем директно да върнем резул¬тат, тъй като по дефиниция първите два члена на редицата на Фибоначи са равни на 1.
Ако даден рекурсивен метод няма дъно на рекурсията, тя ще стане безкрайна и резултатът ще е StackOverflowException.
Друг пример мога да дам с факториел:
Факториел от n е произведението на естествените числа от 1 до n, като по дефиниция 0! = 1.
n! = 1.2.3…n
Много по-удобно е да използваш съответната рекурентна дефиниция на факториел:
n! = 1, при n = 0
n! = n.(n-1)! за n>0
0! = 1
1! = 1 = 1.1 = 1.0!
2! = 2.1 = 2.1!
3! = 3.2.1 = 3.2!
4! = 4.3.2.1 = 4.3!
5! = 5.4.3.2.1 = 5.4!
n! = n.(n-1)!
Дъното на рекурсията е най-простият случай и това е когато n = 0, при който стойността на факториел е 1.
В останалите случаи, решаваме задачата за n-1 и умножаваме получения резултат по n. Така след краен брой стъпки, със сигурност ще достигнем дъното на рекурсията, понеже между 0 и n има краен брой естествени числа.
След като имаме налице тези ключови условия, можем да реализираме метод изчисляващ факториел:
static decimal Factorial(int n) {
// дъното на рекурсията
if (n == 0)
{
return 1;
}
// метода вика себе си
else
{
return n * Factorial(n - 1);
}
}
