Рекурсивни функции

Функция, която се обръща пряко или косвено към себе си се нарича рекурсивна. Под косвено обръщение разбираме следното: една функция F1 се обръща към функция F2, която се обръща към F1.
При всяко рекурсивно обръщение в програмния стек се разпределя памет за параметрите и локалните променливи на функцията. По-общо един обект е рекурсивен, ако частично се съдържа в себе си или е дефиниран с помощта на себе си. Езика C поддържа две езикови конструкции, които позволяват да се реализират рекурсивни алгоритми – това са рекурсивни функции и структури с рекурсия.
Пример:
n! = 1. 2. … .n, n > 0,
n! = 1, n = 0; - итеративна дефиниция (не съдържа рекурсия);

n! = n*(n-1)!, n > 0
n! = 1, n = 0; - рекурсивна дефиниция;

  1. long fact (int n)
  2. {
  3.     if (n==0) return 1;
  4.     else return n*fact(n-1);
  5. }
В общия случай рекурсията позволява да се пишат по-елегантни алгоритми и позволява лесно решаване на по-сложни задачи. Рекурсията повишава ефективността на програмисткия труд. Обикновено рекурсивните програми са по-неефективни, изискват повече ресурси (памет, време). От итерация към рекурсия се преминава лесно, обратното е доста сложно (но винаги е възможно).

Реализиране на обръщението fact (3). При това обръщение рекурсивно се извършват обръщенията fact(2), fact(1), fact (0). При изпълнението на fact (0) няма да последва рекурсивно задълбочаване, тъй като n става равно на 0 функцията ще върне стойност 1, след което ще приключи изпълнението на fact (0) и паметта разпределена в стека за n при това изпълнение ще се освободи. След това се връщаме на обръщението fact (1), което връща стойност 1, паметта за n за това обръщение се изтрива от стека и отново се връщаме на по-горното обръщение и т.н. fact (3) връща стойност 6.

Когато реализираме рекурсия трябва да има гранични условия (условия за излизане от рекурсията), които задължително се достигат. В противен случай се получава зацикляне и програмата обикновено завършва с препълване на програмния стек.
Рекурсивна функция за x на степен n;
  1. double sqr_or_pow (double x, int k = 2)
  2. {
  3.     if (k==2) return x*x;
  4.        else return x*sqr_or_pow(x, k-1);
  5. }
проблем при реализацията на рекурсията в горната програма – губи се ефективност от това, че променливата x не се променя, но влиза в стека при всяко рекурсивно обръщение. Обикновено всички вътрешни променливи, които се използват само преди рекурсивното обръщение могат да се направят външни с цел да се повиши ефективността на програмата.

Друг пример за рекурсия: рекурсивна програма, която чете низ от символи (до натискане на Enter) и го извежда в обратен ред.
  1. #include <stdio.h>
  2. void niz()
  3. {
  4.     int ch;
  5.        if ( (ch = getchar ()) != `
  6. ` )
  7.         {
  8.               niz();
  9.               putchar (ch);
  10.         }
  11. }
При първото обръщение към niz в програмния стек ще се разпредели памет за локалната променлива ch. Ако въведем низ ‘abc’ и натиснем Enter, на ch ще се присвои ‘a’ и след това рекурсивно ще се извърши второ обръщение. При второто обръщение отново ще се разпредели памет за ch и ще му се присвои стойност ‘b’. След това ще последва трето рекурсивно обръщение, при което на новата ch ще се присвои стойност ‘c’ и ще последва рекурсивно четвърто обръщение. Тук вече на новата ch ще се присвои стойност ‘ ’ и обръщението ще приключи, като се освободи паметта за ch. След това се връщаме на третото обръщение, където ch е ‘c’ и я отпечатваме, след което освобождаваме паметта за ch и приключваме третото обръщение. Връщаме се на второто обръщение, отпечатваме ‘b’, след това на първото обръщение, отпечатваме ‘a’ и изпълнението на функцията приключва.