Sem. 12

Рекурсия

Дефиниция

Рекурсия е програмна техника, при която даден метод извиква сам себе си при решаването на определен проблем. Такива методи наричаме рекурсивни.
Един обект наричаме рекурсивен, ако съдържа себе си или е дефиниран чрез себе си.
Рекурсията е програмна техника, чиято правилна употреба води до елегантни решения на определени проблеми. Понякога нейното използване може да опрости значително кода и да подобри четимостта му.

Предназначение

Рекурсията се прави за решаване на проблеми, които могат да бъдат разделени на по-малки, повтарящи се проблеми.
Oсобено подходящ за работа върху алгоритми, които имат много възможни разклонения и са твърде сложни за итеративен подход.

//Returns the sum of all numbers from 0 to a given integer
int sumRange(int num) {
    if (num == 0) {
         return 0;
    }

    return num + sumRange(num - 1)
}

Дъно на рекурсия

Реализирайки рекурсия, трябва да сме сигурни, че след краен брой стъпки ще получим конкретен резултат.
Tрябва да имаме един или няколко случаи, чието решение можем да намерим директно, без рекурсивно извикване. Тези случаи наричаме дъно на рекурсията.
Ако даден рекурсивен метод няма дъно на рекурсията, тя ще стане безкрайна и резултатът ще е StackOverflowException.

void stackoverflow(int random) {
    stackoverflow(random – 1);
}

int main() {
    int test = INT_MAX;
    stackoverflow(test);
}

Създаване на рекурсивни методи

Когато създаваме рекурсивни методи, трябва да разбием задачата, която решаваме, на подзадачи, за чието решение можем да използваме същия алгоритъм (рекурсивно).
Комбинирането на решенията на всички подзадачи, трябва да води до решение на изходната задача.
При всяко рекурсивно извикване, проблемната област трябва да се ограничава така, че в даден момент да бъде достигнато дъното на рекурсията, т.е. разбиването на всяка от подзадачите трябва да води рано или късно до дъното на рекурсията.

Примерна програма - factorial

Ако n е произволно естествено число, следната дефиниция на функцията факториел е рекурсивна.
Условието при n = 0 НЕ съдържа обръщение към функцията факториел и се нарича гранично.

// В тази програма е описана рекурсивната функция fact,
// която приложена към естествено, връща факториела на това число, връща факториела на това число

int fact(const int n) {
    if (n == 0) {
        return 1;
    }

    // Стойността на функцията се определя посредством обръщение към
    // самата функция в оператора return n * fact(n - 1);
    return n * fact(n - 1);
}

// В този случай, рекурсивното дефиниране на функцията факториел
// не е подходящо, тъй като съществува лесно итеративно решение

Примерна програма - gcd

Да се напише рекурсивна функция, която намира най-големия общ делител на две естествени числа.

В случая a = b играе ролята на гранично условие, защото не съдържа обръщение към функцията gcd(Greatest common divisor) и чрез него се достига "дъното".

int gcd(const int a, const int b) {
    if (a == b) {
        return a;
    }

    if (a > b) {
        return gcd(a – b, a);
    }

    return gcd(a, a - b);
}

Примерна програма - fibonacci

Напишете програма, която въвежда цяло число n и пресмята n-тото число на Фибоначи.

int fibonacci(unsigned int n) {
    if (n == 0) {
        return 0;
    }

    if (n == 1) {
        return 1;
    }

    return fibonacci(n - 1) + fibonacci(n - 2);
}

Рекурсия vs Цикли

Рекурсия:

• Рамка в стековата памет се алокира при всяко едно извикване на функцията.
• Получава се "верига" от много стекови рамки, докато се достигне дъното на рекурсията.
• Рекурсията заема много памет, защото се пазят всички стекови рамки докато не се достигне дъното.

Рискове при рекурсия:

• StackOverFlow - няма повече стекова памет, в която да се заделят нови рамки (от там идва и името на форума).
• OutOfMemory - няма повече Heap памет, в която да се заделя за рекурсивните обекти, които се инциализират вътре в рекурсивната функция.

Цикли:

• Можете да използвате цикли и без да създавате отделна функция.
• При всяка итерация в цикъла не се създава нова рамка и не се заема непрекъснато още памет.

Рискове при циклите:

• Може да се получи в някой частен случай безкраен цикъл.

Препоръка: Ако за решаването на някаква задача е уместно да се използва итеративен алгоритъм, реализирайте го.
Не се препоръчва винаги използването на рекурсия, тъй като това води до големи загуби на памет.

Задачи

Задача 1: Да се реализира рекурсивна функция, която пресмята n!

Задача 2: Да се реализира рекурсивна функция, която пресмята n-тото число на фибоначи.

Задача 3: Да се реализира рекурсивна функция, която вдига число на дадена степен.

Задача 4: Да се реализира рекурсивна функция, която приема масив от цели числа и връща сумата на елементите в него.

Задача 5: Да се реализира рекурсивна функция, която приема произволен масив и число и връща дали числото се съдържа в масива. (Линейно търсене).

Задача 6: Да се реализира рекурсивна функция, която приема сортиран масив и число и връща дали числото се съдържа в масива. (Двоично търсене).

Задача 7: Да се реализира рекурсивна функция, която приема стринг и връща дали стрингът е палиндром.

Задача 8: Да се реализира рекурсивна функция, която приема стринг и връща броя на малките и големите символи в него.