Рекурсия

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

Най-често срещаният пример за рекурсивно дефинирана функция е следната дефиниция за функцията f(n), която е факториел;

f(0) = 1

f(n) = n · f(n − 1)   за всяко естествено число n > 0

С тази дефиниция може да се изчисли f(3) например:

f(3) = 3 · f(3 − 1)

= 3 · f(2)

= 3 · 2 · f(2 − 1)

= 3 · 2 · f(1)

= 3 · 2 · 1 · f(1 − 1)

= 3 · 2 · 1 · f(0)

= 3 · 2 · 1 · 1

= 6

Същата функция на програмния език C може да бъде написана по следния начин:

unsigned int factorial(unsigned int n)
{
  if (n == 0)
    return 1;
  else
    return n * factorial(n-1);
}

В информатиката една рекурсивна функция трябва да има поне два елемента: 1) базов случай; 2) повикване към себе си. Базовият случай е условието за излизане от рекурсията. Ако няма такова условие, то рекурсията ще продължи до безкрайност. В случая с фактореила, базовият случай е че факториел от 0 е равен на 1 - тогава рекурсията се прекъсва. Второто условие е функцията да извиква сама себе си. В горния случай функцията factorial() извиква себе си, освен ако условието за излизане от рекурсията не е удовлетворено.

Други типични примери за рекурсия са решаването на задачата за Ханойската кула и числата на Фибоначи.