Рекурсия, какво представлява и примери

+10 гласа
1,938 прегледа
попитан 2016 май 27 в Обща дискусия от Kalina.Mincheva. (1,330 точки)
Здравейте,

Опитвам се да разбера какво представлява рекурсията. Може ли да ми обясните и ако може да ми дадете пример. И като цяло рекурсията използва ли се реално в програмирането или е само по университетите?

Мерси предварително

1 отговор

+5 гласа
отговорени 2016 юни 1 от Daniel Ivanov (11,160 точки)

Привет,

Рекурсията е програмна техника, която включва в себе си използването на процедури, подпрограми, функции или алгоритми, които извикват свои опростени версии един или повече пъти, при решаването на определен проблем (докато дадено условие е изпълнено), през което време резултатът от всяко повторение се изпълнява от последното извикано повторение в посока първото.

В програмирането  - рекурсията е случай, когато една подпрограма вика предходна своя функция.

На пръв поглед рекурсията изглежда парадоксално, поради впечатлението, че при приложението ѝ, обектът бива дефиниран чрез самия обект. По пътя на логиката това би довело до безкрайна цикличност, но в действителност при практическото приложение на рекурсия обектът не бива дефиниран чрез себе си, а по-прости свои версии. За лесно обяснение можем да използваме аналогията на рекурсията към матрьошките - при отваряне на голямата матрьошка, резултатът е по-опростено копие на същата матрьошка, до достигане на най-малкото нейно копие, опростено до такава степен, че не подлежи на последваща манипулация. Т.е. рекурсивното дефиниране на обект е извикване на неговата опростена версия.

Рекурсията най-често бива 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);

                }

}

коментиран 2016 юни 1 от Daniel Ivanov (11,160 точки)
Други прости примери за пряка и косвена рекурсия:

пряка:

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);

}

Има и други видове – нелинейна, споделена, акумулираща, опашкова.


И като последен пример, според мен бая изпозван и ще ти се наложи да го направиш за програма по програмиране – поне в първите 1-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);

   }

 }


Не на последно място - ако чрез използването на рекурсия, постигаме по-просто, кратко и по-лесно за разбиране решение, като това не е за сметка на ефективността и не предизвиква други странични ефекти, тогава можем да предпочетем рекурсивното решение. В противен случай, е добре да помислим дали не е по-подходящо да използваме итерация.


В книжките за програмиране има много много примери и други обяснения за рекурсия, но според мен този с матрьошките е 1 от най-добрите, за които човек може да се сети, също така и най-вече гореспоменатите Ханойски кули.
...