Skip to content

🔁 Рекурсия: Принципи и Дълбочина

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

1. Анатомия на Рекурсията

За да работи коректно, всяка рекурсивна функция трябва да съдържа два задължителни компонента:

  1. Базов случай (Base Case / Дъно на рекурсията):

    • Това е най-простият случай на задачата, който може да се реши директно, без допълнителни извиквания.
    • Служи за прекратяване на рекурсията.
    • Липсата му води до безкраен цикъл и грешка Stack Overflow.

  2. Рекурсивна стъпка (Recursive Step):

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

Пример: Факториел

\(n! = n \times (n-1)!\), с базово условие \(0! = 1\).

long long factorial(int n) {
    // 1. Базов случай
    if (n == 0) return 1;

    // 2. Рекурсивна стъпка
    return n * factorial(n - 1);
}

2. Как работи "под капака"? (Call Stack)

Когато извикате функция, компютърът заделя блок памет в стека (Call Stack), наречен "Stack Frame". Той пази: * Стойностите на локалните променливи. * Параметрите на функцията. * Адреса за връщане (къде да продължи програмата след приключване).

При рекурсия тези рамки се натрупват една върху друга.

Визуализация на factorial(3):

  1. main вика factorial(3). В стека влиза рамка за \(n=3\).
  2. factorial(3) вика factorial(2). Нова рамка отгоре за \(n=2\).
  3. factorial(2) вика factorial(1). Нова рамка за \(n=1\).
  4. factorial(1) вика factorial(0). Нова рамка за \(n=0\).
  5. factorial(0) удря базовия случай и връща 1. Рамката за \(n=0\) се унищожава.
  6. factorial(1) получава 1, пресмята \(1 \times 1 = 1\) и връща 1. Рамката се унищожава.
  7. factorial(2) получава 1, пресмята \(2 \times 1 = 2\) и връща 2.
  8. factorial(3) получава 2, пресмята \(3 \times 2 = 6\) и връща 6. Стекът е празен.

Лимит на стека: В състезанията стекът обикновено е ограничен (напр. 256MB), което позволява около \(10^5\) до \(10^6\) вложени извиквания (в зависимост от броя променливи във функцията).

3. Примери за Рекурсия

3.1. Числа на Фибоначи (Класически пример и предупреждение)

\(F_n = F_{n-1} + F_{n-2}\), \(F_0=0, F_1=1\).

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
Проблем: Тази имплементация е с експоненциална сложност \(O(2^n)\), защото преизчислява едни и същи стойности многократно. За \(N=50\) ще работи милиони години. Решение: Мемоизация (съхраняване на резултатите) или итерация. Това е връзката с Динамичното програмиране.

3.2. Най-голям общ делител (Евклид)

Алгоритъмът на Евклид е естествено рекурсивен. \(\\gcd(a, b) = \\gcd(b, a \\pmod b)\), базово: \(\\gcd(a, 0) = a\).

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
Това е пример за Опашкова рекурсия (Tail Recursion) – рекурсивното извикване е последното действие във функцията. Компилаторите могат лесно да го оптимизират до цикъл, спестявайки памет.

3.3. Отпечатване на цифрите на число

Ако искаме да отпечатаме цифрите на числото 12345 отзад напред, е лесно с цикъл (n % 10). Но в правилния ред?

void printDigits(int n) {
    if (n < 10) {
        cout << n << " ";
        return;
    }
    printDigits(n / 10); // Първо отпечатай предните
    cout << n % 10 << " "; // После текущата
}

3.4. Бързо степенуване (Fast Modular Exponentiation)

Изчисляване на \(a^b \pmod m\) за \(O(\\log b)\). Идея: * Ако \(b\) е четно: \(a^b = (a^{b/2})^2\) * Ако \(b\) е нечетно: \(a^b = a \cdot a^{b-1}\)

long long power(long long a, long long b, long long m) {
    if (b == 0) return 1;
    long long temp = power(a, b / 2, m);
    long long res = (temp * temp) % m;
    if (b % 2 == 1) res = (res * a) % m;
    return res;
}

4. Често срещани грешки

  1. Липсващ базов случай: Програмата "забива" и гърми със "Segmentation fault" (поради Stack Overflow).
  2. Грешен базов случай: Например при факториел, ако пропуснете if (n == 0), ще продължи към factorial(-1).
  3. Локални vs Глобални променливи:
    • Ако дефинирате масив int arr[100000] вътре в рекурсивна функция, стекът ще се препълни почти веднага. Големите структури трябва да са глобални или подавани чрез референция (vector<int>& v).
  4. Прекалено дълбока рекурсия: Ако \(N=10^7\), рекурсията не е удачна. Използвайте цикъл.

5. Задачи за упражнение

  1. Напишете рекурсивна функция за проверка дали низ е палиндром.
  2. Напишете рекурсивна функция за двоично търсене.
  3. Ханойски кули (класическа задача).
  4. Flood Fill (запълване на област в матрица).

Рекурсията изисква практика, за да се "вижда" решението. Започнете с малки примери и рисувайте дървото на извикванията на хартия.

6. Рекурсия vs Итерация

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

Примери за преобразуване

Рекурсивна Факториел: 

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

Итеративна Факториел: 

long long factorial(int n) {
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Рекурсивна Фибоначи с мемоизация: 

long long memo[100];

long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n-1) + fib(n-2);
}

Итеративна Фибоначи: 

long long fib(int n) {
    if (n <= 1) return n;
    long long prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        long long current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

Кога да избираме итерация?

  • Когато дълбочината на рекурсията е голяма (\(> 10^5\)).
  • Когато производителността е критична (итерацията избягва overhead-а от извикване на функции).
  • Когато решението с цикъл е по-интуитивно.

Кога да избираме рекурсия?

  • Задачи с древовидна структура (обхождане на дървета, графи).
  • Алгоритми "Разделяй и владей" (Merge Sort, Quick Sort, Binary Search на дърво).
  • Когато проблемът по природа е рекурсивен (Ханойски кули, комбинаторика).

7. Backtracking (Връщане назад)

Backtracking е специална форма на рекурсия, където изпробваме всички възможни решения, и когато стигнем до задънена улица, "се връщаме назад" и пробваме друг път.

Примери:

  • N-Queens проблем: Поставете \(N\) царици на шахматна дъска \(N \times N\) така, че да не се атакуват взаимно.
  • Судоку решаване.
  • Генериране на всички подмножества.

Шаблон:

void backtrack(int position, vector<int>& current) {
    // Базов случай: намерихме валидно решение
    if (isComplete(current)) {
        printSolution(current);
        return;
    }

    // Пробваме всяка възможна стъпка
    for (int choice : getPossibleChoices(position)) {
        if (isValid(choice, current)) {
            current.push_back(choice); // Избираме
            backtrack(position + 1, current); // Рекурсия
            current.pop_back(); // Връщаме се назад (undoing)
        }
    }
}

8. Допълнителни примери

8.1. Сума на цифрите

int digitSum(int n) {
    if (n == 0) return 0;
    return n % 10 + digitSum(n / 10);
}

8.2. Обръщане на списък (Linked List)

struct Node {
    int val;
    Node* next;
};

Node* reverse(Node* head) {
    if (!head || !head->next) return head;
    Node* newHead = reverse(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

🏁 Заключение

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

Практикувайте с различни задачи, за да развиете интуиция кога рекурсията е най-подходящият подход!