Помогни ни да направим Uroci.net по - богат! Добави урок

Рекурсия

Black Pearl   трудност:    видян: 10919


Какво е рекурсията, защо трябва да се използва и какви са предимствата и недостатъците ?


Първото и най-логично обяснение на рецурсията, това е нещо, което извиква само себе си като се изпълнява толкова пъти колкото е дефинирано в тялото на рекурсията. Най-често срещания пример за рекурсия, това е при дефинирането на функция f(n), която смята фактуриел. Факториел е произведението на всички числа от 1 до n. Когато цикълът завърши, в променливата fakt ще се съдържа стойността на n!. Ето и следния пример.

f(0) = 1

f(n) = n.f(n-1)

като n е естествено число и също така положително (n>0).

int fakt(int n) {
  int f = 1;
  for(int i = 1;i <= n;i++)
    f = f * i;
  return f;
}
Казваме, че функцията n! е зададена рекурсивно, понеже се описва чрез самата себе си, т.е. вместо да описваме процедурата за изчисление на n! (умножаването на числата от 1 до n), ние показваме как проблемът за изчислението на n! се свежда до пресмятането на
(n-1)! (което се предполага, че е по-лесно) и умножението на резултата с n. Защо имаме нужда от това условие? То се нарича дъно на рекурсията или още база на индукцията.
Нека да разгледаме пример, в който трябва да се изчисли 4!
4!=4.3!
3!=3.2!
2!=2.1!
1!=1.0!
 

Този процес се нарича разгъване на рекурсията. Забележете, че тук не можем да обявим веднага, че 1!=1, въпреки че за всеки нормален човек това е повече от очевидно. Тъй като обаче работим сляпо по дефиницията, нямаме никакви основания да обявим че 1!=1. Ако нямахме условието 0!=1, щяхме да продължаваме рекурсията безкрай без никаква надежда някога да разберем колко е 4! Сега обаче имаме:

0!=1
1!=1.0!=1.1=1
2!=2.1!=2.1=2
3!=3.2!=3.2=6
4!=4.3!=4.6=24
 

Пресметнахме 4!. Това се нарича свиване на рекурсията.

Извикване на функции

Вече знаете по какъв начин се извиква функция – чрез записване на името й и параметрите и в скоби. Сега да погледнем отвътре – какво прави компилаторът при извикване на една функция. За пример да разгледаме програмата:

int f(int a,int* b) {

int c = a+1;

return (*b)+a*c;

}

void main() {

int x = 10,y = 4;

cout << f(y,&x) << endl;

}

Истината е, че преди самото извикване на дадена функция, за нея не се отделя място. При извикването й в паметта се създава така наречената стекова рамка на функцията. В тази “рамка” се записват три неща – извикваща функция, стойности на параметрите и променливи на функцията. Звучи сложно, но не е така – всъщност за дадената функция стековата рамка ще изглежда например така:

 

fig-4-1.gif

main() също е функция и като другите и тя си има стекова рамка, в която пък се записват нейните променливи. В табличката за f() е записано, че е извикана от функцията main() (даже точно от кое място в main() е извикана), че параметрите й имат стойности съответно 4 и указател към x, както и че за променливата c място и й е присвоена стойност 4+1=5. Ако функцията f() беше извикала друга функция g() , тогава за нея също ще се създаде стекова рамка и ще се запише, че е извикана от f().

Важното е, че стековата рамка не се запазва завинаги. В момента когато функцията f() приключи работа, компилаторът разбира, че трябва да се върне към извикващата я функция (в случая main()) и при това изтрива стековата рамка за f(). Това обяснява защо ако променим параметъра a във f(), това няма да се отрази на y в main(). Промените остават в стековата рамка и след като функцията завършва, се изгубват безвъзвратно. Затова когато искаме да променяме стойности, предаваме като указател.

Сега да се върнем на рекурсивните функции. Да видим как ще се изпълни функцията fakt(), ако я извикаме в main() с fakt(4). Вече се вижда, че всъщност функцията не извиква себе се, а свое копие. За същата функция се създава нова стекова рамка, където параметрите са други. Картинката в случая ще изглежда така както на фиг.2


fig-4-2-2.gif

fig-4-2-1.gif

При разгъването на рекурсията ще се “разгъват” стекови рамки, докато се достигне дъното на рекурсията, т.е. n=0. След това рекурсията започва да се “свива” – стековите рамки се изтриват една след друга, като остава само резултатът от последната изпълнена функция. Сега се вижда, че всяко извикано копие на функцията има собствена памет. Така ако трябва да сметнем 100!, ще получим 101 стекови рамки, което въобще не е за пренебрегване. Докато пък първата функция, която написахме, ще използва 2 променливи, рекурсивната функция, макар и по-скромно изглеждаща, ще “изяде” цели 100. Истината е, че рекурсивните функции не винаги са толкова ефективни, колкото ни се иска, но затова пък понякога са много по-удобни от обикновените.



Коментари (2)

SunKiss на 05.01 2008 в 12:08ч.
int fakt(int n)
{
int f = 1;
if (n==0) return 1;
f = n * fakt(n-1);
return f;
}
Derp на 06.02 2013 в 16:28ч.
int fakt(int n)
{
if (n==0) return 1;
return n * fakt(n-1);
}
// :)

Регистрирайте се, за да добавите коментар


Калдейта ЕООД - © 2003-2010. Всички права запазени.
Препоръчваме: Национален Бизнес | Bomba.bg | IT Новини | Диплома.бг | TRAVEL туризъм | Реферати | AmAm.bg | Иде.ли | Курсови работи | Фото Форум | Spodeli.net | Фото-Култ | Atol.bg | Elmaz.com | MobileBulgaria.com | Казанлък.Com