C++ част.4 (Функции и обхват)

C++ » C++

fix3d   трудност:    видян: 6172

4.1. Рекурсия

Функция, която прави обръщение към себе си директно или индиректно, се нарича рекурсивна. Функцията gcd(), например, може да бъде написана отново като рекурсивна

rgcd( int v1, int v2 ) { if (v2 == 0 )return v1;
return rgcd( v2, v1%v2 ); }

Една рекурсивна функция трябва винаги да дефинира условие за спиране; иначе ще се получи зацикляне. В нашия случай условието за спиране е нулев остатък.

Извикването

rgcd( 15, 123 );

връща стойност 3. В таблица 4.1 са описани последователните стъпки при изпълнението.

Последното извикване rgcd(3,0) удовлетворява условието за спиране. Тя връща най-големия общ делител - 3. Тази стойност става връщаната стойност на всички предишни обръщения. Казва се, че тази стойност се промъква нагоре.

v1
v2
return

15
123
rgcd(123, 15)

123
15
rgcd( 15, 3)

15
3
rgcd( 3, 0)

3
0
3



Таблица 4.1 Стъпки при изпълнение

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

Факториел на едно число се пресмята като произведение на последователността от числа от 1 до числото. Например, факториела на 5 е 120; т.е.1 * 2 * 3 * 4 * 5 = 120

Пресмятането на факториела на едно число изисква само по себе си рекурсивно решение.

unsigned longfactorial ( int val ) {
if ( val > 1 )
return val * factorial( val - 1);
return val;
}

В този случай условието за спиране е val да има стойност 1.

Упражнение 4-1. Напишете factorial() като итеративна функция.
Упражнение 4-2. Какво ще се случи ако условието за спиране има вида if ( val != 0 )
Упражнение 4-3. Как мислите, защо връщаната стойност на функцията е дефинирана от тип unsigned long, докато аргументът е от тип int?



4.2. Функции inline

Един въпрос, който все още не е зададен директно, е защо min() беше дефинирана като отделна функция. Причината не е в намаляването на обема на текста. Фактически трябва да се напише един символ повече, т.е.

min( i, j );
вместо
i < j ? i ; j;

Ползата от дефинирането й като функция се състои в следното:

- много по-лесно се чете извикването на функцията min() отколкото един аритметичен if, особено когато i и j са сложни изрази.
- много по-лесно се променя един представител на дадена функция, отколкото тристате й появи в текста на програмата. Например, ако сме решили да променим условието така

i <= j

то намирането на всяка негова поява в текста би било досадно и може да предизвика много грешки.

- съществува единна семантика в програмата. За всяка проверка се гарантира еднотипна реализация.
- използуването на функция предполага цялостна проверка на типа на аргументите. Грешките, свързани с типа се откриват още по време на компилация.

- функциите могат да бъдат използувани повторно по-скоро, отколкото да се пишат отново за други приложения. Съществува, обаче, една основна пречка за дефинирането на min() като функция тя ще бъде значително по-бавна. Трябва да се копират два аргумента, трябва да се запазят машинните регистри, програмата трябва да се разклони към ново място. Затова написването на кода е просто по-бързо.

int minVal = i <= j ? i ; j;
intVal1 = min( i, j );

Функциите inline предлагат едно решение. Всяка функция inline се разширява “на реда” в точката на повикването си.

intVal1 = min( i, j );

се записва по време на компилация като

intVal1 = (i <= j) ? i ; j;

Извикването на функцията min() по време на изпълнение се отстранява.

Функцията min() се декларира като inline чрез ключовата дума inline в дефиницията. Трябва да отбележим, обаче, че спецификацията inline е само една препоръка за компилатора. Една рекурсивна функция, такава като gcd(), например, не може напълно да разшири inline (въпреки, че нейното първо повикване би могло да бъде разширено). Вероятно функция с дължина 1200 реда няма да бъде разширена inline. Изобщо механизмът inline е средство за оптимизиране на малки няколко редови често извиквани функции.

Страници: «1 2 3 4 5 »