Рекурсивни функциии
Основни понятия.  Дефиниции и алгоритми. Извикване на функции в С.
Дефиниции и алгоритми.

За да се разбере същността на рекурсията би трябвало да се разбере каква е връзка-та между дефинициите и алгоритмите, които ползват тези дефиниции при реализа-ция на програмите. Нека дефинираме едно множество от n естествени числа. Това може да стане по следните начини:
1.Чрез изброяване на елементите му {1, 2, . . . n}
2.Словесно – това е множество от първите  n естествени числа.
Докато първата дефиниция е получена чрез изброяване, то втората дефиниция е по-обобщена, има обаче и трета метод на за задаване на това множество.
3.Това  е множество от цели числа, зпочващи с 0 и получаващи се чрез прибавяне на 1 към предишното число.
Докато първите две дефиниции са окончателни, то послесдна та не само,че описва множеството, но и дава алгоритъм за получаване на n-тия елемент на множествато. Той може да служи сам по себе си за описание на резултата, който се генерира, ако инструкциите в него подлежат на формално представяне. Задачите, които трябва да реши подобен алгоритъм се изчерпват сас следните три точки:
1.Получаване на елемент следващия елемент от множеството.
2.Проверка за принадлежността на получения елемент към множеството.
3.Проверка за това, дали са получени всички елементи от множеството.
Нека да изведем общия синтаксис на получаване на низови константа. Всички възможни константи от този тип са безкрайно много, за да могат да бъдат изброени явно ипоради  това не е ефективно използването на този начин за  задаване на  множество им. Ще използваме алгоритъм за тяхното получаване. Нека разгледаме следните символни последователности:

CODE

1	“main”            ”double”        “class”

Те се характеризират със следните особености:
-В символните последователности се включват всички символи за букви ‘a’, ‘b’, ‘c’, . . . ‘z’. –
-Във всяка последователност има различен брой символи, т.е. всяка символна последователност може да се разгледа като символ след, който има записана  символна последователност или пък няма никакъв символ.
-Така една символна последоватеност може да се определи като един единствен символ без символи след него, или като символ следван от символни последователности, съдържащи един или няколко символа.
Тогава синтаксисът на низовата константа може да се определи като:
-един единствен символ, след който няма нищо
-като един единствен символ, след който има низова последователност.
Нека да използваме тази дефиниция, за да се определи дали последователността “var”  е низова. “var” се състои от символът ‘v’ и последователността “ar”, а на свой ред тя се състои от символът ‘a’ и последователността “r”, но това е съгласно първото правило също е низова последователност. Тогава, последователността “ar” също е низова съгласно второто правило. Последователността “var” също е низова също съгласно второто правило.
Дефиницията на синтаксиса на низовата последователност е рекурсивна, защото тя се дефинира по отношение сама на себе си. Това определение поражда цикъл, в който се прилагат едни и същи дефиниции към различни данни. Излизането от цикъла става в момента, когато достигаме до символ, след който няма друг символ, или символ, който не влиза в множеството на азбучните. Това условие се нарича условие за край.
С помощта на рекурсивните дефиниции е възможно само чрез няколко операции да се дефинира неограничено множество от елементи. Например типовете данни в езика “C” биха могли да се дефинират също по рекурсивен начин:
-Прост тип данни – чрез него се определя една единствена стйност от тип float, int, char, double;
-Структуриран тип данни- чрез него се определя съвкупност от стойности, всяка, от които е или от прост тип данни, или от структуриран тип – масив, запис, линеен списък.
Пример за рекурсивна дефиниция на дървовидна структура:
-0 се нарича празно дърво, защото не съдържа в себе си други елементи;
-Ако Т1 и Т2 са дървета, то структура, която съдържа връх с два изходящи възела, също е дърво.

Извикване на функции в езика “C”.
На пръв поглед изглежда странно как една функция може да извика сама себе си и да изпълни повторно собствения си код. Компилаторът трансформира изходния код в обектен, а след това линкера го преобразува в изпълним модул, като включва достатъчно памет за съхранение на статични и глобални променлииви. Обемът на тази памет е определен по време на компилиране. Оперативната памет съдържа и динамична област - стек, която се използва разпределя и освобождава по време на изпълнение на програмата за съхраняване на динамични променливи и активиращи записи. Активиращите записи се създават от ОС при извикване на функция в програмния стек. И обратно при излизане функция съответния запис се унищожава и освобождава паметта.

Представяне на рекурсивни функции в “С”.
Данни, за които са в сила рекурсивни дефиниции биха могли да се обработмат от рекурсивни алгоритми. Рекурсивна функци написана на “C” би имала вида:

CODE

1 2 3 4 5 6 7 8 9 10 11

result_type recurs (list_of_parameters)              {    function1 ();    function2 ();    . . . . . . . . .    functionN ();    recurs ();   functionN+1 ();   . . . . . . . . . }

function1 . . . . functionN е множеот во от инструкции в тялото на рекурсивна функция, след което тя извиква сама себе си. Има два вида рекурсивни функции:
-Когато, когато в тялото й има инструкция с нейното име, тя се нарича директно рекурсивна функция
-Когато, когато в тялото й съществува функция, която я извиква, тя се нарича косвено рекурсивна функция.
По правило с рекурсивната функция се свързват множество от локални обекти константи, променливи, типове или функкции, които са определени само за тази процедура и извън нея нямат смисъл. За всяка такава функция се поражда ново множество от такива локални свързани обекти. Макар,че те носят имената на вече създадените в извикващата функция, то техните стоиности са различни и конфликтите на имената се разрешават благодарение на правилата определящи областта на действие на идентификаторите. Това правило е валидно и за стойностите на параметрите на функциите свързани с рекурсивната функция.
Подобно и на цикличните програми рекурсивните функции биха могли да доведат до безкрайни цикли и незавършени изчисления. Очевидно, че основно изискване е рекурсивно изчисление  да се управлява от правилно подбрано логическо условие.

Начинът за доказване на сходимостта на процеса се състои от проверката на следните две условия:
-Определя се функцията F(x) х е множеството от променливи, такава, че от  F(x)<=0 да следва истинността на условието за край на цикъла.
-Доказва се ,че при всяко извикване на функцията F(x) намалява.
В практическите приложения трябва да се убедим,че максималната дълбочина рукурсията е не само крайна, но и достатъчно малка. Това произтича от факта, че активацията на функцията изисква памет за променливите. Освен локалните променливи е необходимо още да се съхранява и тукущото състояние на изчисленията, за да може да се извърши възврат при завършване на активацията на текущата функция.
Известно е, че при всяко извикване на функция от опреционната система се създава
активиращ  в програмния стек и обратно при излизане от нея съответния запис се унищожава. Тези записи съхраняват следната информация:
•Стойности на локалните променливи.
•Стойности на формалните параметри, като параметър предаден като референция съдържа адреса на действителния параметър, а параметър предаден по стойност съдържа стойността на параметъра.
•Адрес за впъщане- адресът на инструкцията следващ непосредствено след инструкцията за извикване.
•Текущата стойност на функцията в случай на рекурсия.
Показана е конкретната трасировка при изпълнението на рекурсивния модул на функцията fibo. Показано е движението на активиращите записи, предизвикано от началното извикване на функцията fibo (5). Всяко извикване на функцията Предизвиква създаване на активиращ запис в програмния стек. При условие n<=2 if (n<=2) получава стойност 1, след което повече рекурсивни цикли  няма да има. Преди излизане от функцията и връщане към мястото на извикване на функцията се присвоява единица. Така,че при следващите проверки 

Пример за рекурсивна обработка на символна последователност. Тази програма е типичен пример за за съхраняване на локални стойности и обработката им в процеса на развитие.
На следната фигура е показано състоянието на входните данни и състоянието на стека по време на изпълнението на функцията.


CODE

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

/*************************/ /* Recursive Ausgabe einer     */ /* gegebenen Zeichenkette.     */ /*************************/ #include <stdio.h> #include <alloc.h> void prec () {   char ch;   ch = getchar ();   if (ch !='*')      prec (); putchar (ch); } void main () {   printf ("Geben Sie eine Zeichenkette ein ");   prec (); } T E S T *          T E S T *      T E S T *      T E S T *       T E S T * T E S T *         T E S T *        T E S T *       T E S T *

Входен буфер, състояние на динамичната памет и крайно сътояние на екрана.

След извеждането на ‘T’ става връщане на първоначалното извикване. Трябва да се обърне внимание на това как се съхраняват локалните версии на променливата ch  в управлявания от операционната система стек. Всяка локална променлива има свое собствено място в оперативната памет на машината. На всеки прочетен символ отговаря по една променлива ch и по едно рекурсивно извикване на функцията. По време на развитие в обратен ред prec извежда стоиностите в обратен ред поради това, че извикването putchar (ch); е записано след извикването на рекурсивната функция.
Проверка на условието за прекратяване на рекурсията. При работа с рекурсивни функции е необходимо винаги да се осигурява проверка на това дали е изпълнено условието за край на рекурсивните извиквания. Ако то е изпълнено, то извикване не се прави и управлението се предава към първата инструкция след рекурсивното извикване, ако има такива, а след това към мястото на обръщение.

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

CODE

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

#include <stdio.h> #define N 10 int s; void sum (int buf) {   int k=buf;   s+= k;   k--;   if (k >= 0)             // Условие за прекратяване на рекурсията      sum (k); } void main () {   int n=N;   s = 0;   sum (N);   printf ("sum = %d", s); } Резултат sum = 55

В този случай рекурсивно обръщение се прави само, ако е налице условието k>=0. С помощта на параметъра k се прехвъля стойността, която трябва да се събере към  стойността на глобалната променлива s. Рекурсивното извикване на функциято ще се прекъсне в момента, когато логическото условие прстане да се изпълнява. Към коя точка ще се предаде изпълнението на програмата? Трябва да се запомнят следните две неща в това отношение:
•При рекурсия се изпълнява един и същ код, но с достъп до различни области от паметта на машината.
•При изход от функцията управлението се предава винаги към мястото от където е започнало нейното извикване.
В конкретния случай изпълнението ще продължи от s = 55. Съществува само едно изпълнимо копие на функцията SUM, но в стека има множество активиращи записи по един за мсяко извикване на функцията. Във всеки от тях се съхранява и по една стойност за параметъра k както и адресът на операцията за извикване.
Какво ще се случи, ако се компилират и изпълнят SUM1 или SUM2 ? Тогава според организацията на вътрешната памет стекът би могъл да расте дотогава, дакато припокрие стека отделен за динамично разпределените променливи, а ако такива няма дакато се достигне границата на динамичната памет. Тогава операционната система прекратява изпълнението на програмата и извежда съобщение stack overflow.
За по-сложни рекурсивни алгоритми е по-трудно предсказуемо при конкретно какви стойности на променливите би трябвало да се прекрати изпълнението на програмата. Това налага такъв начин на пректирането им, че да се осигури изпълнението на условието за край на рекурсията.

Рекурсивни функции с параметри. Етапи на създаване на рекурсивни алгоритми.
Нека си припомним, че предаването на стойностите на параметрите при функциите с параметри в езика С става или чрез предаване на стойността или чрез предаване на адреса на параметъра. За илюстрация на казаното може да се даде пример със следните две програми:

#include <stdio.h>                                                                       #include <stdio.h>
void poin_druck (int *p)                      
void val_druck (int n)
{    {       
  if (*p>0)  {    if (n>0){
     printf (" %d", *p);
               printf (" %d ", n);
     (*p)--;                                                                                      n--;    
     poin_druck (p);                                                                       val_druck (n);
     printf (" %d", *p);                                                                 printf (“%d”, n);
  }                                                                                         }
}           
void main ()        
void main ()
{                                                                                           {
int val = 3;                                     int val = 3;
poin_druck (&val);                          val_druck (val);
} }


Резултат                                                                   
3 2 1 0 1 2

Инструкцията printf, предхожда всяко рекурсивно извикване се изпълнява по време на цикъла на рекурсивните извиквания, а тази след рекурсивното извикване по време на процеса на развиването – при всяко обратно връщане. При извикване по стойност променливата val се държи като локална променлива, така че стойностите които са написани по време на правия ход на рекурсията се извеждат отново. При наличие на извикване чрез предаване по адрес последната записана стойност 0 се записва и връща обратно по време на обратния ход на рекурсията.
Функцията create_list ()  е интересен пример за създаване на линейно свързан списък с помощта на връщаните стойности. По време на правия ход на рекурсията се създават полетата в списъка и се присвояват техните стойности, а по време на обратния ход става осъществяването на връзките между тях с помощта на връщаните стойности. Трябва да се обърне вниимание, че стойността на указателя pkopf остава неопределена почти до края на работата на рекурсивната функция. Тя се определя в момента преди приключване на работата й. При връщането от рекурсивните извиквания се задават стойностите на полетат pnext. Това е така, защото при връщане стойностите се присвояват с помощта на инструкцията  return. На полето pnext на предишния възел се присвоява адресът на текущия възел.
 
CODE

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include <stdio.h> #include <alloc.h> #define NUM 4 typedef struct list {   int data;   struct list *pnext;   } list; list *pkopf, *pbuf; int n; list* create_list (int nu) {   list* pnode;   pnode = (list*) calloc(1, sizeof (list));   pnode->data = nu;   pnode->pnext = NULL;   nu++;   if (nu<= NUM)      pnode->pnext = create_list (nu);   return pnode; } void main () {   n = 1;   pkopf=create_list (n);   pbuf = pkopf;   while (pbuf!=NULL){      printf (" %d ", pbuf->data); pbuf= pbuf->pnext;   } } Резултат   1 2 3 4

Тук са показани действията по време на правия и обратния ход на рекурсивното извикване.

 CODE

1 2 3 4

Pkopf = NULL                      Прав ход на рекрсията   Pkopf = NULL                     Обратен ход на рекрсията

Етапи на създаване на рекурсивни алгоритми. Препоръчват се пет стъпки на създаване на рекурсивни алгоритми:
1.Съпоставка на рекурсивното решение на зададеня проблем с евентуалното му итерационно. Рекурсията е подходяща, ако алгоритъмът може да се разбие на малък брой стъпки. Препоръчително е цялостният проблем да се представи с помощта на рекурентни зависимости.
2.Ясно да се дефинира основната операция, чрез решаването на която ще се стигне до решаването на целия проблем.
3.Да се опрдели условието за прекратяване на рекурсивното извикране на функцията и мястото му във функцията. То трябва да се проверява при всяко обръщение.
4.Изчисленията и условието трябва, така да се организират, че при всяко извикване да е сигурно че изменението му протича в посока прекратяване на извикванията.
5.Трябва да се определят и извънредните ситуации, които ще се обработват  да се включат в алгоритъма.
Например при определянето на числата на Фибоначи рекурсията е възможна, защото цялостния пробем е разложим на по-малки. Условието за прекратяване на рекурсията е n<=2. Многократното изпълнение ни приближава към условието за прекъсване на рекурсивните извиквания. Специалните случаи, които се обработват са n=1 и n=0. Тесе обработват брез проверката n<=2.

Рекурсивно изчисление на степенни функции.
Степеннта функция е умножение на основата сама на себе си n пъти, където n  естепенния показател. В зависимост от стойностите на основата и степенния показател съществуват следните ситуации, които трябва да се обработят.
CODE

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

Основа   a = 0     показател    х=0   резултат R = 0 Основа   a != 0 , показател     х=0   резултат R=1 Основа   a != 0 , показател     х<0   резултат R = 1/(a.a.a.... a)                                       х пъти Основа   a != 0 , показател     х=0   резултат R = a.a.a.a. … a                                         х пъти /********************/ /*  Berexhnung   von      */ /*  Potenz  N einer Zahl */ /********************/ #include <stdio.h> float berechpower (float bas, int poin) {   if (poin==0)      return (1);   else      return (bas*berechpower(bas, poin-1)); } float powers (float basis, int poin) {   if (basis==0)      return (0);   else if (poin>=0)      return (berechpower(basis, poin));   else      return (1/berechpower(basis, -poin)); } void main () { float x, y;   x = powers (3, -3);   y = powers (3, 3);   printf ("x = %f y = %f ", x, y); } Резултат x = 0.037037  y = 27.000000

Основната опрация включва умножение на основата с произведението, получено от умножението на освнвата n-1 пъти. Стойността на степенния показател определя броя на повторенията. Тъй като стойносттта на всяка основа повдигната на степен 0 е равна на 1, то условието за прекратяване на цикъла ще бъде проверката дали степенния показател е равен на 1.